#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define doi(x) cout << #x << " = " << x << '\n'
using namespace std;
#define N 15000100
#define mid ((rl+rr)>>1)
int root[300100], n, q, on[300100], sum[N], ch[N][2], cnt;
void upd1(int &rt,int rl,int rr,int x,int w){
if (!rt) rt=++cnt;sum[rt]+=w;
if (rl==rr) return;
(mid>=x?upd1(ch[rt][0],rl,mid,x,w):upd1(ch[rt][1],mid+1,rr,x,w));
}
int query1(int rt,int rl,int rr,int l,int r){
if (!rt||rl>r||rr<l) return 0;
if (rl>=l&&rr<=r) return sum[rt];
return query1(ch[rt][0],rl,mid,l,r)+query1(ch[rt][1],mid+1,rr,l,r);
}
inline void upd2(int x,int r,int w){
while(x<=n+1)
upd1(root[x],1,n+1,r,w),x+=x&-x;
}
inline int query2(int x,int y){
int ans=0;
while(x)
ans+=query1(root[x],1,n+1,1,y),x-=x&-x;
return ans;
}
inline void upd3(int x1, int y1, int x2, int y2, int W) {
upd2(x1, y1, W);
query2(5,6);
upd2(x1, y2 + 1, -W);
upd2(x2 + 1, y1, -W);
upd2(x2 + 1, y2 + 1, W);
}
struct seg{
int l, r;
};
inline bool operator < (seg a,seg b){
return a.r<b.r;
}
set<seg> st;
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
n++;
string str;
cin >> str;
for (int i=1;i<=n;i++){
st.insert((seg){i,i});
}
for (int i=1;i<n;i++){
on[i]=(str[i-1]-48);
if (on[i]){
auto it = --st.lower_bound((seg){0,i+1});
int l = it->l;
st.erase(it);st.erase((seg){i+1,i+1});
st.insert((seg){l,i+1});
}
}
for(auto i: st)
if(on[i.l])
upd3(i.l,i.l,i.r,i.r,q);
for (int t=1;t<=q;t++){
cin >> str;
if (str=="query"){
int x, y;
cin >> x >> y;
int ans=query2(x,y);
x=(*(st.lower_bound((seg){0,x}))).l;
y=(*(st.lower_bound((seg){0,y}))).l;
cout << (ans-(q-t)*(x==y)) << '\n';
} else {
int x;
cin >> x;
auto it=st.lower_bound((seg){0,x});
int lb1=it->l,rb1=x;
if(!on[x]) it++;
int lb2=x+1,rb2=it->r;
upd3(lb1,lb2,rb1,rb2,(on[x]?t-q:q-t));
if(on[x]) {
st.erase((seg){lb1,rb2});
st.insert((seg){lb1,rb1});
st.insert((seg){lb2,rb2});
} else {
st.erase((seg){lb1,rb1});
st.erase((seg){lb2,rb2});
st.insert((seg){lb1,rb2});
}
on[x]^=1;
}
}
}
Compilation message
strange_device.cpp: In function 'void upd1(int&, int, int, int, int)':
strange_device.cpp:9:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
9 | if (!rt) rt=++cnt;sum[rt]+=w;
| ^~
strange_device.cpp:9:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
9 | if (!rt) rt=++cnt;sum[rt]+=w;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
