链接
传送门
题意
给出一个长度为\(n(1 \leq n \leq 2 \cdot 10^5)\)的字符串，进行\(m(1 \leq m \leq 2 \cdot 10^5)\)次删除操作，每个删除操作将删除当前字符串\(l\)到\(r\)间所有字符\(c\)。输出\(m\)次操作之后的字符串。
思路
对每种字符都用set存下出现的位置，用树状数组来计算位置\(x\)前有多少个未被删除的字符。对于每次删除操作，利用树状数组将位置\(l\)和\(r\)转换为初始字符串中的位置，然后在set中删除并更新字符串和树状数组。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
typedef long long LL;
using namespace std;
const int maxn = 200010;
const int maxm = 260;
int n, m;
int bit[maxn];
char str[maxn];
set<int> s[maxm];
inline int lowbit(int& x) {
return x & (-x);
}
int sum(int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= lowbit(i);
}
return res;
}
void add(int i, int x) {
while(i <= n){
bit[i] += x;
i += lowbit(i);
}
return;
}
int getPos(int x) {
int L = x, R = n, m = x;
while (L <= R) {
m = (L + R) / 2;
if (sum(m) >= x) {
R = m - 1;
} else {
L = m + 1;
}
}
return L;
}
int main() {
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
for (int i = 1; str[i]; ++i) {
s[str[i]].insert(i);
add(i, 1);
}
int l, r;
char tmp[5];
while (m--) {
scanf("%d%d%s", &l, &r, tmp);
l = getPos(l);
r = getPos(r);
auto lb = s[tmp[0]].lower_bound(l);
auto ub = s[tmp[0]].upper_bound(r);
while (lb != ub) {
add(*lb, -1);
str[*lb] = 0;
++lb;
}
s[tmp[0]].erase(s[tmp[0]].lower_bound(l), ub);
}
for (int i = 1; i <= n; ++i) {
if (str[i]) {
putchar(str[i]);
}
}
puts("");
return 0;
}
|