#include <bits/stdc++.h>
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
struct BIT{
vector<int> dat;
void build(int n){
dat.resize(n+1,0);
}
void add(int k,int x){
for(++k;k<dat.size();k+=k&-k){
dat[k]+=x;
}
}
int get(int k){
int res=0;
for(++k;k>0;k-=k&-k){
res+=dat[k];
}
return res;
}
};
struct Segtree{
int n;
vector<BIT> dat;
vector<vector<int>> ds,ls,rs;
Segtree(int n_){
n=1;
while(n<n_)n<<=1;
ds.resize(2*n);
ls.resize(2*n);
rs.resize(2*n);
dat.resize(2*n);
}
void preupd(int x,int y){
ds[x+n].push_back(y);
}
void build(){
for(int k=2*n-1;k>=n;k--){
sort(all(ds[k]));
ds[k].erase(unique(all(ds[k])),ds[k].end());
}
for(int k=n-1;k>0;k--){
ds[k].resize(ds[k<<1].size()+ds[k<<1|1].size());
merge(all(ds[k<<1]),all(ds[k<<1|1]),ds[k].begin());
ds[k].erase(unique(all(ds[k])),ds[k].end());
ls[k].resize(ds[k].size()+1);
rs[k].resize(ds[k].size()+1);
int t1=0,t2=0;
for(int i=0;i<ds[k].size();i++){
while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
ls[k][i]=t1;
rs[k][i]=t2;
}
ls[k][ds[k].size()]=ds[k<<1].size();
rs[k][ds[k].size()]=ds[k<<1|1].size();
}
for(int k=0;k<2*n-1;k++){
dat[k].build(ds[k].size());
}
}
void upd(int x,int y,int z){
y=lower_bound(all(ds[1]),y)-ds[1].begin();
int k=x+n;
dat[k].add(y,z);
k>>=1;
while(k>0){
dat[k].add(y,z);
k>>=1;
}
}
int get(int a,int b,int x,int y,int k,int l,int r){
if(b<=l||r<=a){
return 0;
}
if(a<=l&&r<=b){
return dat[k].get(y)-dat[k].get(x-1);
}
return get(a,b,ls[k][x],ls[k][y],k<<1,l,(l+r)>>1)+
get(a,b,rs[k][x],rs[k][y],k<<1|1,(l+r)>>1,r);
}
inline int get(int a,int b,int x,int y){
x=lower_bound(all(ds[1]),x)-ds[1].begin();
y=lower_bound(all(ds[1]),y)-ds[1].begin();
return get(a,b,x,y,1,0,n);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;cin>>n>>q;
string str;cin>>str;
int b=-1;
Segtree seg(n+10);
set<pair<P,int>> st;
vector<P> vi;
for(int i=0;i<n;i++){
if(str[i]=='1'){
if(b==-1){
b=i;
}
}else{
if(b!=-1){
st.insert(mp(P(b,i-1),-1));
seg.preupd(b,i-1);
b=-1;
}
}
}
if(b!=-1){
st.insert(mp(P(b,n-1),-1));
seg.preupd(b,n-1);
}
vector<vector<pair<P,int>>> vs(q);
vector<int> res(q),aa(q,-1),bb(q);
for(int i=0;i<q;i++){
string t;cin>>t;
if(t=="toggle"){
int a;cin>>a;--a;
auto add=[&](pair<P,int> p){
st.erase(p);
seg.preupd(p.first.first,p.first.second);
vs[i].emplace_back(p.first,p.second);
};
auto ins=[&](pair<P,int> p){
if(p.first.first<=p.first.second){
st.insert(p);
}
};
if(str[a]=='0'){
str[a]='1';
pair<P,int> to=mp(P(a,a),i);
if(st.empty()){
ins(to);
continue;
}
auto ir=st.lower_bound(to);
if(ir!=st.end()&&(*ir).first.first==a+1){
to.first.second=(*ir).first.second;
add(*ir);
}
auto il=st.lower_bound(to);
if(il!=st.begin()){
--il;
if((*il).first.second==a-1){
to.first.first=(*il).first.first;
add(*il);
}
}
ins(to);
}else{
str[a]='0';
auto it=prev(st.lower_bound(mp(P(a+1,-1),-1)));
pair<P,int> p=(*it);
add(*it);
ins(mp(P(p.first.first,a-1),i));
ins(mp(P(a+1,p.first.second),i));
}
}else{
int a,b;cin>>a>>b;--a;--b;--b;
aa[i]=a,bb[i]=b;
seg.preupd(0,a+1);
seg.preupd(bb[i],n);
auto it=st.lower_bound(mp(P(a+1,-1),-1));
if(!st.empty()&&it!=st.begin()){
--it;
if((*it).first.first<=a&&b<=(*it).first.second){
res[i]+=i-(*it).second;
}
}
}
}
seg.build();
for(int i=0;i<q;i++){
if(aa[i]==-1){
for(auto &e:vs[i]){
seg.upd(e.first.first,e.first.second,i-e.second);
}
}else{
res[i]+=seg.get(0,aa[i]+1,bb[i],n);
cout<<res[i]<<'\n';
}
}
}
Compilation message
street_lamps.cpp: In member function 'void BIT::add(int, int)':
street_lamps.cpp:14:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(++k;k<dat.size();k+=k&-k){
~^~~~~~~~~~~
street_lamps.cpp: In member function 'void Segtree::build()':
street_lamps.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ds[k].size();i++){
~^~~~~~~~~~~~~
street_lamps.cpp:54:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
21240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
