#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// struct Node {
// int sum, lazy, tl, tr, l, r;
// Node() : sum(0), lazy(0), l(-1), r(-1) {}
// };
// // [1,1e9] - indexed 1
// struct SegTree {
// vector<Node> st;
// int cnt = 2;
// void build(int n) {
// st.assign(64*123456, Node());
// st[1].sum = 0;
// st[1].lazy = 0;
// st[1].tl = 1;
// st[1].tr = n;
// }
// void push_left(int node){
// if (st[node].l == -1) {
// st[node].l = cnt++;
// st[st[node].l].tl = st[node].tl;
// st[st[node].l].tr = (st[node].tl + st[node].tr) / 2;
// }
// }
// void push_right(int node){
// if (st[node].r == -1) {
// st[node].r = cnt++;
// st[st[node].r].tl = (st[node].tl + st[node].tr) / 2 + 1;
// st[st[node].r].tr = st[node].tr;
// }
// }
// void push_lazy(int node) {
// if (st[node].lazy) {
// st[node].sum = st[node].tr - st[node].tl + 1;
// push_left(node);
// push_right(node);
// st[st[node].l].lazy = st[st[node].r].lazy = 1;
// st[node].lazy = 0;
// }
// }
// void update(int l, int r, int node=1) {
// push_lazy(node);
// if (l == st[node].tl && r == st[node].tr) {
// st[node].lazy = 1;
// push_lazy(node);
// } else {
// int mid = (st[node].tl + st[node].tr) / 2;
// push_left(node);
// push_right(node);
// if (l > mid) update(l, r,st[node].r);
// else if (r <= mid) update(l, r,st[node].l);
// else {
// update(l, mid, st[node].l);
// update(mid + 1, r, st[node].r);
// }
// push_lazy(st[node].l);
// push_lazy(st[node].r);
// st[node].sum = st[st[node].l].sum + st[st[node].r].sum;
// }
// }
// int get(int l, int r, int node=1) {
// push_lazy(node);
// if (l == st[node].tl && r == st[node].tr) return st[node].sum;
// int mid = (st[node].tl + st[node].tr) / 2;
// push_left(node);
// push_right(node);
// if (l > mid) return get(l, r, st[node].r);
// else if (r <= mid) return get(l, r, st[node].l);
// else return get(l, mid, st[node].l) + get(mid + 1, r, st[node].r);
// }
// };
struct node {
int lz, lzL, lzR, val;
node *L, *R;
node(int lz = 0) : lz(lz), lzL(0), lzR(0), val(0), L(0), R(0) {}
void propagate(int l, int r) {
if(lz) {
if(l != r) {
if(L) L->lz = 1;
else lzL = 1;
if(R) R->lz = 1;
else lzR = 1;
}
val = (r-l+1);
lz = 0;
}
}
};
int get_val(node* root, int lz, int a, int b) {
if(!root) return lz*(b-a+1);
return root->val;
}
int null = 0;
struct SegTree {
node* root;
int n; // 0-indexed
SegTree(int n) : n(n), root(new node()) {}
void update(int a, int b, int x) { update(root, a, b, 0, n-1, x); }
void update(node* &root, int a, int b, int l, int r, int x, int lz = 0) {
if((l > b || r < a) && !root) return;
if(root == nullptr) root = new node(lz);
root->propagate(l, r);
if(l > b || r < a) return;
if(a <= l && r <= b) {
root->lz = x;
root->propagate(l, r);
} else {
int m = (l+r) >> 1;
update(root->L, a, b, l, m, x, root->lzL);
update(root->R, a, b, m+1, r, x, root->lzR);
root->val = get_val(root->L, root->lzL, l, m) + get_val(root->R, root->lzR, m+1, r);
}
}
int get(int a, int b) { return get(root, a, b, 0, n-1); }
int get(node* root, int a, int b, int l, int r, int lz = 0) {
if(l > b || r < a) return null;
if(root) root->propagate(l, r);
if((a <= l && r <= b) || !root) {
return get_val(root, lz, l, r);
} else {
int m = (l+r) >> 1;
return get(root->L, a, b, l, m, root->lzL) + get(root->R, a, b, m+1, r, root->lzR);
}
}
};
int main() {
iostream::sync_with_stdio(false);cin.tie(nullptr);
int q;cin>>q;
int op,l,r,c=0;
SegTree st(1e9);
while(q--){
cin>>op>>l>>r;
l--;r--;
if(op==1){
c=st.get(l+c,r+c);
cout<<c<<"\n";
}else{
st.update(l+c,r+c,1);
}
}
return 0;
}
Compilation message
apple.cpp: In constructor 'SegTree::SegTree(int)':
apple.cpp:109:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
109 | int n; // 0-indexed
| ^
apple.cpp:108:8: warning: 'node* SegTree::root' [-Wreorder]
108 | node* root;
| ^~~~
apple.cpp:110:2: warning: when initialized here [-Wreorder]
110 | SegTree(int n) : n(n), root(new node()) {}
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
