#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
//#define int long long
const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int active=0;
int n,q;
struct fen2d{
/*
l, add at l, stop at x+1
r add at x,stop at r+1
l,t x+1,-t
x,t r+1,-t
first{
update(l,x,t)
update(l,r+1,-t)
update(x+1,x,-t)
update(x+1,r+1,t)
}*/
vector<int>element[mxn+10];
int e[mxn+10],st[mxn+10],fwk[mxn+10];
int cnt=0;
void init(){
int m=0;
active=1;
for(int i=0;i<n;i++){
st[i]=m;
sort(all(element[i]));
element[i].erase(unique(all(element[i])),element[i].end());
copy(all(element[i]),e+st[i]);
m+=element[i].size();
}
st[n]=m;
}
void update(int x,int y,int val){
if(!active){
for(;x<=n;x+=(x&-x)){
if(x==0)assert(0);
element[x-1].pb(y);
}
return;
}
for(;x<=n;x+=(x&-x)){
if(x==0)assert(0);
int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
while(k<=st[x]-st[x-1]){
//if(k==0)assert(0);
fwk[st[x-1]+k-1]+=val;
k+=(k&-k);
}
}
}
int qry(int x,int y){
int sum=0;
for(;x>0;x-=(x&-x)){
if(x==0)assert(0);
int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
while(k){
// if(k==0)assert(0);
sum+=fwk[st[x-1]+k-1];
k-=(k&-k);
}
}
return sum;
}
void addrange(int l,int r,int x,int val){
update(l,x,val);
update(l,r+1,-val);
update(x+1,x,-val);
update(x+1,r+1,val);
}
}t;
struct seg{
int v[2*mxn+10];
void update(int pos,int val){
pos+=n;
v[pos]=val;
for(int i=pos;i>0;i>>=1)v[i>>1]=(v[i]&v[i^1]);
}
int qry(int l,int r){
int ans=1;
for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
if(l&1)ans=(ans&v[l++]);
if(!(r&1))ans=(ans&v[r--]);
}
return ans;
}
}t2;
int getl(int x){
int l=1,r=x;
int ans=x;
while(l<=r){
int mid=l+(r-l)/2;
if(t2.qry(mid,x))r=mid-1,ans=min(ans,mid);
else l=mid+1;
}
return ans;
}
int getr(int x){
int l=x,r=n;
int ans=x;
while(l<=r){
int mid=l+(r-l)/2;
if(t2.qry(x,mid))l=mid+1,ans=max(ans,mid);
else r=mid-1;
}
return ans;
}
int32_t main(){
fastio
cin>>n>>q;
string a;cin>>a;
a='b'+a;
string keep=a;
for(int i=1;i<=n;i++)if(a[i]=='1')t2.update(i,1);
vector<pair<int,pii>>qry;
for(int i=0;i<q;i++){
string ty;cin>>ty;
if(ty=="query"){
int l,r;cin>>l>>r;
r--;
qry.pb({1,{l,r}});
}
else{
int x;cin>>x;
qry.pb({2,{x,-1}});
if(a[x]=='1'){
t.addrange(getl(x),getr(x),x,0);
a[x]='0';
t2.update(x,0);
}
else{
a[x]='1';
t2.update(x,1);
t.addrange(getl(x),getr(x),x,0);
}
}
}
for(int i=1;i<=n;i++)t2.update(i,(keep[i]=='1'));
t.init();
a=keep;
for(int i=0;i<q;i++){
if(qry[i].f==1){
int ans=t.qry(qry[i].s.f,qry[i].s.s);
if(t2.qry(qry[i].s.f,qry[i].s.s))ans+=(i+1);
cout<<ans<<'\n';
}
else{
int x=qry[i].s.f;
if(a[x]=='1'){
t.addrange(getl(x),getr(x),x,i+1);
a[x]='0';
t2.update(x,0);
}
else{
a[x]='1';
t2.update(x,1);
t.addrange(getl(x),getr(x),x,-i-1);
}
}
}
/*
qry l->r
turn on at x ->lf,ri of continuos segment then every lf<=l<=x,x<=r<=ri will start -> -t
turn of at x->lf,ri of contiuos segment then every lf<=l<=x,x<=r<=ri will end -> +t
qry l,r->if l,r still on then ans=l,r+t->to end else ans=l,r
update can be done by 2d offline fenwick
->sort all l,r
each l is first dimension
second dimension is different for each l
finding lf and ri can be dones by bnary search and seg tree?
*/
}
Compilation message
street_lamps.cpp:34:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
34 | const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
| ^~~~
street_lamps.cpp:34:49: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
34 | const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
| ^~~~~
street_lamps.cpp: In function 'void setIO(std::string)':
street_lamps.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
18780 KB |
Output is correct |
3 |
Correct |
4 ms |
18780 KB |
Output is correct |
4 |
Correct |
4 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
233 ms |
33640 KB |
Output is correct |
2 |
Correct |
350 ms |
35096 KB |
Output is correct |
3 |
Correct |
702 ms |
40240 KB |
Output is correct |
4 |
Runtime error |
706 ms |
125300 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
19032 KB |
Output is correct |
2 |
Correct |
6 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
16732 KB |
Output is correct |
4 |
Correct |
4 ms |
16732 KB |
Output is correct |
5 |
Runtime error |
1143 ms |
170648 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18780 KB |
Output is correct |
2 |
Correct |
5 ms |
18780 KB |
Output is correct |
3 |
Correct |
6 ms |
19036 KB |
Output is correct |
4 |
Correct |
6 ms |
19036 KB |
Output is correct |
5 |
Correct |
196 ms |
28896 KB |
Output is correct |
6 |
Runtime error |
484 ms |
95744 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
18780 KB |
Output is correct |
3 |
Correct |
4 ms |
18780 KB |
Output is correct |
4 |
Correct |
4 ms |
18780 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
3 ms |
16732 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
233 ms |
33640 KB |
Output is correct |
9 |
Correct |
350 ms |
35096 KB |
Output is correct |
10 |
Correct |
702 ms |
40240 KB |
Output is correct |
11 |
Runtime error |
706 ms |
125300 KB |
Execution killed with signal 11 |
12 |
Halted |
0 ms |
0 KB |
- |