#include <bits/stdc++.h>
#define N 100000
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
using namespace std;
typedef string str;
typedef pair<int,int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iv;
const int inf = 1e9;
const int MOD = 1e9 + 7;
const bool multi_test = false;
const string NAME = "VOI";
struct node {
int sum, lazy, tl, tr, l, r;
node() : sum(0), lazy(0), l(-1), r(-1) {}
};
struct sparse_segment_tree{
int cnt;
node st[50*N+5];
void init(){
cnt = 1;
st[cnt].tl = 1;
st[cnt].tr = 1e9;
}
void down_lazy(int id){
if (st[id].lazy){
int mid = (st[id].tl + st[id].tr) / 2;
if (st[id].l == -1){
st[id].l = ++cnt;
st[cnt].tl = st[id].tl;
st[cnt].tr = mid;
}
if (st[id].r == -1){
st[id].r = ++cnt;
st[cnt].tl = mid + 1;
st[cnt].tr = st[id].tr;
}
st[st[id].l].sum = mid - st[id].tl + 1;
st[st[id].r].sum = st[id].tr - mid;
st[st[id].l].lazy = st[st[id].r].lazy = 1;
st[id].lazy = 0;
}
}
void update(int u, int v, int id = 1){
int l = st[id].tl, r = st[id].tr;
if (l > v || r < u) return;
if (u <= l && r <= v) {
st[id].sum = r - l + 1;
st[id].lazy = 1;
return;
}
int mid = (l + r) >> 1;
down_lazy(id);
if (st[id].l == -1){
st[id].l = ++cnt;
st[cnt].tl = l;
st[cnt].tr = mid;
// cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl;
}
if (st[id].r == -1){
st[id].r = ++cnt;
st[cnt].tl = mid + 1;
st[cnt].tr = r;
// cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl;
}
// cout << u << " " << v << " " << l << " " << r << " " << id << " " << st[id].l << " " << st[id].r << endl;
update(u, v, st[id].l);
update(u, v, st[id].r);
st[id].sum = st[st[id].l].sum + st[st[id].r].sum;
}
int querry(int u, int v, int id = 1){
int l = st[id].tl, r = st[id].tr;
if (l > v || r < u) return 0;
if (u <= l && r <= v) return st[id].sum;
int mid = (l + r) >> 1;
down_lazy(id);
if (st[id].l == -1){
st[id].l = ++cnt;
st[cnt].tl = l;
st[cnt].tr = mid;
}
if (st[id].r == -1){
st[id].r = ++cnt;
st[cnt].tl = mid + 1;
st[cnt].tr = r;
}
return querry(u, v, st[id].l) + querry(u, v, st[id].r);
}
};
int n;
sparse_segment_tree st;
void solve(){
cin >> n;
st.init();
int c = 0;
while (n--){
int d, x, y;
cin >> d >> x >> y;
if (d == 1) {
c = st.querry(x + c, y + c);
cout << c << '\n';
} else {
st.update(x + c, y + c);
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1;
if (multi_test) cin >> t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
235088 KB |
Output is correct |
| 2 |
Correct |
29 ms |
235140 KB |
Output is correct |
| 3 |
Correct |
30 ms |
235092 KB |
Output is correct |
| 4 |
Correct |
36 ms |
235092 KB |
Output is correct |
| 5 |
Correct |
38 ms |
235248 KB |
Output is correct |
| 6 |
Correct |
38 ms |
235084 KB |
Output is correct |
| 7 |
Correct |
38 ms |
235276 KB |
Output is correct |
| 8 |
Correct |
89 ms |
235408 KB |
Output is correct |
| 9 |
Correct |
169 ms |
235504 KB |
Output is correct |
| 10 |
Correct |
184 ms |
235780 KB |
Output is correct |
| 11 |
Correct |
173 ms |
235584 KB |
Output is correct |
| 12 |
Correct |
171 ms |
235536 KB |
Output is correct |
| 13 |
Correct |
149 ms |
235608 KB |
Output is correct |
| 14 |
Correct |
147 ms |
235528 KB |
Output is correct |
| 15 |
Correct |
205 ms |
235664 KB |
Output is correct |
| 16 |
Correct |
207 ms |
235600 KB |
Output is correct |
| 17 |
Correct |
152 ms |
235788 KB |
Output is correct |
| 18 |
Correct |
145 ms |
235536 KB |
Output is correct |
| 19 |
Correct |
203 ms |
235544 KB |
Output is correct |
| 20 |
Correct |
201 ms |
235912 KB |
Output is correct |
