#include<bits/stdc++.h>
using namespace std;
const long long int MAX_N = 1000000000000;
const long long int NIL = -1;
class SparseSegmentTree{
public:
SparseSegmentTree(long long int number_of_datum){
n = 1;
while(n < number_of_datum) n *= 2;
root = new Node(0, n);
}
void range_update(long long int s, long long int t){
inner_add(s, t + 1, root);
}
long long int range_query(long long int s, long long int t){
return inner_getsum(s, t + 1, root);
}
private:
struct Node{
long long int left_bound, right_bound;
long long int dat, laz = NIL;
Node *left_child, *right_child;
Node(long long int lb, long long int rb){
left_bound = lb;
right_bound = rb;
}
};
void inner_split(Node *node){
if(node->left_child) return;
long long int l = node->left_bound;
long long int r = node->right_bound;
if(l + 1 == r) return;
long long int mid = (l + r) / 2;
node->left_child = new Node(l, mid);
node->right_child = new Node(mid, r);
}
void inner_prop(Node *node){
inner_split(node);
if(!node->left_child) return;
if(node->laz == NIL) return;
node->left_child->dat = node->laz / 2;
node->right_child->dat = node->laz / 2;
node->left_child->laz = node->laz / 2;
node->right_child->laz = node->laz / 2;
node->laz = NIL;
}
void inner_add(long long int a, long long int b, Node *node){
long long int l = node->left_bound;
long long int r = node->right_bound;
if(b <= l || r <= a) return;
if(a <= l && r <= b){
node->dat = r - l;
node->laz = r - l;
return;
}
inner_prop(node);
if(!node->left_child) return;
inner_add(a, b, node->left_child);
inner_add(a, b, node->right_child);
node->dat = node->left_child->dat + node->right_child->dat;
}
long long int inner_getsum(long long int a, long long int b, Node *node){
if(!node) return 0;
long long int l = node->left_bound;
long long int r = node->right_bound;
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return node->dat;
inner_prop(node);
return inner_getsum(a, b, node->left_child) + inner_getsum(a, b, node->right_child);
}
long long int n;
Node *root;
};
int q;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> q;
SparseSegmentTree st(MAX_N);
long long int C = 0;
while(q--){
int op;
cin >> op;
if(op == 2){
long long int s, t;
cin >> s >> t;
s--;
t--;
st.range_update(s + C, t + C);
}else{
long long int s, t;
cin >> s >> t;
s--;
t--;
long long int res = st.range_query(s + C, t + C);
cout << res << endl;
C += res;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
356 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
