#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 88
#define dout if (0) cout
#endif
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (int i=0;i<a.size();i++) cin>>a[i]; return cin; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define RE(i, n) for (int i = 0; i < n; i++)
#define RE2(i, start, n) for (int i = start; i < n; i++)
// #define MULTI_CASES
// #define LOCAL_MULTI_CASES
// SparseSegmentTree (Dynamic SegmentTree), with lazy propagate.
// Similar to above, only with dynamic allocate space for children nodes.
template <class T>
struct TreeNode {
T value = 0;
bool lazy = false;
T lazyValue = 0;
TreeNode *leftChild = NULL, *rightChild = NULL;
};
template <class T>
class SparseSegmentTree {
public:
// n is the max value bound (exclusive), allowed range is [0, n - 1].
SparseSegmentTree(int n) : n(n) { root = build(); }
// Range update [i, j] to val.
void update(int i, int j, T val) { update(root, 0, n - 1, i, j, val); }
// Range query [i, j].
T query(int i, int j) { return query(root, 0, n - 1, i, j); }
private:
int n;
TreeNode<T>* root;
TreeNode<T>* build() {
return new TreeNode<T>();
}
void expand(TreeNode<T>* curr, int L, int R) {
int m = (L + R) / 2;
if (!curr->leftChild) { curr->leftChild = new TreeNode<T>(); }
if (!curr->rightChild) { curr->rightChild = new TreeNode<T>(); }
}
T calculate(T v1, T v2) {
return v1 + v2; // case by case 1/4.
}
// propagate lazy value one level down.
void propagate(TreeNode<T>* curr, int L, int R) {
if (!curr->lazy) return;
if (L == R) {
// case by case 2/4.
// data[L] += curr->lazyValue; // leaf node; time to update.
} else {
TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild; int m = (L + R) / 2;
lc->lazy = rc->lazy = true;
// case by case 3/4.
lc->lazyValue = curr->lazyValue;
rc->lazyValue = curr->lazyValue;
lc->value = (m - L + 1) * curr->lazyValue;
rc->value = (R - (m + 1) + 1) * curr->lazyValue;
}
curr->lazy = false; curr->lazyValue = 0;
}
void update(TreeNode<T>* curr, int L, int R, int i, int j, T val) {
assert(L <= i && i <= j && j <= R);
expand(curr, L, R);
propagate(curr, L, R);
if (i == L && j == R) {
// case by case 4/4.
curr->lazyValue = val;
curr->value = (R - L + 1) * val;
curr->lazy = true; return;
}
int m = (L + R) / 2;
TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild;
if (i <= m) { update(lc, L, m, i, min(m, j), val); }
if (j >= m + 1) { update(rc, m + 1, R, max(i, m + 1), j, val); }
T lValue = lc->value; T rValue = rc->value;
curr->value = calculate(lValue, rValue);
}
T query(TreeNode<T>* curr, int L, int R, int i, int j) {
assert(L <= i && i <= j && j <= R);
T ans;
if (i == L && j == R) {
ans = curr->value;
} else {
expand(curr, L, R);
propagate(curr, L, R); int m = (L + R) / 2;
TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild;
if (j <= m) { ans = query(lc, L, m, i, j);
} else if (i >= m + 1) { ans = query(rc, m + 1, R, i, j);
} else {
T lValue = query(lc, L, m, i, m);
T rValue = query(rc, m + 1, R, m + 1, j);
ans = calculate(lValue, rValue);
}
}
return ans;
}
};
void solve() {
int n;
cin >> n;
debug(n);
int preans = 0;
SparseSegmentTree<int> st(1000000000);
RE(i, n) {
int type, x, y;
cin >> type >> x >> y;
x += preans; y += preans;
x--; y--;
if (type == 1) {
// query
preans = st.query(x, y);
cout << preans << "\n";
} else {
assert(type == 2);
// update
st.update(x, y, 1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int cases = 1;
#if defined MULTI_CASES || (defined LOCAL && defined LOCAL_MULTI_CASES)
cin >> cases;
#endif
for (int i = 0; i < cases; i++) {
dout << "cases: " << i + 1 << endl;
solve();
dout << endl;
}
return 0;
}
Compilation message
apple.cpp: In function 'void solve()':
apple.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 88
| ^~
apple.cpp:113:3: note: in expansion of macro 'debug'
113 | debug(n);
| ^~~~~
apple.cpp: In instantiation of 'void SparseSegmentTree<T>::expand(TreeNode<T>*, int, int) [with T = int]':
apple.cpp:95:7: required from 'T SparseSegmentTree<T>::query(TreeNode<T>*, int, int, int, int) [with T = int]'
apple.cpp:37:39: required from 'T SparseSegmentTree<T>::query(int, int) [with T = int]'
apple.cpp:124:29: required from here
apple.cpp:46:9: warning: unused variable 'm' [-Wunused-variable]
46 | int m = (L + R) / 2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
5972 KB |
Output is correct |
| 5 |
Correct |
15 ms |
7268 KB |
Output is correct |
| 6 |
Correct |
19 ms |
7100 KB |
Output is correct |
| 7 |
Correct |
13 ms |
7244 KB |
Output is correct |
| 8 |
Correct |
134 ms |
55236 KB |
Output is correct |
| 9 |
Correct |
250 ms |
95968 KB |
Output is correct |
| 10 |
Correct |
257 ms |
106112 KB |
Output is correct |
| 11 |
Correct |
268 ms |
113896 KB |
Output is correct |
| 12 |
Correct |
282 ms |
117420 KB |
Output is correct |
| 13 |
Correct |
275 ms |
135244 KB |
Output is correct |
| 14 |
Correct |
228 ms |
136980 KB |
Output is correct |
| 15 |
Correct |
428 ms |
250916 KB |
Output is correct |
| 16 |
Correct |
389 ms |
252492 KB |
Output is correct |
| 17 |
Correct |
241 ms |
141712 KB |
Output is correct |
| 18 |
Correct |
285 ms |
141712 KB |
Output is correct |
| 19 |
Correct |
392 ms |
258164 KB |
Output is correct |
| 20 |
Correct |
406 ms |
258264 KB |
Output is correct |
