#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
struct Query{
int type, a, b;
};
struct Bit2D{
vector<int> nodes[N], d[N];
void fakeQuery(int x, int y){
for(; x > 0; x -= x & -x)
nodes[x].push_back(y);
}
void normalize(){
for(int i = 1; i < N; i++){
sort(nodes[i].begin(), nodes[i].end());
nodes[i].resize(unique(nodes[i].begin(), nodes[i].end()) - nodes[i].begin());
d[i].assign(nodes[i].size() + 1, 0);
}
}
void update(int x, int y, int val){
for(; x < N; x += x & -x){
int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
for(; p <= (int) nodes[x].size(); p += p & -p)
d[x][p] += val;
}
}
int query(int x, int y){
int res = 0;
for(; x > 0; x -= x & -x){
int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
for(; p > 0; p -= p & -p)
res += d[x][p];
}
return res;
}
} bit;
int n, q, last[N];
Query queries[N];
string s, cur;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> s;
s = '*' + s;
for(int i = 1; i <= q; i++){
string p;
cin >> p;
if (p == "query"){
queries[i].type = 0;
cin >> queries[i].a >> queries[i].b;
queries[i].b--;
} else {
queries[i].type = 1;
cin >> queries[i].a;
}
}
for(int i = 1; i <= q; i++)
if (queries[i].type == 0)
bit.fakeQuery(queries[i].a, queries[i].b);
bit.normalize();
cur = s;
set<int> empPos;
for(int i = 1; i <= n; i++){
last[i] = 0;
if (cur[i] == '0')
empPos.insert(i);
}
empPos.insert(0);
empPos.insert(n + 1);
for(int i = 1; i <= q; i++){
if (queries[i].type == 0){
int res = bit.query(queries[i].a, queries[i].b);
auto it = empPos.lower_bound(queries[i].a);
if (*it > queries[i].b)
res += (i - last[*(--it) + 1]);
cout << res << '\n';
} else {
int pos = queries[i].a;
if (cur[pos] == '0'){
empPos.erase(pos);
auto it = empPos.lower_bound(pos);
int r = *it;
int l = *(--it);
if (l + 1 <= pos - 1){
int num = i - last[l + 1];
bit.update(l + 1, l + 1, num);
bit.update(l + 1, pos, -num);
last[l + 1] = i;
}
if (pos + 1 <= r - 1){
int num = i - last[pos + 1];
bit.update(pos + 1, pos + 1, num);
bit.update(pos + 1, r, -num);
last[pos + 1] = i;
}
cur[pos] = '1';
last[pos] = i;
} else {
auto it = empPos.lower_bound(pos);
int r = *it;
int l = *(--it);
if (l + 1 <= r - 1){
int num = i - last[l + 1];
bit.update(l + 1, l + 1, num);
bit.update(l + 1, r, -num);
last[l + 1] = i;
}
last[pos + 1] = i;
empPos.insert(pos);
cur[pos] = '0';
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
23812 KB |
Output is correct |
2 |
Correct |
25 ms |
23708 KB |
Output is correct |
3 |
Correct |
25 ms |
23776 KB |
Output is correct |
4 |
Correct |
32 ms |
23716 KB |
Output is correct |
5 |
Correct |
24 ms |
23708 KB |
Output is correct |
6 |
Correct |
23 ms |
23724 KB |
Output is correct |
7 |
Correct |
23 ms |
23816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
30536 KB |
Output is correct |
2 |
Correct |
245 ms |
30788 KB |
Output is correct |
3 |
Correct |
397 ms |
32540 KB |
Output is correct |
4 |
Correct |
1275 ms |
50448 KB |
Output is correct |
5 |
Correct |
1364 ms |
52216 KB |
Output is correct |
6 |
Correct |
1097 ms |
47932 KB |
Output is correct |
7 |
Correct |
1434 ms |
67372 KB |
Output is correct |
8 |
Correct |
1081 ms |
54648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23884 KB |
Output is correct |
2 |
Correct |
24 ms |
23884 KB |
Output is correct |
3 |
Correct |
24 ms |
23884 KB |
Output is correct |
4 |
Correct |
25 ms |
23852 KB |
Output is correct |
5 |
Correct |
685 ms |
43408 KB |
Output is correct |
6 |
Correct |
1140 ms |
48112 KB |
Output is correct |
7 |
Correct |
1217 ms |
51184 KB |
Output is correct |
8 |
Correct |
1101 ms |
56004 KB |
Output is correct |
9 |
Correct |
164 ms |
30776 KB |
Output is correct |
10 |
Correct |
177 ms |
31312 KB |
Output is correct |
11 |
Correct |
183 ms |
31560 KB |
Output is correct |
12 |
Correct |
1460 ms |
68648 KB |
Output is correct |
13 |
Correct |
1073 ms |
56024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
23884 KB |
Output is correct |
2 |
Correct |
24 ms |
23852 KB |
Output is correct |
3 |
Correct |
32 ms |
23840 KB |
Output is correct |
4 |
Correct |
24 ms |
23844 KB |
Output is correct |
5 |
Correct |
1374 ms |
61432 KB |
Output is correct |
6 |
Correct |
1220 ms |
55008 KB |
Output is correct |
7 |
Correct |
1112 ms |
47812 KB |
Output is correct |
8 |
Correct |
663 ms |
36604 KB |
Output is correct |
9 |
Correct |
292 ms |
29380 KB |
Output is correct |
10 |
Correct |
231 ms |
27536 KB |
Output is correct |
11 |
Correct |
275 ms |
29380 KB |
Output is correct |
12 |
Correct |
222 ms |
27416 KB |
Output is correct |
13 |
Correct |
291 ms |
29312 KB |
Output is correct |
14 |
Correct |
212 ms |
27500 KB |
Output is correct |
15 |
Correct |
1494 ms |
68768 KB |
Output is correct |
16 |
Correct |
1054 ms |
55900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
23812 KB |
Output is correct |
2 |
Correct |
25 ms |
23708 KB |
Output is correct |
3 |
Correct |
25 ms |
23776 KB |
Output is correct |
4 |
Correct |
32 ms |
23716 KB |
Output is correct |
5 |
Correct |
24 ms |
23708 KB |
Output is correct |
6 |
Correct |
23 ms |
23724 KB |
Output is correct |
7 |
Correct |
23 ms |
23816 KB |
Output is correct |
8 |
Correct |
214 ms |
30536 KB |
Output is correct |
9 |
Correct |
245 ms |
30788 KB |
Output is correct |
10 |
Correct |
397 ms |
32540 KB |
Output is correct |
11 |
Correct |
1275 ms |
50448 KB |
Output is correct |
12 |
Correct |
1364 ms |
52216 KB |
Output is correct |
13 |
Correct |
1097 ms |
47932 KB |
Output is correct |
14 |
Correct |
1434 ms |
67372 KB |
Output is correct |
15 |
Correct |
1081 ms |
54648 KB |
Output is correct |
16 |
Correct |
25 ms |
23884 KB |
Output is correct |
17 |
Correct |
24 ms |
23884 KB |
Output is correct |
18 |
Correct |
24 ms |
23884 KB |
Output is correct |
19 |
Correct |
25 ms |
23852 KB |
Output is correct |
20 |
Correct |
685 ms |
43408 KB |
Output is correct |
21 |
Correct |
1140 ms |
48112 KB |
Output is correct |
22 |
Correct |
1217 ms |
51184 KB |
Output is correct |
23 |
Correct |
1101 ms |
56004 KB |
Output is correct |
24 |
Correct |
164 ms |
30776 KB |
Output is correct |
25 |
Correct |
177 ms |
31312 KB |
Output is correct |
26 |
Correct |
183 ms |
31560 KB |
Output is correct |
27 |
Correct |
1460 ms |
68648 KB |
Output is correct |
28 |
Correct |
1073 ms |
56024 KB |
Output is correct |
29 |
Correct |
27 ms |
23884 KB |
Output is correct |
30 |
Correct |
24 ms |
23852 KB |
Output is correct |
31 |
Correct |
32 ms |
23840 KB |
Output is correct |
32 |
Correct |
24 ms |
23844 KB |
Output is correct |
33 |
Correct |
1374 ms |
61432 KB |
Output is correct |
34 |
Correct |
1220 ms |
55008 KB |
Output is correct |
35 |
Correct |
1112 ms |
47812 KB |
Output is correct |
36 |
Correct |
663 ms |
36604 KB |
Output is correct |
37 |
Correct |
292 ms |
29380 KB |
Output is correct |
38 |
Correct |
231 ms |
27536 KB |
Output is correct |
39 |
Correct |
275 ms |
29380 KB |
Output is correct |
40 |
Correct |
222 ms |
27416 KB |
Output is correct |
41 |
Correct |
291 ms |
29312 KB |
Output is correct |
42 |
Correct |
212 ms |
27500 KB |
Output is correct |
43 |
Correct |
1494 ms |
68768 KB |
Output is correct |
44 |
Correct |
1054 ms |
55900 KB |
Output is correct |
45 |
Correct |
120 ms |
27276 KB |
Output is correct |
46 |
Correct |
166 ms |
27804 KB |
Output is correct |
47 |
Correct |
622 ms |
37052 KB |
Output is correct |
48 |
Correct |
1198 ms |
50020 KB |
Output is correct |
49 |
Correct |
194 ms |
32156 KB |
Output is correct |
50 |
Correct |
193 ms |
31828 KB |
Output is correct |
51 |
Correct |
202 ms |
32296 KB |
Output is correct |
52 |
Correct |
262 ms |
33968 KB |
Output is correct |
53 |
Correct |
254 ms |
34004 KB |
Output is correct |
54 |
Correct |
259 ms |
34072 KB |
Output is correct |