#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
struct Implicit {
vector <int> tree, tl, tr; int cnt;
int create () {
++cnt; tl.push_back(-1); tr.push_back(-1); tree.push_back(0); return cnt;
}
void init () {
tree.push_back(0); tl.push_back(-1); tr.push_back(-1); cnt = 0;
}
void update (int l, int r, int a, int b, int node) {
if (l == r) {
tree[node] += b; return;
}
int mid = (l + r) >> 1;
if (a <= mid) {
if (tl[node] == -1) {
int z = create(); tl[node] = z;
} else tree[node] -= tree[tl[node]];
update(l, mid, a, b, tl[node]);
tree[node] += tree[tl[node]];
} else {
if (tr[node] == -1) {
int z = create(); tr[node] = z;
}
else tree[node] -= tree[tr[node]];
update(mid + 1, r, a, b, tr[node]);
tree[node] += tree[tr[node]];
}
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
int sum = 0, mid = (l + r) >> 1;
if (tl[node] != -1) sum += get(l, mid, a, b, tl[node]);
if (tr[node] != -1) sum += get(mid + 1, r, a, b, tr[node]);
return sum;
}
};
typedef long long ll;
const int MAXN = 3e5 + 25;
bool a[MAXN];
int n, q;
set <array <int, 3>> cur;
Implicit tree[MAXN << 1];
void init () {
for (int i = 1; i <= n; i++) {
if (!a[i]) continue;
int j = i; while (j + 1 <= n && a[j + 1]) j++;
cur.insert({i, j, 0});
i = j;
}
}
void update (int l, int r, int a, int b, int c, int node) {
tree[node].update(1, n, b, c, 0);
if (l == r) return;
int mid = (l + r) >> 1, tl = node + 1, tr = node + 2 * (mid - l + 1);
if (a <= mid) update(l, mid, a, b, c, tl);
else update(mid + 1, r, a, b, c, tr);
}
int dfs (int l, int r, int a, int b, int c, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node].get(1, n, c, n, 0);
int mid = (l + r) >> 1, tl = node + 1, tr = node + 2 * (mid - l + 1);
return dfs(l, mid, a, b, c, tl) + dfs(mid + 1, r, a, b, c, tr);
}
void add (array <int, 3> x, int y) {
cur.erase(x);
update(1, n, x[0], x[1], y - x[2], 1);
}
void insert (array <int, 3> x) {
cur.insert(x);
}
int query (int l, int r, int x) {
int sum = dfs(1, n, 1, l, r, 1);
auto z = cur.upper_bound({l, n + 1, 0});
if (z != cur.begin()) {
z--; auto g = *z;
if (g[0] <= l && r <= g[1]) sum += x - g[2];
}
return sum;
}
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i < 2 * n; i++) tree[i].init();
for (int i = 1; i <= n; i++) {
char x; cin >> x; a[i] = x == '1';
}
init();
for (int t = 1; t <= q; t++) {
string x; cin >> x;
if (x == "query") {
int l, r; cin >> l >> r; r--;
cout << query(l, r, t) << '\n';
} else {
int x; cin >> x; a[x] ^= 1;
if (!a[x]) {
auto z = *(--cur.lower_bound({x + 1, 0, 0}));
add(z, t);
auto l = z; l[2] = t; l[1] = x - 1;
if (l[0] <= l[1]) insert(l);
l = z; l[2] = t; l[0] = x + 1;
if (l[0] <= l[1]) insert(l);
} else {
int mn = x, mx = x;
if (x < n && a[x + 1]) {
auto z = *(cur.lower_bound({x + 1, x + 1, 0}));
add(z, t);
mx = z[1];
}
if (x > 1 && a[x - 1]) {
auto z = *(--cur.lower_bound({x, x, 0}));
add(z, t);
mn = z[0];
}
array <int, 3> z = {mn, mx, t};
insert(z);
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
47192 KB |
Output is correct |
2 |
Correct |
10 ms |
47444 KB |
Output is correct |
3 |
Correct |
10 ms |
47196 KB |
Output is correct |
4 |
Correct |
11 ms |
47236 KB |
Output is correct |
5 |
Correct |
10 ms |
47452 KB |
Output is correct |
6 |
Correct |
10 ms |
47196 KB |
Output is correct |
7 |
Correct |
11 ms |
47452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
48508 KB |
Output is correct |
2 |
Correct |
247 ms |
48720 KB |
Output is correct |
3 |
Correct |
471 ms |
55044 KB |
Output is correct |
4 |
Correct |
2483 ms |
297060 KB |
Output is correct |
5 |
Correct |
2855 ms |
323984 KB |
Output is correct |
6 |
Correct |
2783 ms |
309660 KB |
Output is correct |
7 |
Correct |
296 ms |
104600 KB |
Output is correct |
8 |
Correct |
326 ms |
106040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
48216 KB |
Output is correct |
2 |
Correct |
13 ms |
47964 KB |
Output is correct |
3 |
Correct |
12 ms |
48068 KB |
Output is correct |
4 |
Correct |
11 ms |
47452 KB |
Output is correct |
5 |
Correct |
4130 ms |
381004 KB |
Output is correct |
6 |
Correct |
3686 ms |
367576 KB |
Output is correct |
7 |
Correct |
2726 ms |
323416 KB |
Output is correct |
8 |
Correct |
300 ms |
105812 KB |
Output is correct |
9 |
Correct |
82 ms |
48256 KB |
Output is correct |
10 |
Correct |
87 ms |
48152 KB |
Output is correct |
11 |
Correct |
100 ms |
48468 KB |
Output is correct |
12 |
Correct |
283 ms |
104532 KB |
Output is correct |
13 |
Correct |
287 ms |
105852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
47448 KB |
Output is correct |
2 |
Correct |
12 ms |
47708 KB |
Output is correct |
3 |
Correct |
12 ms |
47964 KB |
Output is correct |
4 |
Correct |
15 ms |
48216 KB |
Output is correct |
5 |
Correct |
477 ms |
120400 KB |
Output is correct |
6 |
Correct |
1610 ms |
249044 KB |
Output is correct |
7 |
Correct |
2692 ms |
309588 KB |
Output is correct |
8 |
Correct |
4159 ms |
345564 KB |
Output is correct |
9 |
Correct |
241 ms |
47956 KB |
Output is correct |
10 |
Correct |
222 ms |
47572 KB |
Output is correct |
11 |
Correct |
240 ms |
48156 KB |
Output is correct |
12 |
Correct |
192 ms |
47568 KB |
Output is correct |
13 |
Correct |
248 ms |
47952 KB |
Output is correct |
14 |
Correct |
189 ms |
47452 KB |
Output is correct |
15 |
Correct |
281 ms |
104532 KB |
Output is correct |
16 |
Correct |
320 ms |
105988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
47192 KB |
Output is correct |
2 |
Correct |
10 ms |
47444 KB |
Output is correct |
3 |
Correct |
10 ms |
47196 KB |
Output is correct |
4 |
Correct |
11 ms |
47236 KB |
Output is correct |
5 |
Correct |
10 ms |
47452 KB |
Output is correct |
6 |
Correct |
10 ms |
47196 KB |
Output is correct |
7 |
Correct |
11 ms |
47452 KB |
Output is correct |
8 |
Correct |
166 ms |
48508 KB |
Output is correct |
9 |
Correct |
247 ms |
48720 KB |
Output is correct |
10 |
Correct |
471 ms |
55044 KB |
Output is correct |
11 |
Correct |
2483 ms |
297060 KB |
Output is correct |
12 |
Correct |
2855 ms |
323984 KB |
Output is correct |
13 |
Correct |
2783 ms |
309660 KB |
Output is correct |
14 |
Correct |
296 ms |
104600 KB |
Output is correct |
15 |
Correct |
326 ms |
106040 KB |
Output is correct |
16 |
Correct |
15 ms |
48216 KB |
Output is correct |
17 |
Correct |
13 ms |
47964 KB |
Output is correct |
18 |
Correct |
12 ms |
48068 KB |
Output is correct |
19 |
Correct |
11 ms |
47452 KB |
Output is correct |
20 |
Correct |
4130 ms |
381004 KB |
Output is correct |
21 |
Correct |
3686 ms |
367576 KB |
Output is correct |
22 |
Correct |
2726 ms |
323416 KB |
Output is correct |
23 |
Correct |
300 ms |
105812 KB |
Output is correct |
24 |
Correct |
82 ms |
48256 KB |
Output is correct |
25 |
Correct |
87 ms |
48152 KB |
Output is correct |
26 |
Correct |
100 ms |
48468 KB |
Output is correct |
27 |
Correct |
283 ms |
104532 KB |
Output is correct |
28 |
Correct |
287 ms |
105852 KB |
Output is correct |
29 |
Correct |
11 ms |
47448 KB |
Output is correct |
30 |
Correct |
12 ms |
47708 KB |
Output is correct |
31 |
Correct |
12 ms |
47964 KB |
Output is correct |
32 |
Correct |
15 ms |
48216 KB |
Output is correct |
33 |
Correct |
477 ms |
120400 KB |
Output is correct |
34 |
Correct |
1610 ms |
249044 KB |
Output is correct |
35 |
Correct |
2692 ms |
309588 KB |
Output is correct |
36 |
Correct |
4159 ms |
345564 KB |
Output is correct |
37 |
Correct |
241 ms |
47956 KB |
Output is correct |
38 |
Correct |
222 ms |
47572 KB |
Output is correct |
39 |
Correct |
240 ms |
48156 KB |
Output is correct |
40 |
Correct |
192 ms |
47568 KB |
Output is correct |
41 |
Correct |
248 ms |
47952 KB |
Output is correct |
42 |
Correct |
189 ms |
47452 KB |
Output is correct |
43 |
Correct |
281 ms |
104532 KB |
Output is correct |
44 |
Correct |
320 ms |
105988 KB |
Output is correct |
45 |
Correct |
76 ms |
47824 KB |
Output is correct |
46 |
Correct |
125 ms |
47676 KB |
Output is correct |
47 |
Correct |
1149 ms |
149736 KB |
Output is correct |
48 |
Correct |
2405 ms |
296572 KB |
Output is correct |
49 |
Correct |
96 ms |
47896 KB |
Output is correct |
50 |
Correct |
94 ms |
47952 KB |
Output is correct |
51 |
Correct |
101 ms |
48460 KB |
Output is correct |
52 |
Correct |
103 ms |
48008 KB |
Output is correct |
53 |
Correct |
124 ms |
48124 KB |
Output is correct |
54 |
Correct |
99 ms |
47972 KB |
Output is correct |