#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e5+10;
const int N=1e3+10;
const int mod=1e9+7;
int n,q,a[M],b[M];
string tt[M];
int s[M];
// bit 1 chieu
int T[M];
void upd(int idx,int val)
{
while(idx<=n)
{
T[idx]+=val;
idx+=idx&(-idx);
}
}
int get(int idx)
{
int res=0;
while(idx>0) {
res+=T[idx];
idx-=idx&(-idx);
}
return res;
}
int findl(int idx)
{
int l=1,r=idx-1,ret=idx;
while(l<=r) {
int mid=(l+r)/2;
//cout << idx << " " << mid << " " << get(idx)-get(mid-1) << " " << idx-mid+1 << "\n";
if(get(idx)-get(mid-1)==idx-mid+1) {
r=mid-1;
ret=mid;
}
else l=mid+1;
}
return ret;
}
int findr(int idx)
{
int l=idx+1,r=n,ret=idx;
while(l<=r) {
int mid=(l+r)/2;
//cout << idx << " " << mid << " " << get(mid)-get(idx-1) << " " << mid-idx+1 << "\n";
if(get(mid)-get(idx-1)==mid-idx+1) {
l=mid+1;
ret=mid;
}
else r=mid-1;
}
return ret;
}
// fake
vector<int> pos[M];
vector<int> bit[M];
void fake_upd2(int u,int v)
{
while(u<=n) {
pos[u].pb(v);
u+=u&(-u);
}
}
void fake_get2(int u,int v)
{
while(u>0) {
pos[u].pb(v);
u-=u&(-u);
}
}
void fake_sqrt2(int u,int v)
{
fake_upd2(u,u);
fake_upd2(v+1,u);
fake_upd2(u,v+1);
fake_upd2(v+1,v+1);
}
int tmps[M];
void fake_solve()
{
fori(i,1,n) tmps[i]=s[i];
fori(i,1,n) if(tmps[i]) upd(i,1);
fori(i,1,q) {
if(tt[i]=="toggle") {
int idx=a[i];
if(tmps[idx]) { //tach
int l=findl(idx);
int r=findr(idx);
upd(idx,-1);
tmps[idx]=0;
fake_sqrt2(l,r+1);//->l,r;
}
else { // hop
upd(idx,1);
tmps[idx]=1;
int l=findl(idx);
int r=findr(idx);
if(l!=idx) fake_sqrt2(l,idx);//->l,i-1
if(r!=idx) fake_sqrt2(idx+1,r+1);//->i+1,r
}
}
else {
cin >> a[i] >> b[i];
fake_get2(a[i],b[i]);// a[i],b[i]
}
}
fori(i,1,n+1) {
pos[i].pb(0);
sort(pos[i].begin(),pos[i].end());
pos[i].resize(unique(pos[i].begin(),pos[i].end())-pos[i].begin());
bit[i].assign(pos[i].size(),0);
}
fori(i,1,n) T[i]=0;
}
// bit 2 chieu
void upd2(int u,int v,int val)
{
for(int i=u;i<=n+1;i+=i&(-i)) {
for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j<pos[i].size();j+=j&(-j)) {
bit[i][j]+=val;
}
}
}
int get2(int u,int v) {
int res=0;
for(int i=u;i>0;i-=i&(-i)) {
for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j>0;j-=j&(-j))
res+=bit[i][j];
}
return res;
}
// segment tree
int t[4*M],lz[4*M];
void lazy(int s)
{
t[s*2]=lz[s];
t[s*2+1]=lz[s];
lz[s*2]=lz[s];
lz[s*2+1]=lz[s];
lz[s]=0;
return ;
}
void upd_seg(int s,int l,int r,int u,int v,int val)
{
if(l>v||r<u) return ;
if(u<=l&&r<=v)
{
t[s]=val;
lz[s]=val;
return ;
}
int mid=(l+r)/2;
if(l!=r&&lz[s]) lazy(s);
upd_seg(s*2,l,mid,u,v,val);
upd_seg(s*2+1,mid+1,r,u,v,val);
t[s]=max(t[s*2],t[s*2+1]);
}
int get_seg(int s,int l,int r,int u,int v)
{
if(l>v||r<u) return 0;
if(u<=l&&r<=v) return t[s];
int mid=(l+r)/2;
if(l!=r&&lz[s]) lazy(s);
return max(get_seg(s*2,l,mid,u,v),get_seg(s*2+1,mid+1,r,u,v));
}
//
void sqrt2(int u,int v,int val)
{
upd2(u,u,val);
upd2(v+1,u,-val);
upd2(u,v+1,-val);
upd2(v+1,v+1,val);
}
void solve(){
fori(i,1,n) if(s[i]) upd(i,1);
fori(i,1,q) {
if(tt[i]=="toggle") {
int idx=a[i];
if(s[idx]) { //tach
int l=findl(idx);
int r=findr(idx);
upd(idx,-1);
s[idx]=0;
int pre=get_seg(1,1,n,l,r);
sqrt2(l,r+1,i-pre);//->l,r;
if(idx!=l) upd_seg(1,1,n,l,idx-1,i);
if(idx!=r) upd_seg(1,1,n,idx+1,r,i);
}
else { // hop
upd(idx,1);
s[idx]=1;
int l=findl(idx);
int r=findr(idx);
if(l!=idx) {
int pre=get_seg(1,1,n,l,idx-1);
sqrt2(l,idx,i-pre);//->l,i-1
}
if(r!=idx) {
int pre=get_seg(1,1,n,idx+1,r);
sqrt2(idx+1,r+1,i-pre);
}
//fori(i,1,n) fori(j,i,n) cout << i << " " << j << " " << get(j)-get(i-1) << "\n";
//cout << l << " " << r << "\n";
upd_seg(1,1,n,l,r,i);
}
}
else {
cin >> a[i] >> b[i];
int x=0;
//cout << get(b[i]-1)-get(a[i]-1) << " " << b[i]-a[i] << " ";
if(get(b[i]-1)-get(a[i]-1)==b[i]-a[i]) x=i-get_seg(1,1,n,a[i],b[i]-1);
cout << get2(a[i],b[i])+x << "\n";// a[i],b[i]
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r"))
{
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> q;
fori(i,1,n) {
char ch;
cin >> ch;
s[i]=ch-'0';
}
fori(i,1,q) {
cin >> tt[i];
if(tt[i]=="toggle") cin >> a[i];
else cin >> a[i] >> b[i];
}
fake_solve();
solve();
}
Compilation message
street_lamps.cpp: In function 'void upd2(long long int, long long int, long long int)':
street_lamps.cpp:130:74: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j<pos[i].size();j+=j&(-j)) {
| ~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:238:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
238 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:239:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
239 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:244:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
244 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:245:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
245 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
25436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15184 KB |
Output is correct |
| 2 |
Correct |
5 ms |
13136 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12880 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12880 KB |
Output is correct |
| 5 |
Runtime error |
20 ms |
21840 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12880 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12880 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12880 KB |
Output is correct |
| 4 |
Correct |
6 ms |
13136 KB |
Output is correct |
| 5 |
Runtime error |
18 ms |
21840 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12624 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12624 KB |
Output is correct |
| 8 |
Runtime error |
29 ms |
25436 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
