#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;
bool lazy = false;
T lazyValue = 0;
array<int, 2> children = {0, 0};
};
vector<TreeNode<int>> st;
int createTreeNode() { // returns the index
st.emplace_back();
return st.size() - 1;
}
template <class T>
class SparseSegmentTree {
public:
SparseSegmentTree(int n) : n(n) { build(); }
// 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); }
private:
int n;
int root;
void build() {
root = createTreeNode();
}
int leftChild(int index) {
// dynamic allocate child node
if (!st[index].children[0]) { st[index].children[0] = createTreeNode(); }
return st[index].children[0];
}
int rightChild(int index) {
// dynamic allocate child node
if (!st[index].children[1]) { st[index].children[1] = createTreeNode(); }
return st[index].children[1];
}
T calculate(T v1, T v2) {
return v1 + v2; // case by case 1/4.
}
// propagate lazy value one level down.
void propagate(int index, int L, int R) {
if (!st[index].lazy) return;
if (L == R) {
// case by case 2/4.
// data[L] += st[index].lazyValue; // leaf node; time to update.
} else {
int lc = leftChild(index); int rc = rightChild(index); int m = (L + R) / 2;
st[lc].lazy = st[rc].lazy = true;
// case by case 3/4.
st[lc].lazyValue = st[index].lazyValue;
st[rc].lazyValue = st[index].lazyValue;
st[lc].value = (m - L + 1) * st[index].lazyValue;
st[rc].value = (R - (m + 1) + 1) * st[index].lazyValue;
}
st[index].lazy = false; st[index].lazyValue = 0;
}
int update(int index, int L, int R, int i, int j, T val) {
assert(L <= i && i <= j && j <= R);
propagate(index, L, R);
if (i == L && j == R) {
// case by case 4/4.
int newIndex = createTreeNode();
// st[newIndex] = st[index]; // No copy, as children should not be re-used.
st[newIndex].lazyValue = val; st[newIndex].value = (R - L + 1) * val;
st[newIndex].lazy = true;
return newIndex;
}
int m = (L + R) / 2;
int lc = leftChild(index); int rc = rightChild(index);
int newIndex = createTreeNode();
st[newIndex] = st[index]; // copy first to re-use some non-updated child in the following
if (i <= m) {
st[newIndex].children[0] = lc = update(lc, L, m, i, min(m, j), val);
}
if (j >= m + 1) {
st[newIndex].children[1] = rc = update(rc, m + 1, R, max(i, m + 1), j, val);
}
T lValue = st[lc].value; T rValue = st[rc].value;
st[newIndex].value = calculate(lValue, rValue);
return newIndex;
}
T query(int index, int L, int R, int i, int j) {
assert(L <= i && i <= j && j <= R);
T ans;
if (i == L && j == R) {
ans = st[index].value;
} else {
propagate(index, L, R); int m = (L + R) / 2;
int lc = leftChild(index); int rc = rightChild(index);
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:129:3: note: in expansion of macro 'debug'
129 | debug(n);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
1040 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
