#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
template <class T>
struct TreeNode {
T value = 0;
bool lazy = false;
T lazyValue = 0;
TreeNode *leftChild = NULL, *rightChild = NULL;
};
template <class T>
class PersistentSegmentTree {
public:
PersistentSegmentTree(vector<T>& data) : n(data.size()) { root = new TreeNode<T>(); build(root, data, 0, n - 1); }
// n is the max value bound (exclusive), allowed range is [0, n - 1]. // not tested yet
PersistentSegmentTree(int n) : n(n) { root = new TreeNode<T>(); }
// Could be copied to keep history at this moment.
PersistentSegmentTree(const PersistentSegmentTree& pst) : n(pst.n), root(pst.root) {}
// Range update [i, j] to val.
void update(int i, int j, T val) { root = 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); }
void clear() { clear(root); }
private:
int n;
TreeNode<T>* root;
void build(TreeNode<T>* curr, vector<T>& data, int L, int R) {
if (L == R) { curr->value = data[L]; return; }
expand(curr, L, R);
int m = (L + R) / 2;
build(curr->leftChild, data, L, m); build(curr->rightChild, data, m + 1, R);
curr->value = calculate(curr->leftChild->value, curr->rightChild->value);
}
void expand(TreeNode<T>* curr, int L, int R) {
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;
}
TreeNode<T>* 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);
TreeNode<T>* newCurr = new TreeNode<T>();
// copy first
newCurr->leftChild = curr->leftChild; newCurr->rightChild = curr->rightChild;
if (i == L && j == R) {
// case by case 4/4.
newCurr->lazyValue = val;
newCurr->value = (R - L + 1) * val;
newCurr->lazy = true;
return newCurr;
}
int m = (L + R) / 2;
TreeNode<T> *lc = newCurr->leftChild, *rc = newCurr->rightChild;
if (i <= m) { lc = newCurr->leftChild = update(lc, L, m, i, min(m, j), val); }
if (j >= m + 1) { rc = newCurr->rightChild = update(rc, m + 1, R, max(i, m + 1), j, val); }
T lValue = lc->value; T rValue = rc->value;
newCurr->value = calculate(lValue, rValue);
return newCurr;
}
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;
PersistentSegmentTree<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:122:3: note: in expansion of macro 'debug'
122 | debug(n);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
29 ms |
18916 KB |
Output is correct |
| 5 |
Correct |
27 ms |
23016 KB |
Output is correct |
| 6 |
Correct |
30 ms |
23632 KB |
Output is correct |
| 7 |
Correct |
30 ms |
23080 KB |
Output is correct |
| 8 |
Correct |
257 ms |
135012 KB |
Output is correct |
| 9 |
Correct |
516 ms |
259240 KB |
Output is correct |
| 10 |
Runtime error |
491 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Halted |
0 ms |
0 KB |
- |
