#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
const long MAXN = 200000;
struct node{
int sum, lazy;
node *left, *right;
node(int v = 0, int l = 0) : sum(v), lazy(l), left(nullptr), right(nullptr) {}
};
void apply(node*& v){
if(!v) v = new node();
v->lazy = 1;
}
void update(node*& v, int l, int r, int a, int b){
if(!v) v = new node();
if(v->lazy == 1){
v->sum = r - l + 1;
if(l != r){
apply(v->left);
apply(v->right);
}
v->lazy = 0;
}
if(l > b or r < a) return;
if(l >= a and r <= b){
v->sum = r - l + 1;
if(l != r){
apply(v->left);
apply(v->right);
}
return;
}
int m = (l + r)/2;
update(v->left, l, m, a, b);
update(v->right, m + 1, r, a, b);
v->sum = v->left->sum + v->right->sum;
return;
}
int query(node*& v, int l, int r, int a, int b){
if(!v) v = new node();
if(v->lazy == 1){
v->sum = r - l + 1;
if(l != r){
apply(v->left);
apply(v->right);
}
v->lazy = 0;
}
if(l > b or r < a) return 0;
if(l >= a and r <= b) return v->sum;
int m = (l + r)/2;
return query(v->left, l, m, a, b) + query(v->right, m + 1, r, a, b);
}
int main(){
int M, C = 0;
cin >> M;
node *root = new node();
for(int i = 0; i < M; i++){
int d, l, r;
cin >> d >> l >> r;
if(d == 1){
C = query(root, 0, 1e9 - 1, l + C, r + C);
cout << C << "\n";
}
else{
update(root, 0, 1e9 - 1, l + C, r + C);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |