Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- //@justinlu
- //<3 for reminding me substring is bad
- //<3 for reminding me to use character array
- //<3 for reminding me that I am useless
- //<3 for reminding me that you are my new kouhai
- //<3 for reminding me that I am retarted
- //<3 for reminding me that my brain is small
- public class Main {
- static int n, bit [] [] = new int [26] [100005];
- public static void update(int alpha, int index){
- for(int i = index;i<=n;i+=(i&-i))bit[alpha][i]++;
- }
- public static void remo(int alpha, int index){
- for(int i = index;i<=n;i+=(i&-i))bit[alpha][i]--;
- }
- public static int query(int alpha, int qu){
- int tot = 0;
- for(int i = qu;i>0;i-=(i&-i)){
- tot+=bit[alpha][i];
- }
- return tot;
- }
- public static void main(String[] args) throws IOException{
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- TreeSet<Integer> map [] = new TreeSet [26];
- for(int i = 0;i<26;i++) map[i]=new TreeSet<Integer>();
- n = Integer.parseInt(br.readLine());
- char s []= br.readLine().toCharArray();
- for(int i = 0;i<n;i++){
- update(s[i]-'a',n-i);
- map[s[i]-'a'].add(n-i);
- }
- int q = Integer.parseInt(br.readLine());
- for(int i = 0;i<q;i++){
- String op [] = br.readLine().split(" ");
- if(op[0].equals("LARGEST")){
- int prev = n; int ans = 0;
- for(int j = 25;j>=0;j--){
- if(prev <= 0)break;
- if(map[j].size() == 0)continue;
- ans+=query(j,prev);
- if(map[j].first()<prev)prev=map[j].first();
- }
- System.out.println(ans);
- }
- else{
- int x = Integer.parseInt(op[1]);
- int c = op[2].charAt(0)-'a';
- int y = s[x]-'a';
- s[x]=op[2].charAt(0);
- remo(y,n-x);
- map[y].remove(n-x);
- update(c,n-x);
- map[c].add(n-x);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement