#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n, q;
bool status[300005];
struct segTree {
struct node {
int val;
node *left, *right;
node() {
val = 0;
left = right = NULL;
}
};
node *root;
segTree() {
root = new node();
}
void update(node *cur, int l, int r, int wl, int wr, int v) {
if(wl<=l && wr>=r) {
cur->val += v;
return;
}
int m = (l+r)/2;
if(wl<=m) {
if(!cur->left) cur->left = new node();
update(cur->left, l, m, wl, wr, v);
}
if(wr>m) {
if(!cur->right) cur->right = new node();
update(cur->right, m+1, r, wl, wr, v);
}
}
void update(int wl, int wr, int v) {update(root, 0, n, wl, wr, v);}
int query(node *cur, int l, int r, int x) {
int ret = cur->val;
if(l==r) return ret;
int m = (l+r)/2;
if(x<=m && cur->left) return ret+query(cur->left, l, m, x);
if(x>m && cur->right) return ret+query(cur->right, m+1, r, x);
return ret;
}
int query(int x) {return query(root, 0, n, x);}
};
struct segTree2 {
struct node2 {
segTree *tree;
node2 *left, *right;
node2() {
tree = new segTree();
left = right = NULL;
}
};
node2 *root;
segTree2() {
root = new node2();
}
void update(node2 *cur, int l, int r, int wl, int wr, int wll, int wrr, int v) {
if(wl<=l && wr>=r) {
cur->tree->update(wll, wrr, v);
return;
}
int m = (l+r)/2;
if(wl<=m) {
if(!cur->left) cur->left = new node2();
update(cur->left, l, m, wl, wr, wll, wrr, v);
}
if(wr>m) {
if(!cur->right) cur->right = new node2();
update(cur->right, m+1, r, wl, wr, wll, wrr, v);
}
}
void update(int wl, int wr, int wll, int wrr, int v) {update(root, 0, n, wl, wr, wll, wrr, v);}
int query(node2 *cur, int l, int r, int x, int xx) {
int ret = cur->tree->query(xx);
if(l==r) return ret;
int m = (l+r)/2;
if(x<=m && cur->left) return ret+query(cur->left, l, m, x, xx);
if(x>m && cur->right) return ret+query(cur->right, m+1, r, x, xx);
return ret;
}
int query(int x, int xx) {return query(root, 0, n, x, xx);}
} *seg;
set<pii> range;
pii func01(int x) {
int l = x, r = x;
auto it = upper_bound(range.begin(), range.end(), make_pair(x, x));
if(it!=range.end() && it->first==x+1) {
r = it->second;
range.erase(it);
}
it = lower_bound(range.begin(), range.end(), make_pair(x, x));
if(it!=range.begin() && prev(it)->second==x-1) {
it--;
l = it->first;
range.erase(it);
}
range.insert({l, r});
return {l, r};
}
pii func10(int x) {
auto it = upper_bound(range.begin(), range.end(), make_pair(x, (int)1e9));
it--;
auto [l, r] = *it;
range.erase(it);
if(l<x) range.insert({l, x-1});
if(r>x) range.insert({x+1, r});
return {l, r};
}
bool inrange(int l, int r) {
auto it = upper_bound(range.begin(), range.end(), make_pair(l, (int)1e9));
if(it==range.begin()) return 0;
it--;
return it->second>=r;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin>>n>>q;
string s;
cin>>s;
int st = -1;
for(int i=1;i<=n;i++) {
status[i] = s[i-1]-'0';
if(status[i]==0 && st!=-1) {
range.insert({st, i-1});
st = -1;
} else if(status[i]==1 && st==-1) {
st = i;
}
}
seg = new segTree2();
if(st!=-1) range.insert({st, n});
for(int i=1;i<=q;i++) {
cin>>s;
if(s[0]=='q') {
int a, b;
cin>>a>>b;
int ans = 0;
if(inrange(a, b-1)) ans = i;
ans += seg->query(a, b-1);
cout<<ans<<'\n';
} else {
int a;
cin>>a;
if(status[a]==0) {
auto [l, r] = func01(a);
seg->update(l, a, a, r, -i);
} else {
auto [l, r] = func10(a);
seg->update(l, a, a, r, i);
}
status[a] = !status[a];
}
}
}
/*
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 'std::pair<int, int> func10(int)':
street_lamps.cpp:109:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | auto [l, r] = *it;
| ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:153:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | auto [l, r] = func01(a);
| ^
street_lamps.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
156 | auto [l, r] = func10(a);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
388 ms |
5316 KB |
Output is correct |
| 3 |
Execution timed out |
5043 ms |
11772 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Correct |
3 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
5045 ms |
13680 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
4 ms |
604 KB |
Output is correct |
| 4 |
Correct |
5 ms |
860 KB |
Output is correct |
| 5 |
Execution timed out |
5034 ms |
9956 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
224 ms |
4820 KB |
Output is correct |
| 9 |
Correct |
388 ms |
5316 KB |
Output is correct |
| 10 |
Execution timed out |
5043 ms |
11772 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
