#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct off2dseg
{
struct BIT
{
vector<ll> bit;
void upd(ll pos,ll val)
{
while(pos<bit.size())
{
bit[pos]+=val;
pos+=pos&(-pos);
}
}
ll get(ll i)
{
ll ans=0;
while(i>0)
{
ans+=bit[i];
i-=i&(-i);
}
return ans;
}
}bit[4*maxN];
vector<ll>vec[4*maxN];
void fupdate(ll x1,ll y1,ll x2,ll y2,ll id=1,ll l=1,ll r=n)
{
if(x2<l||r<x1) return;
if(x1<=l&&r<=x2)
{
vec[id].pb(y1);
vec[id].pb(y2+1);
return;
}
ll mid=l+r>>1;
fupdate(x1,y1,x2,y2,id*2,l,mid);
fupdate(x1,y1,x2,y2,id*2+1,mid+1,r);
}
void build()
{
for(int i=1;i<=4*n;i++)
{
sort(vec[i].begin(),vec[i].end());
bit[i].bit.resize(vec[i].size()+1);
}
}
void update(ll x1,ll y1,ll x2,ll y2,ll v,ll id=1,ll l=1,ll r=n)
{
if(x2<l||r<x1) return;
if(x1<=l&&r<=x2)
{
y1=lower_bound(vec[id].begin(),vec[id].end(),y1)-vec[id].begin()+1;
y2=lower_bound(vec[id].begin(),vec[id].end(),y2+1)-vec[id].begin()+1;
bit[id].upd(y1,v);
bit[id].upd(y2,-v);
return;
}
ll mid=l+r>>1;
update(x1,y1,x2,y2,v,id*2,l,mid);
update(x1,y1,x2,y2,v,id*2+1,mid+1,r);
}
ll get(ll x,ll y,ll id=1,ll l=1,ll r=n)
{
ll p=upper_bound(vec[id].begin(),vec[id].end(),y)-vec[id].begin();
p=bit[id].get(p);
if(l==r) return p;
ll mid=l+r>>1;
if(x<=mid) return p+get(x,y,id*2,l,mid);
else return p+get(x,y,id*2+1,mid+1,r);
}
}tree;
set<int> s;
ll q;
char c[maxN];
ll a[maxN],r[maxN],t[maxN];
string T[maxN];
struct qq
{
ll i,l,r,v;
};
vector<qq> quer;
set<int> ::iterator it;
ll x[maxN],y[maxN];
ll ans[maxN];
void solve()
{
cin >> n >> q ;
for(int i=1;i<=n;i++)
{
cin >> c[i];
a[i]=c[i]-'0';
}
for(int i=1;i<=n;i++)
{
ll j=i;
if(a[i]==0) continue;
while(j<=n&&a[j]==a[i])
{
j++;
}
s.insert(i);
r[i]=j-1;
t[i]=0;
i=j-1;
}
for(int i=1;i<=q;i++)
{
cin >> T[i];
if(T[i]=="toggle")
{
ll p;
cin >> p;
if(a[p]==1)
{
it=s.upper_bound(p);
it--;
ll L=*it;
ll R=r[L];
ll T=t[L];
s.erase(it);
tree.fupdate(L,L,R,R);
quer.pb({i,L,R,i-T});
if(L<=p-1)
{
r[L]=p-1;
t[L]=i;
s.insert(L);
}
if(p+1<=R)
{
r[p+1]=R;
t[p+1]=i;
s.insert(p+1);
}
}
else
{
it=s.lower_bound(p);
ll L=p,R=p;
vector<ll> xoa;
if(it!=s.end()&&*it==p+1)
{
tree.fupdate(p+1,p+1,r[p+1],r[p+1]);
R=r[p+1];
quer.pb({i,p+1,r[p+1],i-t[p+1]});
xoa.pb(p+1);
}
if(it!=s.begin())
{
it--;
if(r[*it]==p-1)
{
tree.fupdate(*it,*it,p-1,p-1);
L=*it;
quer.pb({i,L,p-1,i-t[L]});
xoa.pb(L);
}
}
for(auto zz:xoa) s.erase(zz);
r[L]=R;
t[L]=i;
s.insert(L);
}
a[p]^=1;
}
else
{
cin >> x[i] >> y[i];
it=s.upper_bound(y[i]);
if(it!=s.begin())
{
it--;
if(*it<=x[i])
{
ans[i]+=i-t[*it];
}
}
}
}
//cout << ans[4]<<'\n';
tree.build();
ll j=0;
for(int i=1;i<=q;i++)
{
while(j<quer.size()&&quer[j].i<=i)
{
ll L=quer[j].l;
ll R=quer[j].r;
ll v=quer[j].v;
tree.update(L,L,R,R,v);
j++;
}
if(T[i]=="query")
{
ans[i]+=tree.get(x[i],y[i]);
cout << ans[i]<<'\n';
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
street_lamps.cpp:11:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
11 | const ll inf=1e18;
| ^~~~
street_lamps.cpp: In member function 'void off2dseg::BIT::upd(ll, ll)':
street_lamps.cpp:21:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | while(pos<bit.size())
| ~~~^~~~~~~~~~~
street_lamps.cpp: In member function 'void off2dseg::fupdate(ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | ll mid=l+r>>1;
| ~^~
street_lamps.cpp: In member function 'void off2dseg::update(ll, ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | ll mid=l+r>>1;
| ~^~
street_lamps.cpp: In member function 'll off2dseg::get(ll, ll, ll, ll, ll)':
street_lamps.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | ll mid=l+r>>1;
| ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:198:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | while(j<quer.size()&&quer[j].i<=i)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
66040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
77384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
66260 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
66336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
66256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
66040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
