#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int y, val, sz, c, sum;
node *lx, *rx;
node(int x, int v) : val(x), sz(1), c(v), sum(v), lx(NULL), rx(NULL){
y = uniform_int_distribution<int>(0, 2e9)(rng);
}
};
struct rbst{
void rec(node* a){
a->sum = (a->lx != NULL ? a->lx->sum : 0) + (a->rx != NULL ? a->rx->sum : 0) + a->c;
}
node* merge(node* a, node* b){
if(a == NULL) return b;
if(b == NULL) return a;
if(a->y > b->y){
a->rx = merge(a->rx, b);
rec(a);
return a;
} else {
b->lx = merge(a, b->lx);
rec(b);
return b;
}
}
ar<node*, 2> split(node* a, int v){
if(a == NULL) return {NULL, NULL};
if(a->val < v){
auto t = split(a->rx, v);
a->rx = t[0]; rec(a);
return {a, t[1]};
} else {
auto t = split(a->lx, v);
a->lx = t[1]; rec(a);
return {t[0], a};
}
}
bool is(node*&a, int x, int v){
if(a == NULL) return false;
if(a->val == x){
a->c += v; rec(a);
return true;
}
bool ok = 0;
if(a->val < x) ok = is(a->rx, x, v);
else ok = is(a->lx, x, v);
rec(a);
return ok;
}
void add(node*&root, int x, int v){
if(is(root, x, v)) return;
node* tmp = new node(x, v);
auto tt = split(root, x);
root = merge(tt[0], tmp);
root = merge(root, tt[1]);
}
int get(node*&a, int x){
if(a == NULL) return 0;
if(a->val <= x){
return (a->lx != NULL ? a->lx->sum : 0) + a->c + get(a->rx, x);
} else {
return get(a->lx, x);
}
}
void print(node* a){
if(a == NULL) return;
print(a->lx);
cout<<a->val<<" ";
print(a->rx);
}
}T;
const int N = 3e5 + 5;
struct ST{
node* tree[N << 2];
void add(int l, int r, int L, int R, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
T.add(tree[x], L, v), T.add(tree[x], R, -v);
return;
} int m = (lx + rx) >> 1;
add(l, r, L, R, v, lx, m, x<<1), add(l, r, L, R, v, m+1, rx, x<<1|1);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
//~ cout<<"->"<<T.get(tree[x], r)[0]<<" "<<T.get(tree[x], r)[1]<<"\n";
if(lx == rx) return T.get(tree[x], r);
int m = (lx + rx) >> 1;
if(l <= m) return T.get(tree[x], r) + get(l, r, lx, m, x<<1);
else return T.get(tree[x], r) + get(l, r, m+1, rx, x<<1|1);
}
}tree;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin>>n>>q;
string s; cin>>s;
set<int> ss; ss.insert(-1), ss.insert(n);
for(int i=0;i<n;){
if(s[i] == '0') { ss.insert(i++); continue; }
int j = i;
while(j<n && s[j] == '1') j++;
tree.add(i, j - 1, i, j, 1);
i = j;
}
for(int t=0;t<q;t++){
string q; cin>>q;
if(q == "query"){
int l, r; cin>>l>>r; l--, r-=2;
bool is = 0;
{
auto it = ss.lower_bound(l);
if(r < *it) is = 1;
}
cout<<tree.get(l, r) + is * t<<"\n";
} else {
int p; cin>>p; p--;
if(s[p] == '1'){
auto lx = --ss.upper_bound(p);
auto rx = ss.lower_bound(p);
tree.add(*lx + 1, p, p, *rx, t);
ss.insert(p); s[p] = '0';
} else {
ss.erase(p); s[p] = '1';
auto lx = --ss.upper_bound(p);
auto rx = ss.lower_bound(p);
tree.add(*lx + 1, p, p, *rx, -t);
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
1324 KB |
Output is correct |
2 |
Correct |
178 ms |
1604 KB |
Output is correct |
3 |
Correct |
281 ms |
5028 KB |
Output is correct |
4 |
Correct |
515 ms |
46216 KB |
Output is correct |
5 |
Correct |
542 ms |
58012 KB |
Output is correct |
6 |
Correct |
556 ms |
49052 KB |
Output is correct |
7 |
Correct |
374 ms |
15296 KB |
Output is correct |
8 |
Correct |
137 ms |
2876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
572 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
649 ms |
72468 KB |
Output is correct |
6 |
Correct |
556 ms |
71292 KB |
Output is correct |
7 |
Correct |
506 ms |
62688 KB |
Output is correct |
8 |
Correct |
145 ms |
8608 KB |
Output is correct |
9 |
Correct |
78 ms |
4000 KB |
Output is correct |
10 |
Correct |
90 ms |
4332 KB |
Output is correct |
11 |
Correct |
93 ms |
4556 KB |
Output is correct |
12 |
Correct |
346 ms |
21212 KB |
Output is correct |
13 |
Correct |
132 ms |
8652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
379 ms |
36016 KB |
Output is correct |
6 |
Correct |
488 ms |
45244 KB |
Output is correct |
7 |
Correct |
580 ms |
53608 KB |
Output is correct |
8 |
Correct |
645 ms |
63092 KB |
Output is correct |
9 |
Correct |
200 ms |
4308 KB |
Output is correct |
10 |
Correct |
179 ms |
3540 KB |
Output is correct |
11 |
Correct |
199 ms |
4284 KB |
Output is correct |
12 |
Correct |
186 ms |
3400 KB |
Output is correct |
13 |
Correct |
190 ms |
4276 KB |
Output is correct |
14 |
Correct |
177 ms |
3428 KB |
Output is correct |
15 |
Correct |
400 ms |
21220 KB |
Output is correct |
16 |
Correct |
130 ms |
8772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
161 ms |
1324 KB |
Output is correct |
9 |
Correct |
178 ms |
1604 KB |
Output is correct |
10 |
Correct |
281 ms |
5028 KB |
Output is correct |
11 |
Correct |
515 ms |
46216 KB |
Output is correct |
12 |
Correct |
542 ms |
58012 KB |
Output is correct |
13 |
Correct |
556 ms |
49052 KB |
Output is correct |
14 |
Correct |
374 ms |
15296 KB |
Output is correct |
15 |
Correct |
137 ms |
2876 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
572 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
649 ms |
72468 KB |
Output is correct |
21 |
Correct |
556 ms |
71292 KB |
Output is correct |
22 |
Correct |
506 ms |
62688 KB |
Output is correct |
23 |
Correct |
145 ms |
8608 KB |
Output is correct |
24 |
Correct |
78 ms |
4000 KB |
Output is correct |
25 |
Correct |
90 ms |
4332 KB |
Output is correct |
26 |
Correct |
93 ms |
4556 KB |
Output is correct |
27 |
Correct |
346 ms |
21212 KB |
Output is correct |
28 |
Correct |
132 ms |
8652 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
379 ms |
36016 KB |
Output is correct |
34 |
Correct |
488 ms |
45244 KB |
Output is correct |
35 |
Correct |
580 ms |
53608 KB |
Output is correct |
36 |
Correct |
645 ms |
63092 KB |
Output is correct |
37 |
Correct |
200 ms |
4308 KB |
Output is correct |
38 |
Correct |
179 ms |
3540 KB |
Output is correct |
39 |
Correct |
199 ms |
4284 KB |
Output is correct |
40 |
Correct |
186 ms |
3400 KB |
Output is correct |
41 |
Correct |
190 ms |
4276 KB |
Output is correct |
42 |
Correct |
177 ms |
3428 KB |
Output is correct |
43 |
Correct |
400 ms |
21220 KB |
Output is correct |
44 |
Correct |
130 ms |
8772 KB |
Output is correct |
45 |
Correct |
95 ms |
2756 KB |
Output is correct |
46 |
Correct |
123 ms |
2768 KB |
Output is correct |
47 |
Correct |
257 ms |
23208 KB |
Output is correct |
48 |
Correct |
534 ms |
51108 KB |
Output is correct |
49 |
Correct |
95 ms |
4356 KB |
Output is correct |
50 |
Correct |
89 ms |
4428 KB |
Output is correct |
51 |
Correct |
90 ms |
4628 KB |
Output is correct |
52 |
Correct |
97 ms |
4928 KB |
Output is correct |
53 |
Correct |
119 ms |
4896 KB |
Output is correct |
54 |
Correct |
95 ms |
4940 KB |
Output is correct |