#include <bits/stdc++.h>
using namespace std;
const int maxn=4*1e5;
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)return 0;
if(ql<=l&&r<=qr)return v[i].val;
if(v[i].l==-1)makeLeft(i);
if(v[i].r==-1)makeRight(i);
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;
}
if(v[i].l==-1)makeLeft(i);
if(v[i].r==-1)makeRight(i);
int lf=v[i].l,rt=v[i].r;
int m=(l+r)/2;
if(idx<=m)update(lf,l,m,idx,val);
else update(rt,m+1,r,idx,val);
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;
}
if(v[i].l==-1)makeLeft(i);
if(v[i].r==-1)makeRight(i);
int lf=v[i].l,rt=v[i].r;
//cout<<lf<<" "<<rt<<endl;
int m=(l+r)/2;
if(idx<=m)update(lf,l,m,idx,val,other);
else update(rt,m+1,r,idx,val,other);
int curr=v[lf].s.query(0,1,n,other,other)+v[rt].s.query(0,1,n,other,other);
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)return 0;
if(ql<=l&&r<=qr)return v[i].s.query(0,1,n,h1,h2);
if(v[i].l==-1)makeLeft(i);
if(v[i].r==-1)makeRight(i);
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];
void read()
{
cin>>n>>q;
int bg=-1;
for(int i=1; i<=n; i++)
{
cin>>c[i];
if(c[i]=='0')
{
if(bg!=-1)
{
itv.insert(bg);
r[bg]=i-1;
tmr[bg]=0;
}
bg=-1;
}
else
{
if(bg==-1)bg=i;
}
}
if(bg!=-1)
{
itv.insert(bg);
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;
if(c[x]=='0')
{
c[x]='1';
if(c[x-1]=='0'&&c[x+1]=='0')
{
itv.insert(x);
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;
itv.erase(x+1);
itv.insert(x);
}
else if(c[x+1]=='0')
{
auto it=itv.upper_bound(x);
it--;
int lf=*it;
s.update(0,1,n,lf,i-tmr[lf],x-1);
r[lf]=x;
tmr[lf]=i;
}
else
{
//cout<<"in"<<endl;
auto it=itv.upper_bound(x);
it--;
int lf=*it;
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;
itv.erase(x+1);
}
}
else
{
c[x]='0';
auto it=itv.upper_bound(x);
it--;
s.update(0,1,n,*it,i-tmr[*it],r[*it]);
if(c[x-1]=='0'&&c[x+1]=='0')
{
itv.erase(x);
}
else if(c[x-1]=='0')
{
itv.erase(x);
itv.insert(x+1);
tmr[x+1]=i;
r[x+1]=r[x];
}
else if(c[x+1]=='0')
{
tmr[*it]=i;
r[*it]=x-1;
}
else
{
tmr[*it]=tmr[x+1]=i;
r[x+1]=r[*it];
r[*it]=x-1;
itv.insert(x+1);
}
}
/*for(auto it=itv.begin();it!=itv.end();it++)
{
cout<<*it<<" "<<r[*it]<<" "<<tmr[*it]<<endl;
}*/
}
if(tp=="query")
{
cin>>x>>y;
int add=0;
if(itv.size())
{
auto ch=itv.rbegin();
if(*ch<=x)
{
if(r[*ch]>=y-1)
add=i-tmr[*ch];
}
else
{
auto it=itv.upper_bound(x);
it--;
if(*itv.begin()<=x&&r[*it]>=y-1)
add=i-tmr[*it];
}
}
cout<<add+s.query(0,1,n,1,x,y-1,n)<<endl;
}
/*for(int j=1;j<=n;j++)
cout<<c[j];
cout<<endl;*/
}
}
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 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
446 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
580 ms |
3924 KB |
Output is correct |
| 3 |
Correct |
1148 ms |
14816 KB |
Output is correct |
| 4 |
Runtime error |
3885 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4184 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 5 |
Runtime error |
3034 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3928 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3676 KB |
Output is correct |
| 5 |
Runtime error |
2064 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
446 ms |
3412 KB |
Output is correct |
| 9 |
Correct |
580 ms |
3924 KB |
Output is correct |
| 10 |
Correct |
1148 ms |
14816 KB |
Output is correct |
| 11 |
Runtime error |
3885 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
