#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()
const int MAXN = 1e9 + 1;
struct SegTree{
struct Node{
int sum, lazy, lc, rc;
Node(int sum, int lazy, int lc, int rc) : sum(sum), lazy(lazy), lc(lc), rc(rc) {}
Node() : Node(0, 0, -1, -1) {}
};
int idx = 2;
vector<Node> st;
SegTree() : st(2, Node()) {}
inline int extend(){
while(idx >= sz(st)){
st.emplace_back(Node());
}
return idx++;
}
inline void extend(int &c){
if(c == -1){
c = extend();
}
return;
}
inline void combine(int v){
int res = 0;
if(st[v].lc != -1){
res += st[st[v].lc].sum;
}
if(st[v].rc != -1){
res += st[st[v].rc].sum;
}
st[v].sum = res;
return;
}
inline void apply(int v, int val, int len){
st[v].sum = len * val;
st[v].lazy = val;
return;
}
inline void propagate(int v, int tl, int mid, int tr){
if(st[v].lazy){
if(st[v].lc == -1){
st[v].lc = extend();
}
if(st[v].rc == -1){
st[v].rc = extend();
}
apply(st[v].lc, st[v].lazy, mid - tl + 1);
apply(st[v].rc, st[v].lazy, tr - (mid + 1) + 1);
st[v].lazy = 0;
}
return;
}
inline void update(int ul, int ur, int val, int v, int tl, int tr){
if(ul > tr || tl > ur) return;
if(ul <= tl && tr <= ur){
apply(v, val, tr - tl + 1);
return;
}
int mid = (tl + tr) >> 1;
propagate(v, tl, mid, tr);
if(ul <= mid){
if(st[v].lc == -1){
st[v].lc = extend();
}
update(ul, ur, val, st[v].lc, tl, mid);
}
if(mid + 1 <= ur){
if(st[v].rc == -1){
st[v].rc = extend();
}
update(ul, ur, val, st[v].rc, mid + 1, tr);
}
combine(v);
return;
}
inline int query(int ql, int qr, int v, int tl, int tr){
if(ql > tr || tl > qr) return 0ll;
if(ql <= tl && tr <= qr) return st[v].sum;
int mid = (tl + tr) >> 1;
propagate(v, tl, mid, tr);
if(ql <= mid && mid + 1 <= qr){
if(st[v].lc == -1){
st[v].lc = extend();
}
if(st[v].rc == -1){
st[v].rc = extend();
}
return query(ql, qr, st[v].lc, tl, mid) + query(ql, qr, st[v].rc, mid + 1, tr);
}
else if(ql <= mid){
if(st[v].lc == -1){
st[v].lc = extend();
}
return query(ql, qr, st[v].lc, tl, mid);
}
else{
if(st[v].rc == -1){
st[v].rc = extend();
}
return query(ql, qr, st[v].rc, mid + 1, tr);
}
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int m, c = 0;
cin >> m;
SegTree st;
while(m--){
int d, l, r;
cin >> d >> l >> r;
if(d == 1){
l += c, r += c;
c = st.query(l, r, 1, 1, MAXN);
cout << c << "\n";
}
else{
l += c, r += c;
st.update(l, r, 1, 1, 1, MAXN);
}
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |