#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};
};
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) { update(0, 0, n-1, i, j, val); }
// Range query [i, j].
T query(int i, int j) { return query(0, 0, n-1, i, j); }
private:
int n;
vector<TreeNode<T>> st;
int leftChild(int index) {
if (!st[index].children[0]) {
st.emplace_back();
st[index].children[0] = st.size() - 1;
}
return st[index].children[0];
}
int rightChild(int index) {
if (!st[index].children[1]) {
st.emplace_back();
st[index].children[1] = st.size() - 1;
}
return st[index].children[1];
}
T calculate(T v1, T v2) {
return v1 + v2; // case by case 1/4.
}
void build() {
st.emplace_back();
}
// 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;
}
void 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.
st[index].lazyValue = val; st[index].value = (R - L + 1) * val;
st[index].lazy = true; return;
}
int m = (L + R) / 2;
int lc = leftChild(index); int rc = rightChild(index);
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 = st[lc].value; T rValue = st[rc].value;
st[index].value = calculate(lValue, rValue);
}
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:117:3: note: in expansion of macro 'debug'
117 | 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 |
212 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3144 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5740 KB |
Output is correct |
| 6 |
Correct |
11 ms |
5760 KB |
Output is correct |
| 7 |
Correct |
11 ms |
5748 KB |
Output is correct |
| 8 |
Correct |
81 ms |
42416 KB |
Output is correct |
| 9 |
Correct |
167 ms |
42444 KB |
Output is correct |
| 10 |
Correct |
181 ms |
84572 KB |
Output is correct |
| 11 |
Correct |
190 ms |
84572 KB |
Output is correct |
| 12 |
Correct |
193 ms |
84432 KB |
Output is correct |
| 13 |
Correct |
169 ms |
84444 KB |
Output is correct |
| 14 |
Correct |
170 ms |
84464 KB |
Output is correct |
| 15 |
Correct |
275 ms |
166808 KB |
Output is correct |
| 16 |
Correct |
276 ms |
166888 KB |
Output is correct |
| 17 |
Correct |
174 ms |
84424 KB |
Output is correct |
| 18 |
Correct |
186 ms |
84624 KB |
Output is correct |
| 19 |
Correct |
267 ms |
166792 KB |
Output is correct |
| 20 |
Correct |
277 ms |
166656 KB |
Output is correct |
