#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
struct Vertex{
int sum = 0, lazy_set = 0, tl, tr;
Vertex *lc = nullptr, *rc = nullptr;
Vertex(int lb, int rb){
tl = lb, tr = rb;
}
inline void extend(){
if(!lc){
int mid = (tl + tr) / 2;
lc = new Vertex(tl, mid);
rc = new Vertex(mid + 1, tr);
}
}
inline void propagate(){
extend();
if(!lazy_set) return;
int mid = (tl + tr) / 2;
lc->lazy_set = rc->lazy_set = lazy_set;
lc->sum = (mid - tl + 1) * lazy_set;
rc->sum = (tr - mid) * lazy_set;
lazy_set = 0;
}
void update(int l, int r, int val){
if(r < tl || l > tr) return;
if(r >= tr && l <= tl){
sum = (tr - tl + 1) * val;
lazy_set = val;
return;
}
int mid = (tl + tr) / 2;
propagate();
if(l <= mid)
lc->update(l, r, val);
if(r > mid)
rc->update(l, r, val);
sum = lc->sum + rc->sum;
}
int query(int l, int r){
if(r < tl || l > tr) return 0ll;
if(r >= tr && l <= tl) return sum;
int mid = (tl + tr) / 2, sm1 = 0, sm2 = 0;
propagate();
if(l <= mid)
sm1 = lc->query(l, r);
if(r > mid)
sm2 = lc->query(l, r);
return sm1 + sm2;
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
Vertex st(1, 1e9);
int m, type, l, r, c = 0;
cin >> m;
while(m--){
cin >> type >> l >> r;
if(type == 1){
c = st.query(l + c, r + c);
cout << c << "\n";
}
else{
st.update(l + c, r + c, 1);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
