#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct SegmentTree {
private:
int acc = 0, lazy = 0; // implicitly 0
SegmentTree* left_child, * right_child;
int tl, tr; // left and right endpoint of segment (inclusive)
public:
SegmentTree(int left, int right) {
tl = left;
tr = right;
}
SegmentTree(vector<int>& a) {
tl = 0; tr = (int)a.size() - 1;
for (int i = 0; i <= tr; ++i) {
point_update(i, a[i]);
}
}
int merge_function(int a, int b) {
return a + b;
}
int merge() {
int tm = tl + (tr - tl) / 2;
return merge_function(
left_child->query(tl, tm),
right_child->query(tm + 1, tr)
);
}
void point_update(int position, int value) {
push();
if (tl == tr) {
acc = value;
} else {
int tm = tl + (tr - tl) / 2;
if (position <= tm)
left_child->point_update(position, value);
else
right_child->point_update(position, value);
acc = merge();
}
}
void update(int l, int r) {
push();
if (l == tl && tr == r) {
lazy = 1;
} else {
int tm = tl + (tr - tl) / 2;
if (r <= tm) left_child->update(l, r);
else if (l > tm) right_child->update(l, r);
else {
left_child->update(l, tm);
right_child->update(tm + 1, r);
}
acc = merge();
}
}
int query(int l, int r) {
push();
if (l == tl && tr == r) return acc;
int tm = tl + (tr - tl) / 2;
if (r <= tm) return left_child->query(l, r);
if (l > tm) return right_child->query(l, r);
return merge();
}
void push() {
construct_children();
if (lazy) {
acc = tr - (tl - 1);
if (tl < tr) {
left_child->lazy = lazy;
right_child->lazy = lazy;
}
lazy = 0;
}
}
void construct_children() {
if (tl == tr) return;
int tm = tl + (tr - tl) / 2;
if (!left_child) left_child = new SegmentTree(tl, tm);
if (!right_child) right_child = new SegmentTree(tm + 1, tr);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
SegmentTree tree(1, (int)1e9);
int M;
cin >> M;
int C = 0;
while (M--) {
int D, X, Y;
cin >> D >> X >> Y;
if (D == 1) {
C = tree.query(X + C, Y + C);
cout << C << endl;
} else {
tree.update(X + C, Y + C);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
