#include <bits/stdc++.h>
using namespace std;
const int maxn=3*1e5+5;
int n,q;
struct node
{
int l,r;
int val;
node() {}
node(int _l,int _r,int v)
{
l=_l;
r=_r;
val=v;
}
};
struct segmentTree
{
vector<node> v= {{-1,-1,0}};
void makeLeft(int i)
{
v[i].l=v.size();
v.push_back({-1,-1,0});
}
void makeRight(int i)
{
v[i].r=v.size();
v.push_back({-1,-1,0});
}
int query(int i,int l,int r,int ql,int qr)
{
if(ql>qr||i==-1)return 0;
if(ql<=l&&r<=qr)return v[i].val;
int m=(l+r)/2;
return query(v[i].l,l,m,ql,min(qr,m))+query(v[i].r,m+1,r,max(ql,m+1),qr);
}
void update(int i,int l,int r,int idx,int val)
{
//cout<<l<<" nml "<<r<<endl;
if(l==r)
{
if(val>0)v[i].val+=val;
else v[i].val=-val;
return;
}
int lf=v[i].l,rt=v[i].r;
int m=(l+r)/2;
if(idx<=m)
{
if(lf==-1)makeLeft(i);
lf=v[i].l;
update(lf,l,m,idx,val);
}
else
{
if(rt==-1)makeRight(i);
rt=v[i].r;
update(rt,m+1,r,idx,val);
}
if(lf==-1)v[i].val=v[rt].val;
else if(rt==-1)v[i].val=v[lf].val;
else v[i].val=v[lf].val+v[rt].val;
}
};
struct twoDnode
{
segmentTree s;
int l,r;
twoDnode() {}
twoDnode(segmentTree _s,int _l,int _r)
{
s=_s;
l=_l;
r=_r;
}
};
struct twoD
{
segmentTree g;
vector<twoDnode> v= {{g,-1,-1}};
void makeLeft(int i)
{
v[i].l=v.size();
v.push_back({g,-1,-1});
}
void makeRight(int i)
{
v[i].r=v.size();
v.push_back({g,-1,-1});
}
void update(int i,int l,int r,int idx,int val,int other)
{
//cout<<l<<" 2d "<<r<<endl;
if(l==r)
{
v[i].s.update(0,1,n,other,val);
return;
}
int lf=v[i].l,rt=v[i].r;
//cout<<lf<<" "<<rt<<endl;
int m=(l+r)/2;
if(idx<=m)
{
if(lf==-1)makeLeft(i);
lf=v[i].l;
update(lf,l,m,idx,val,other);
}
else
{
if(rt==-1)makeRight(i);
rt=v[i].r;
update(rt,m+1,r,idx,val,other);
}
int val1=0;
int val2=0;
if(lf!=-1)
val1=v[lf].s.query(0,1,n,other,other);
if(rt!=-1)
val2=v[rt].s.query(0,1,n,other,other);
int curr=val1+val2;
v[i].s.update(0,1,n,other,-curr);
}
int query(int i,int l,int r,int ql,int qr,int h1,int h2)
{
if(ql>qr||i==-1)return 0;
if(ql<=l&&r<=qr)return v[i].s.query(0,1,n,h1,h2);
int lf=v[i].l,rt=v[i].r;
int m=(l+r)/2;
return query(lf,l,m,ql,min(qr,m),h1,h2)+query(rt,m+1,r,max(m+1,ql),qr,h1,h2);
}
};
twoD s;
set<int> itv;
int l[maxn],r[maxn],tmr[maxn];
char c[maxn];
int t[4*maxn];
void update(int i,int l,int r,int idx,int val)
{
if(l==r)
{
if(val==0)t[i]=l;
else t[i]=n+1;
return;
}
int m=(l+r)/2;
if(idx<=m)update(i*2,l,m,idx,val);
else update(i*2+1,m+1,r,idx,val);
t[i]=min(t[i*2],t[i*2+1]);
}
int previous(int i,int l,int r,int idx)
{
//cout<<l<<" "<<r<<" "<<t[i]<<endl;
if(l==r)return l;
int m=(l+r)/2;
if(t[i*2+1]<=idx)return previous(i*2+1,m+1,r,idx);
else return previous(i*2,l,m,idx);
}
void read()
{
cin>>n>>q;
for(int i=1;i<=4*n;i++)
t[i]=n+1;
int bg=-1;
for(int i=1; i<=n; i++)
{
cin>>c[i];
if(c[i]=='0')
{
if(bg!=-1)
{
r[bg]=i-1;
tmr[bg]=0;
}
bg=-1;
}
else
{
update(1,0,n+1,i,1);
if(bg==-1)bg=i;
}
}
if(bg!=-1)
{
r[bg]=n;
tmr[bg]=0;
}
}
void solve()
{
c[0]=c[n+1]='0';
for(int i=1; i<=q; i++)
{
string tp;
int x,y;
cin>>tp;
if(tp=="toggle")
{
cin>>x;
int prv=previous(0,0,n+1,x)+1;
//cout<<prv<<endl;
if(c[x]=='0')
{
c[x]='1';
update(1,0,n+1,x,1);
if(c[x-1]=='0'&&c[x+1]=='0')
{
r[x]=x;
tmr[x]=i;
}
else if(c[x-1]=='0')
{
s.update(0,1,n,x+1,i-tmr[x+1],r[x+1]);
r[x]=r[x+1];
tmr[x]=i;
}
else if(c[x+1]=='0')
{
int lf=prv;
s.update(0,1,n,lf,i-tmr[lf],x-1);
r[lf]=x;
tmr[lf]=i;
}
else
{
//cout<<"in"<<endl;
int lf=prv;
s.update(0,1,n,lf,i-tmr[lf],x-1);
s.update(0,1,n,x+1,i-tmr[x+1],r[x+1]);
r[lf]=r[x+1];
tmr[lf]=i;
//cout<<lf<<" "<<r[x+1]<<endl;
}
}
else
{
c[x]='0';
update(1,0,n+1,x,0);
s.update(0,1,n,prv,i-tmr[prv],r[prv]);
if(c[x-1]=='0'&&c[x+1]=='0')
{
;
}
else if(c[x-1]=='0')
{
tmr[x+1]=i;
r[x+1]=r[x];
}
else if(c[x+1]=='0')
{
tmr[prv]=i;
r[prv]=x-1;
}
else
{
tmr[prv]=tmr[x+1]=i;
r[x+1]=r[prv];
r[prv]=x-1;
itv.insert(x+1);
}
}
}
if(tp=="query")
{
cin>>x>>y;
int add=0;
int prv=previous(1,0,n+1,x)+1;
if(prv<=x&&r[prv]>=y-1)add=i-tmr[prv];
cout<<add+s.query(0,1,n,1,x,y-1,n)<<'\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
solve();
return 0;
}
/*
7 10
0110101
query 2 3
toggle 2
query 2 3
toggle 2
query 2 3
toggle 6
query 5 7
query 6 6
toggle 5
query 5 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
230 ms |
6740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
