#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 fakeUpdate(int x, int y){
for(; x < N; x += x & -x)
nodes[x].push_back(y);
}
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;
}
}
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){
bit.fakeQuery(queries[i].a, queries[i].b);
} 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){
bit.fakeUpdate(l + 1, l + 1);
bit.fakeUpdate(l + 1, pos);
}
if (pos + 1 <= r - 1)
bit.fakeUpdate(pos + 1, pos + 1);
bit.fakeUpdate(pos + 1, r);
cur[pos] = '1';
} else {
auto it = empPos.lower_bound(pos);
int r = *it;
int l = *(--it);
if (l + 1 <= r - 1)
bit.fakeUpdate(l + 1, r - 1);
empPos.insert(pos);
cur[pos] = '0';
}
}
}
bit.normalize();
cur = s;
empPos.clear();
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;
}
last[pos] = i;
cur[pos] = '1';
} 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;
}
empPos.insert(pos);
cur[pos] = '0';
}
}
}
return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:93:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
93 | if (pos + 1 <= r - 1)
| ^~
street_lamps.cpp:95:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
95 | bit.fakeUpdate(pos + 1, r);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
584 ms |
50968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
24140 KB |
Output is correct |
| 2 |
Correct |
32 ms |
24120 KB |
Output is correct |
| 3 |
Correct |
28 ms |
23920 KB |
Output is correct |
| 4 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
2798 ms |
104476 KB |
Output is correct |
| 6 |
Correct |
2662 ms |
98116 KB |
Output is correct |
| 7 |
Correct |
2189 ms |
84944 KB |
Output is correct |
| 8 |
Correct |
1068 ms |
61972 KB |
Output is correct |
| 9 |
Correct |
169 ms |
33544 KB |
Output is correct |
| 10 |
Correct |
176 ms |
34504 KB |
Output is correct |
| 11 |
Correct |
208 ms |
34784 KB |
Output is correct |
| 12 |
Correct |
1487 ms |
74800 KB |
Output is correct |
| 13 |
Correct |
1053 ms |
61988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
23876 KB |
Output is correct |
| 2 |
Correct |
28 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
28 ms |
24012 KB |
Output is correct |
| 4 |
Correct |
29 ms |
24016 KB |
Output is correct |
| 5 |
Correct |
1377 ms |
67744 KB |
Output is correct |
| 6 |
Correct |
1692 ms |
72744 KB |
Output is correct |
| 7 |
Correct |
2060 ms |
75592 KB |
Output is correct |
| 8 |
Correct |
2603 ms |
76584 KB |
Output is correct |
| 9 |
Incorrect |
843 ms |
56864 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
