#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int l,r,st,in;
};
int n,q,l[3000005],r[3000005],br=2;
string s,a[3000005];
cell p[20000005];
map<pair<int,int>,int>m;
void checkmap()
{
for(auto i=m.begin(); i!=m.end(); i++)
{
cout<<i->first.first<<" "<<i->first.second<<" "<<i->second;
cout<<endl;
}
cout<<endl;
}
void update2(int l,int r,int ql,int qr,int h,int x)
{
if(l>qr||r<qr)return;
if(l==r&&r==qr)
{
p[h].st+=x;
//cout<<l<<" "<<r<<" "<<p[h].st<<" : ";
return;
}
if(!p[h].l)
{
p[h].l=br;
p[h].r=br+1;
br+=2;
if(br>=20000000)exit(0);
}
int mi=(l+r)/2;
update2(l,mi,ql,qr,p[h].l,x);
update2(mi+1,r,ql,qr,p[h].r,x);
p[h].st=p[p[h].l].st+p[p[h].r].st;
}
void update1(int l,int r,int ql,int qr,int h,int x)
{
if(l>ql||r<ql)return;
if(!p[h].l)
{
p[h].l=br;
p[h].r=br+1;
p[h].in=br+2;
br+=3;
if(br>=20000000)exit(0);
}
if(l==r&&r==ql)
{
//cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
update2(1,n,ql,qr,p[h].in,x);
//cout<<endl;
return;
}
int mi=(l+r)/2;
update1(l,mi,ql,qr,p[h].l,x);
update1(mi+1,r,ql,qr,p[h].r,x);
//cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
update2(1,n,ql,qr,p[h].in,x);
//cout<<endl;
}
int query2(int l,int r,int ql,int qr,int h)
{
if(r<qr||!p[h].l)return 0;
if(l>=qr)
{
return p[h].st;
}
int mi=(l+r)/2;
return query2(l,mi,ql,qr,p[h].l)+query2(mi+1,r,ql,qr,p[h].r);
}
int query1(int l,int r,int ql,int qr,int h)
{
if(l>ql||!p[h].l)return 0;
if(r<=ql)
{
return query2(1,n,ql,qr,p[h].in);
}
int mi=(l+r)/2;
return query1(l,mi,ql,qr,p[h].l)+query1(mi+1,r,ql,qr,p[h].r);
}
void remov(int in,int tim)
{
pair<int,int>p;
p.first=in;
p.second=1000000000;
auto it=m.upper_bound(p);
int le,ri,st;
it--;
le=it->first.first,ri=it->first.second,st=it->second;
update1(1,n,le,ri,1,tim-st+1);
m.erase(it);
if(in-1>=le)
{
p.first=le;
p.second=in-1;
m[p]=tim+1;
}
if(in+1<=ri)
{
p.first=in+1;
p.second=ri;
m[p]=tim+1;
}
s[in-1]='0';
//checkmap();
}
void ad(int in,int tim)
{
int lp=0,rp=0;
pair<int,int>p;
if(m.size()>0)
{
p.first=in;
p.second=100000000;
auto it=m.upper_bound(p);
int le,ri,st;
if(it!=m.begin())
{
it--;
le=it->first.first,ri=it->first.second,st=it->second;
if(ri==in-1)
{
update1(1,n,le,ri,1,tim-st+1);
m.erase(it);
lp=le;
}
it++;
}
if(it!=m.end())
{
le=it->first.first,ri=it->first.second,st=it->second;
if(le==in+1)
{
update1(1,n,le,ri,1,tim-st+1);
m.erase(it);
rp=ri;
}
}
}
if(!lp)lp=in;
if(!rp)rp=in;
p.first=lp;
p.second=rp;
m[p]=tim+1;
s[in-1]='1';
}
void print(int l,int r,int tim)
{
if(m.size()==0)
{
cout<<query1(1,n,l,r,1)<<endl;
return;
}
pair<int,int>p;
p.first=l;
p.second=100000000;
auto it=m.upper_bound(p);
if(it==m.begin())
{
cout<<query1(1,n,l,r,1)<<endl;
return;
}
it--;
int le=it->first.first;
int ri=it->first.second;
if(le<=l&&ri>=r)
{
cout<<query1(1,n,l,r,1)+tim-it->second+1<<endl;
//cout<<query1(1,n,l,r,1)<<endl;
}
else cout<<query1(1,n,l,r,1)<<endl;
}
void newstart()
{
for(int i=0; i<n; i++)
{
if(s[i]=='1')ad(i+1,0);
}
}
void read()
{
cin>>n>>q>>s;
for(int i=1; i<=q; i++)
{
cin>>a[i]>>l[i];
if(a[i]=="query")cin>>r[i];
}
newstart();
for(int i=1; i<=q; i++)
{
if(a[i]=="toggle")
{
if(s[l[i]-1]=='0')ad(l[i],i);
else remov(l[i],i);
}
else
{
print(l[i],r[i]-1,i);
}
}
}
int main()
{
speed();
read();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
95832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
97956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
96596 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
96596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
96080 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
96176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
95832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
