#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int lc, rc, sum, lz;
node(){
lc = rc = -1;
sum = lz = 0;
}
};
vector<node> bit;
void acc(int id){
if (bit[id].lc == -1){
bit[id].lc = (int) bit.size();
bit.push_back(node());
}
if (bit[id].rc == -1){
bit[id].rc = (int) bit.size();
bit.push_back(node());
}
}
void add(int id, int l, int r, int val){
bit[id].sum = val * (r - l + 1);
bit[id].lz = val;
}
void down(int id, int l, int r){
if (l == r || bit[id].lz == 0) return;
acc(id);
int mid = (l + r) >> 1;
add(bit[id].lc, l, mid, bit[id].lz);
add(bit[id].rc, mid + 1, r, bit[id].lz);
bit[id].lz = 0;
}
void ud(int id, int l, int r, int u, int v, int val){
if (l > v || r < u) return;
if (l >= u && r <= v){
add(id, l, r, val);
return;
}
int mid = (l + r) >> 1;
acc(id);
down(id, l, r);
ud(bit[id].lc, l, mid, u, v, val);
ud(bit[id].rc, mid + 1, r, u, v, val);
bit[id].sum = bit[bit[id].lc].sum + bit[bit[id].rc].sum;
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (l >= u && r <= v) return bit[id].sum;
int mid = (l + r) >> 1;
down(id, l, r);
int t = 0, tt = 0;
if (bit[id].lc != -1) t = get(bit[id].lc, l, mid, u, v);
if (bit[id].rc != -1) tt = get(bit[id].rc, mid + 1, r, u, v);
return (t + tt);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
bit.push_back(node());
int c = 0;
int q;
int n = 1e9;
cin >> q;
while (q--){
int typ, l, r;
cin >> typ >> l >> r;
l += c; r += c;
if (typ == 1){
int t = get(0, 1, n, l, r);
c += t;
cout << t << "\n";
continue;
}
ud(0, 1, n, l, r, 1);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
