#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
typedef long long ll;
const int maxn = 3e5+10;
const int mod = 1e9+7;
const int inf = 1e9+10;
int n, q;
struct paralel_segment
{
int root[maxn<<2], seg[maxn*80], lst, L[maxn*80], R[maxn*80];
paralel_segment()
{
memset(root, 0, sizeof root);
memset(seg, 0, sizeof seg);
memset(L, 0, sizeof L);
memset(R, 0, sizeof R);
lst = 0;
}
void add(int pos, int val, int v, int tl = 0, int tr = n)
{
if(tl == tr)
{
seg[v] += val;
return;
}
int tm = (tl + tr) >> 1;
if(!L[v]) L[v] = ++lst;
if(!R[v]) R[v] = ++lst;
if(pos <= tm) add(pos, val, L[v], tl, tm);
else add(pos, val, R[v], tm+1, tr);
seg[v] = seg[L[v]] + seg[R[v]];
}
int ask(int l, int r, int v, int tl = 0, int tr = n)
{
if(v == 0 || l > r) return 0;
if(tl == l && tr == r) return seg[v];
int tm = (tl + tr) >> 1;
return ask(l, min(tm,r), L[v], tl, tm) +
ask(max(tm+1,l), r, R[v], tm+1, tr);
}
} seg2;
struct segment
{
void upd(int pos, int val, int I, int tp, int v = 1, int tl = 0, int tr = n)
{
if(!seg2.root[v]) seg2.root[v] = ++seg2.lst;
if(tp == 1)
seg2.add(val, I, seg2.root[v]);
else
seg2.add(val,-I, seg2.root[v]);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos, val, I, tp, v<<1, tl, tm);
else upd(pos, val, I, tp, v<<1|1, tm+1, tr);
}
int ask(int l, int r, int val, int v = 1, int tl = 0, int tr = n)
{
/// tedad adad hadeagal val
if(!seg2.root[v]) seg2.root[v] = ++seg2.lst;
if(l > r) return 0;
if(tl == l && tr == r)
return seg2.ask(val, n, seg2.root[v]);
int tm = (tl + tr) >> 1;
return ask(l, min(tm,r), val, v<<1, tl, tm) +
ask(max(tm+1,l), r, val, v<<1|1, tm+1, tr);
}
} seg;
vector<pair<pii,int>> vec[maxn<<2];
//vector<pair<pii,pii>> rec;
void add(int l, int r, int L, int R, int I, int v = 1, int tl = 0, int tr = q)
{
/// l, r baezye zamani
/// L, R bazeye makani
if(v == 1)
{
// rec.push_back({{l,r},{L,R}});
r = q;
}
if(l > r) return;
if(tl == l && tr == r)
{
vec[v].push_back({{L,R},I});
//cout<< I <<" "<< l <<" "<< r <<" "<< L <<" "<< R <<"\n";
return;
}
int tm = (tl + tr) >> 1;
add(l, min(tm,r), L, R, I, v<<1, tl, tm);
add(max(tm+1,l), r, L, R, I, v<<1|1, tm+1, tr);
}
pii Q[maxn];
int ans[maxn];
void dfs(int v = 1, int tl = 0, int tr = q)
{
for(auto X : vec[v])
{
// cout<<"upd "<< X.F.F <<" "<< X.F.S <<" "<< X.S <<" "<< 1 <<"\n";
seg.upd(X.F.F, X.F.S, X.S, 1);
}
if(tl == tr)
{
if(Q[tl].F)
{
// cout<<"ask "<< 0 <<" "<< Q[tl].F <<" "<< Q[tl].S <<" "<< seg.ask(0, Q[tl].F, Q[tl].S) <<"\n";
ans[tl] += seg.ask(0, Q[tl].F, Q[tl].S);
}
}
if(tl < tr)
{
int tm = (tl + tr) >> 1;
dfs(v<<1, tl, tm);
dfs(v<<1|1, tm+1, tr);
}
for(auto X : vec[v])
{
seg.upd(X.F.F, X.F.S, X.S, 2);
// cout<<"upd "<< X.F.F <<" "<< X.F.S <<" "<< X.S <<" "<< 2 <<"\n";
}
}
map<int,int> mp[maxn], mp2[maxn];
bool is[maxn];
int lst;
vector<int> must[maxn];
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>> n >> q;
string s; cin>> s; s = "*" + s;
int Ll = 0, Rr = 0;
set<pii> se;
for(int i = 1; i <= n; i++)
{
if(s[i] == '1')
{
Rr = i;
is[i] = 1;
}
else Ll = i;
if(s[i] == '1')
{
bool sw = 0;
if(i == n) sw = 1;
else if(s[i+1] == '0') sw = 1;
if(sw)
{
mp[Ll+1][Rr] = 0;
se.insert({Ll+1,Rr});
mp2[Ll+1][Rr] = ++lst;
}
}
}
for(int i = 1; i <= q; i++)
{
string tp; cin>> tp;
if(tp == "query")
{
int l, r; cin>> l >> r; r--;
auto it = se.upper_bound({l,inf});
if(it != se.begin())
{
it--; int L = (*it).F, R = (*it).S;
if(r <= R) must[mp2[L][R]].push_back(i);
}
Q[i] = {l,r};
}
else
{
int pos; cin>> pos;
if(is[pos])
{
auto it = se.upper_bound({pos,inf}); it--;
int l = (*it).F, r = (*it).S;
se.erase({l,r});
for(auto id : must[mp2[l][r]])
ans[id] -= i-id;
must[mp2[l][r]].clear();
add(mp[l][r], i-1, l, r, i-mp[l][r]);
mp[l][r] = 0;
if(pos != l)
{
se.insert({l,pos-1});
mp2[l][pos-1] = ++lst;
mp[l][pos-1] = i;
}
if(pos != r)
{
se.insert({pos+1,r});
mp2[pos+1][r] = ++lst;
mp[pos+1][r] = i;
}
is[pos] = 0;
}
else
{
int L = pos, R = pos;
auto it = se.upper_bound({pos,inf});
bool DO = 0;
auto it2 = it; if(it2 != se.begin()) {it2--; DO = 1;}
if(it != se.end())
{
int l = (*it).F, r = (*it).S;
if(pos+1 == l)
{
R = r;
se.erase({l,r});
for(auto id : must[mp2[l][r]])
ans[id] -= i-id;
must[mp2[l][r]].clear();
// cout<< l <<" "<< r <<"\n";
add(mp[l][r], i-1, l, r, i-mp[l][r]);
mp[l][r] = 0;
}
}
// cout<< (*it).F <<" "<< (*it).S <<"\n";
if(DO)
{
it = it2; int l = (*it).F, r = (*it).S;
// cout<< l <<" "<< r <<"\n";
if(pos-1 == r)
{
L = l;
// cout<< l <<" "<< r <<"\n";
se.erase({l,r});
for(auto id : must[mp2[l][r]])
ans[id] -= i-id;
must[mp2[l][r]].clear();
add(mp[l][r], i-1, l, r, i-mp[l][r]);
mp[l][r] = 0;
}
}
se.insert({L,R});
mp[L][R] = i;
mp2[L][R] = ++lst;
is[pos] = 1;
}
}
}
for(auto X : se)
{
int l = X.F, r = X.S;
for(auto id : must[mp2[l][r]])
ans[id] -= q+1-id;
must[mp2[l][r]].clear();
add(mp[l][r], q, l, r, q+1-mp[l][r]);
mp[l][r] = 0;
}
dfs();
for(int i = 1; i <= q; i++)
if(Q[i].F) cout<< ans[i] <<"\n";
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
350200 KB |
Output is correct |
| 2 |
Correct |
202 ms |
350200 KB |
Output is correct |
| 3 |
Correct |
202 ms |
350200 KB |
Output is correct |
| 4 |
Correct |
197 ms |
350200 KB |
Output is correct |
| 5 |
Correct |
196 ms |
350328 KB |
Output is correct |
| 6 |
Correct |
196 ms |
350200 KB |
Output is correct |
| 7 |
Correct |
196 ms |
350200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1646 ms |
380772 KB |
Output is correct |
| 2 |
Correct |
2263 ms |
381284 KB |
Output is correct |
| 3 |
Execution timed out |
5018 ms |
383776 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
350456 KB |
Output is correct |
| 2 |
Correct |
204 ms |
350360 KB |
Output is correct |
| 3 |
Correct |
204 ms |
350328 KB |
Output is correct |
| 4 |
Correct |
194 ms |
350332 KB |
Output is correct |
| 5 |
Execution timed out |
5043 ms |
431656 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
350328 KB |
Output is correct |
| 2 |
Correct |
202 ms |
350328 KB |
Output is correct |
| 3 |
Correct |
205 ms |
350584 KB |
Output is correct |
| 4 |
Correct |
207 ms |
350416 KB |
Output is correct |
| 5 |
Correct |
1582 ms |
367584 KB |
Output is correct |
| 6 |
Execution timed out |
5072 ms |
387432 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
350200 KB |
Output is correct |
| 2 |
Correct |
202 ms |
350200 KB |
Output is correct |
| 3 |
Correct |
202 ms |
350200 KB |
Output is correct |
| 4 |
Correct |
197 ms |
350200 KB |
Output is correct |
| 5 |
Correct |
196 ms |
350328 KB |
Output is correct |
| 6 |
Correct |
196 ms |
350200 KB |
Output is correct |
| 7 |
Correct |
196 ms |
350200 KB |
Output is correct |
| 8 |
Correct |
1646 ms |
380772 KB |
Output is correct |
| 9 |
Correct |
2263 ms |
381284 KB |
Output is correct |
| 10 |
Execution timed out |
5018 ms |
383776 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
