#include<bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const int SIZ = 120;
int n, q, ofs = 1, cnt;
string s;
map <int, int> mp, rst;
set <int> st;
set <int> :: iterator it;
int t[MAXN * SIZ], lef[MAXN * SIZ], rig[MAXN * SIZ];
struct tournament {
int root;
tournament () {
root = ++cnt;
}
void update (int x, int pos, int lo, int hi, int val) {
if (lo == hi) {
t[x] += val;
return;
}
int mid = (lo + hi) / 2;
if (pos <= mid) {
if (lef[x] == 0) lef[x-1] = ++cnt;
update(lef[x], pos, lo, mid, val);
} else {
if (rig[x] == 0) rig[x] = ++cnt;
update(rig[x], pos, mid+1, hi, val);
}
t[x] = t[lef[x]] + t[rig[x]];
}
int upit (int x, int from, int to, int lo, int hi) {
if (x == 0) return 0;
if (from <= lo && hi <= to) return t[x];
if (to < lo || hi < from) return 0;
return upit(lef[x], from, to, lo, (lo + hi)/2) + upit(rig[x], from, to, (lo + hi)/2+1, hi);
}
} fen[MAXN];
void ubaci (int x, int y, int val) {
for (; x < MAXN; x += x&-x) {
fen[x].update(fen[x].root, y, 0, ofs-1, val);
}
}
int upit (int x, int y) {
int res = 0;
for (; x > 0; x -= x&-x) {
res += fen[x].upit(fen[x].root, y, ofs-1, 0, ofs-1);
}
return res;
}
void dodaj (int a, int b, int t) {
st.insert(a);
mp[a] = t;
rst[a] = b;
}
void brisi (int a, int b, int t) {
ubaci(a, b, t - mp[a]);
st.erase(a);
mp.erase(a);
rst.erase(a);
}
void precompute () {
int lim = -1;
for (int i=1; i<=n; i++) {
if (s[i] == '1' && (i == 1 || s[i-1] == '0')) lim = i;
if (s[i] == '1' && (i == n || s[i+1] == '0')) {
dodaj(lim, i, 0);
}
}
}
void ispis () {
cout << "ispis" << endl;
for (auto x : st) {
cout << "bla " << x << " " << rig[x] << " " << mp[x] << endl;
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q >> s;
s = '.' + s;
while (ofs < n+1) ofs *= 2;
precompute();
for (int i=1; i<=q; i++) {
string t;
cin >> t;
if (t == "query") {
int a, b;
cin >> a >> b; b--;
int res = upit(a, b);
it = st.upper_bound(a);
if (it != st.begin()) {
it--;
if (b <= rst[*it]) {
res += i - mp[*it];
}
}
cout << res << '\n';
} else {
int x;
cin >> x;
if (s[x] == '0') {
s[x] = '1';
int ll = x, rr = x;
it = st.upper_bound(x);
if (it != st.end() && *it == x+1) {
rr = rst[*it];
brisi(*it, rst[*it], i);
}
it = st.upper_bound(x);
if (it != st.begin()) {
it--;
if (rst[*it] == x-1) {
ll = *it;
brisi(*it, rst[*it], i);
}
}
dodaj(ll, rr, i);
} else {
s[x] = '0';
it = st.upper_bound(x); it--;
int ll = *it;
int rr = rst[*it];
brisi(ll, rr, i);
if (ll <= x-1) dodaj(ll, x-1, i);
if (x+1 <= rr) dodaj(x+1, rr, i);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
92540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2424 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
2452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1784 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1912 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
