#include <bits/stdc++.h>
using namespace std;
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) tl[node] = create();
else tree[node] -= tree[tl[node]];
update(l, mid, a, b, tl[node]);
tree[node] += tree[tl[node]];
} else {
if (tr[node] == -1) tr[node] = create();
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 <vector <int>> 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;
}
}
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, 1);
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 update (int l, int r, int a, int b, int c, int d, int node) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
tree[node].update(1, n, c, d, 1);
return;
}
int mid = (l + r) >> 1, tl = node + 1, tr = node + 2 * (mid - l + 1);
update(l, mid, a, b, c, d, tl); update(mid + 1, r, a, b, c, d, tr);
}
//vector <vector <int>> inserted;
void add (vector <int> x, int y) {
cur.erase(x);
update(1, n, 1, x[0], x[1], y - x[2], 1);
//inserted.push_back({x[0], x[1], y - x[2]});
}
void insert (vector <int> x) {
cur.insert(x);
}
int query (int l, int r, int x) {
//int sum = 0;
//for (auto i : inserted) if (i[0] <= l && r <= i[1]) sum += i[2];
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 () {
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';
}
return 0;
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];
}
vector <int> z = {mn, mx, t};
insert(z);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
47192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
47192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
