Codeforces 899F Letters Removing

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 #include <bitset>
15 
16 using namespace std;
17 
18 typedef long long ll;
19 typedef pair<int, int> pii;
20 const int maxn = 2e5 + 10;
21 char str[maxn];
22 int n, m, cnt = 0;
23 int k[1000], last[maxn], pre[maxn], c[maxn];
24 set<int> s[100];
25 set<int>::iterator itr;
26 bool vis[maxn];
27 
28 int lowbit(int x) { return x & (-x); }
29 void update(int x) { while (x < maxn) { ++c[x]; x += lowbit(x); } }
30 int query(int x) {
31     int ret = 0;
32     while (x > 0) { ret += c[x]; x -= lowbit(x); }
33     return ret;
34 }
35 int cal(int x) {
36     int low = 1, high = n + 1, mid;
37     while (low < high) {
38         mid = (low + high) / 2;
39         if (mid - query(mid) >= x) { high = mid; } else { low = mid + 1; }
40     }
41     return high;
42 }
43 void remove(int l, int r, int x) {
44     if (s[x].empty() || *(--s[x].end()) < l) { return; }
45 //    printf("%d %d
", l, r);
46     int t = *s[x].lower_bound(l);
47     while (t <= r) {
48 //        printf("t = %d
", t);
49         s[x].erase(t); update(t); last[pre[t]] = last[t];
50         pre[last[t]] = pre[t]; t = last[t];
51     }
52 }
53 void print() {
54     memset(vis, false, sizeof(vis));
55     for (int i = 0; i < cnt; ++i) {
56         for (itr = s[i].begin(); itr != s[i].end(); ++itr) { vis[*itr] = true; }
57     }
58     for (int i = 1; i <= n; ++i) {
59         if (vis[i]) { printf("%c", str[i - 1]); }
60     }
61     printf("
");
62 }
63 
64 int main() {
65 #ifdef __AiR_H
66     freopen("F.in", "r", stdin);
67 //    freopen("out.txt", "w", stdout);
68 #endif // __AiR_H
69     scanf("%d %d %s", &n, &m, str); int l, r, t, t1, l_t, r_t; char c;
70     for (int i = 'a'; i <= 'z'; ++i) { k[i] = cnt++; }
71     for (int i = 'A'; i <= 'Z'; ++i) { k[i] = cnt++; }
72     for (int i = '0'; i <= '9'; ++i) { k[i] = cnt++; }
73     for (int i = 1; i <= n; ++i) {
74         t = k[str[i - 1]];
75         if (s[t].empty()) { s[t].insert(i); continue; }
76         t1 = *(--s[t].end()); pre[i] = t1; last[t1] = i; s[t].insert(i);
77     }
78     for (int i = 0; i < cnt; ++i) {
79         if (s[i].empty()) { continue; }
80         last[*(--s[i].end())] = n + 1;
81     }
82     while (m--) {
83         scanf("%d %d %c", &l, &r, &c);
84         l_t = cal(l); r_t = cal(r); t = k[c]; remove(l_t, r_t, t);
85     }
86     print();
87     return 0;
88 }
View Code