#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*30], lst, L[maxn*30], R[maxn*30];
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];
void add(int l, int r, int L, int R, int I)
{
/// l, r baezye zamani
/// L, R bazeye makani
vec[l].push_back({{L,R},I});
}
pii Q[maxn];
int ans[maxn];
map<int,int> mp[maxn], mp2[maxn];
bool is[maxn];
int lst;
vector<int> must[maxn*3];
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();
add(mp[l][r], i-1, l, r, i-mp[l][r]);
mp[l][r] = 0;
}
}
if(DO)
{
it = it2; int l = (*it).F, r = (*it).S;
if(pos-1 == r)
{
L = l;
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;
}
for(int i = 0; i <= q; i++)
{
for(auto X : vec[i])
seg.upd(X.F.F, X.F.S, X.S, 1);
if(Q[i].F)
ans[i] += seg.ask(0, Q[i].F, Q[i].S);
}
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 |
98 ms |
167032 KB |
Output is correct |
| 2 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 3 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 4 |
Correct |
97 ms |
167064 KB |
Output is correct |
| 5 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 6 |
Correct |
96 ms |
167032 KB |
Output is correct |
| 7 |
Correct |
96 ms |
167032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
384 ms |
177388 KB |
Output is correct |
| 2 |
Correct |
476 ms |
177656 KB |
Output is correct |
| 3 |
Correct |
846 ms |
180344 KB |
Output is correct |
| 4 |
Runtime error |
1152 ms |
405984 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
167160 KB |
Output is correct |
| 2 |
Correct |
101 ms |
167300 KB |
Output is correct |
| 3 |
Correct |
102 ms |
167192 KB |
Output is correct |
| 4 |
Correct |
99 ms |
167160 KB |
Output is correct |
| 5 |
Runtime error |
1320 ms |
420736 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
167072 KB |
Output is correct |
| 2 |
Correct |
103 ms |
167160 KB |
Output is correct |
| 3 |
Correct |
107 ms |
167160 KB |
Output is correct |
| 4 |
Correct |
105 ms |
167160 KB |
Output is correct |
| 5 |
Runtime error |
759 ms |
369632 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 2 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 3 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 4 |
Correct |
97 ms |
167064 KB |
Output is correct |
| 5 |
Correct |
98 ms |
167032 KB |
Output is correct |
| 6 |
Correct |
96 ms |
167032 KB |
Output is correct |
| 7 |
Correct |
96 ms |
167032 KB |
Output is correct |
| 8 |
Correct |
384 ms |
177388 KB |
Output is correct |
| 9 |
Correct |
476 ms |
177656 KB |
Output is correct |
| 10 |
Correct |
846 ms |
180344 KB |
Output is correct |
| 11 |
Runtime error |
1152 ms |
405984 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
