Codeforces 899 F. Letters Removing （二分、树状数组）

doggod 2018-01-29 原文

题意：

　　给你一个长度为n的字符串，给出m次操作。每次操作给出一个l,r和一个字符c，要求删除字符串l到r之间所有的c。

题解：

　　看样例可以看出，这题最大的难点在于每次在字符串中删除了前面的字符会对后面的字符产生影响。如何确定当前l和r所指的字符？这里由于对字符的位置查询相当于单点操作区间查询，可以用树状数组维护字符串的前缀和，这样就可以确定l和r的位置了（二分+树状数组：复杂度(log(n)×log(n))）。再把所有的字符放到set里面进行删除操作。注意这里因为字符的数量比较少，可以每一个字符用一个set放所含这个字符的位置，不然如果只用一个set放整个字符串进行暴力的话会超时。$.$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N = 2e5+9;
 4 int vec[MAX_N];
 5 int res[MAX_N];
 6 char tran[MAX_N];
 7 int N,M,T;
 8 set<int> st[70];
 9 set<int>::iterator it,ite;
10 vector<int> temp;
11 int name(char x)
12 {
13     if(x>='a'&&x<='z'){
14         return x-'a'+1;
15     }else if(x>='0'&&x<='9'){
16         return x-'0'+1+26;
17     }else{
18         return x-'A'+1+36;
19     }
20 }
21 void add(int x,int num)
22 {
23     for(; x<=N; x+=(x&-x))
24         vec[x] += num;
25 }
26 int sum(int x)
27 {
28     int ans = 0;
29     for(; x>0; x-=(x&-x))
30         ans += vec[x];
31     return ans;
32 }
33 int two_find(int x)
34 {
35     int l=1,r=N+1;
36     while(l<r)
37     {
38         int mid = (l+r)/2;
39         if(sum(mid) < x)l = mid+1;
40         else r = mid;
41     }
42     return l;
43 }
44 int main()
45 {
46     for(int i=0;i<70;i++) st[i].clear();
47     memset(res,0,sizeof(res));
48     cin>>N>>M;
49     getchar();
50     for(int i=1; i<=N; i++)
51     {
52         char t;
53         scanf("%c",&tran[i]);
54         st[name(tran[i])].insert(i);
55         add(i,1);
56     }
57     int l,r;
58     char t;
59     for(int i=0; i<M; i++)
60     {
61         temp.clear();
62         scanf("%d%d",&l,&r);
63         getchar();
64         scanf("%c",&t);
65         int x = name(t);
66         int pos1 = two_find(l);
67         int pos2 = two_find(r);
68         it = st[x].lower_bound(pos1);
69         while(it != st[x].end() && *it<=pos2)
70         {
71             add(*it,-1);
72             res[*it] = 1;
73             temp.push_back(*it);
74             it++;
75         }
76         for(int i=0; i<temp.size(); i++) st[x].erase(temp[i]);
77     }
78     for(int i=1;i<=N;i++) if(!res[i]) printf("%c",tran[i]);
79     printf("\n");
80     return 0;
81 }