Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.14 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. //@justinlu
  4. //<3 for reminding me substring is bad
  5. //<3 for reminding me to use character array
  6. //<3 for reminding me that I am useless
  7. //<3 for reminding me that you are my new kouhai
  8. //<3 for reminding me that I am retarted
  9. //<3 for reminding me that my brain is small
  10. public class Main {
  11.     static int n, bit [] [] = new int [26] [100005];
  12.     public static void update(int alpha, int index){
  13.         for(int i = index;i<=n;i+=(i&-i))bit[alpha][i]++;
  14.     }
  15.     public static void remo(int alpha, int index){
  16.         for(int i = index;i<=n;i+=(i&-i))bit[alpha][i]--;
  17.     }
  18.     public static int query(int alpha, int qu){
  19.         int tot = 0;
  20.         for(int i = qu;i>0;i-=(i&-i)){
  21.             tot+=bit[alpha][i];
  22.         }
  23.         return tot;
  24.     }
  25.     public static void main(String[] args) throws IOException{
  26.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  27.         TreeSet<Integer> map [] = new TreeSet [26];
  28.         for(int i = 0;i<26;i++) map[i]=new TreeSet<Integer>();
  29.         n = Integer.parseInt(br.readLine());
  30.         char s []= br.readLine().toCharArray();
  31.         for(int i = 0;i<n;i++){
  32.             update(s[i]-'a',n-i);
  33.             map[s[i]-'a'].add(n-i);
  34.         }
  35.         int q = Integer.parseInt(br.readLine());
  36.         for(int i = 0;i<q;i++){
  37.             String op [] = br.readLine().split(" ");
  38.             if(op[0].equals("LARGEST")){
  39.                 int prev = n; int ans = 0;
  40.                 for(int j = 25;j>=0;j--){
  41.                     if(prev <= 0)break;
  42.                     if(map[j].size() == 0)continue;
  43.                     ans+=query(j,prev);
  44.                     if(map[j].first()<prev)prev=map[j].first();
  45.                 }
  46.                 System.out.println(ans);
  47.             }
  48.             else{
  49.                 int x = Integer.parseInt(op[1]);
  50.                 int c = op[2].charAt(0)-'a';
  51.                 int y = s[x]-'a';
  52.                 s[x]=op[2].charAt(0);
  53.                 remo(y,n-x);
  54.                 map[y].remove(n-x);
  55.                 update(c,n-x);
  56.                 map[c].add(n-x);
  57.             }
  58.         }
  59.     }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement