#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define eb emplace_back
#define mp make_pair
typedef pair<int,int> pii;
#define f first
#define s second
#ifdef local
#define debug(x,label) cerr<<"DEBUG "<<label<<" "<<x<<'\n';
#else
#define debug(x,label);
#endif
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
//const int mod=1000000007 or 998244353;
#define ls(x) (x&(-x))
int n,q,ft[300005];
int ans[300005],curr=0;
/*map<int,int> ft[300005];
void update(int a,int b,int upd){b++;
//cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
for(;a<=n;a+=ls(a)){
for(int x=b;x<=n;x+=ls(x)){
if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
else ft[a][x]+=upd;
}
}
}
int query(int a,int b){b++;
int ans=0;
for(;a;a-=ls(a)){
for(int x=b;x;x-=ls(x)){
//if(ft[a].find(x)==ft[a].end())continue;
ans+=ft[a][x];
}
}
return ans;
}*/ //sparse 2d fenwick TLE :(
void upddd(int p,int v){
debug(p,"update p")
for(;p<=n;p+=ls(p))ft[p]+=v;
}
int query(int p){
debug(p,"query p")
int ansss=0;
for(;p;p-=ls(p))ansss+=ft[p];
return ansss;
}
struct node{
int s,e;
vector<pair<pii,int> > v;//type,b, update value OR ans index...
node *l,*r;
node(int ss,int ee){
s=ss;e=ee;
if(s==e)l=r=NULL;
else{
l=new node(s,(s+e)/2);r=new node((s+e)/2+1,e);
}
}
void upd(int a,int b,int c,bool upda=1){//1 to a...
if(s==1 && e==n){
b++;
//if(upda)cout<<a<<' '<<b<<' '<<'\n';
}
if(upda==false) goto end;
if(a<=s){
if(upda)v.eb(mp(1,b),c);//update
else v.eb(mp(2,b),c);//query
return;
}
if(a<=(s+e)/2)l->upd(a,b,c,upda);
r->upd(a,b,c,upda);
return;
end:;
if(a>=e){
if(upda)v.eb(mp(1,b),c);//update
else v.eb(mp(2,b),c);//query
return;
}
if(a>(s+e)/2)r->upd(a,b,c,upda);
l->upd(a,b,c,upda);
}
void dfs(){
for(auto xx:v){
if(xx.f.f==1){
upddd(xx.f.s,xx.s);
}else ans[xx.s]+=query(xx.f.s);
}
for(auto xx:v){
if(xx.f.f==1)upddd(xx.f.s,-xx.s);//reset ft
}
if(s==e)return;
l->dfs();r->dfs();
}
} *root;
#define update root->upd
bool lam[300005];
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int prev=0,a,b,c,d;
cin>>n>>q;
root=new node(1,n);
string s;
cin>>s;
set<pair<pii,int> > cur;//"cur ranges"
set<pair<pii,int> >::iterator it;
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(prev<=i-1){
cur.insert(mp(mp(prev+1,i),0));
}
prev=i+1;
}
lam[i+1]=(s[i]=='1');
}
if(prev<=n-1){
cur.insert(mp(mp(prev+1,n),0));
}
for(int i=1;i<=q;i++){
cin>>s;
if(s[0]=='t'){
cin>>a;
if(lam[a]){
it=--cur.upper_bound(mp(mp(a,INT_MAX),-1));
b=it->f.f;c=it->f.s;//range b to c...
root->upd(b,n-c,i-it->s);
cur.erase(it);
if(b<a)cur.insert(mp(mp(b,a-1),i));
if(a<c)cur.insert(mp(mp(a+1,c),i));
}else{
b=c=a;
if(lam[a-1]){
it=--cur.upper_bound(mp(mp(a-1,INT_MAX),-1));
b=it->f.f;
root->upd(it->f.f,n-it->f.s,i-it->s);
cur.erase(it);
}
if(lam[a+1]){
it=--cur.upper_bound(mp(mp(a+1,INT_MAX),-1));
c=it->f.s;
root->upd(it->f.f,n-it->f.s,i-it->s);
cur.erase(it);
}
cur.insert(mp(mp(b,c),i));
}
lam[a]^=1;
}else{
ans[curr]=0;
cin>>a>>b;b--;
it=cur.upper_bound(mp(mp(a,INT_MAX),-1));
if(it!=cur.begin()){
it--;
if(it->f.f<=a && b<=it->f.s){
ans[curr]+=(i-it->s);
}
}
root->upd(a,n-b,curr,0);
//ans+=query(a,n-b);//if first index >=a, then n-first index<=n-a
//cout<<ans<<'\n';
curr++;
}
}
//for(int i=0;i<curr;i++)cout<<ans[i]<<' ';cout<<'\n';
debug('x',"dfsing")
root->dfs();
for(int i=0;i<curr;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
Compilation message
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:107:20: warning: unused variable 'd' [-Wunused-variable]
107 | int prev=0,a,b,c,d;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
167 ms |
19484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
