#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "debug.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#else
#define debug(...) 42
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
struct DSU
{
vector<int> dsu, val;
DSU(int sz) : dsu(sz+1, -1), val(sz+1, 0) { }
int get(int x) {
if(dsu[x] < 0) {
return x;
}
int par = get(dsu[x]);
val[x] ^= val[dsu[x]];
return dsu[x] = par;
}
int bit(int x) {
get(x);
return val[x];
}
bool merge(int x, int y, int b) {
if(get(x) == get(y)) {
return bit(x) == (bit(y) ^ b);
}
int px = get(x), py = get(y);
const int eb = b ^ bit(x) ^ bit(px) ^ bit(y) ^ bit(py);
if(dsu[px] > dsu[py]) {
swap(x, y);
swap(px, py);
}
dsu[px] += dsu[py];
dsu[py] = x;
val[py] ^= eb;
}
};
struct Node
{
Node *lc, *rc;
int lb, rb, sum, lazy;
Node(int L, int R) : lc(NULL), rc(NULL), lb(L), rb(R), sum(0), lazy(0) { }
void push() {
if(lazy) { sum = rb - lb + 1; }
if(lb == rb) { return; }
const int m = (lb + rb) / 2;
if(!lc) {
lc = new Node(lb, m);
}
if(!rc) {
rc = new Node(m+1, rb);
}
lc->lazy |= lazy;
rc->lazy |= lazy;
return;
}
void add(int L, int R, int x) {
push();
if(rb < L or R < lb) { return; }
debug(lb, rb, sum);
if(L <= lb and rb <= R) {
lazy = 1;
push();
debug("R",lb, rb, sum);
return;
}
lc->add(L, R, x);
rc->add(L, R, x);
sum = lc->sum + rc->sum;
debug("H", lb, rb, sum, lc->sum, rc->sum);
}
int get(int L, int R) {
push();
if(rb < L or R < lb) { return 0; }
debug(lb, rb, sum);
if(L <= lb and rb <= R) {
return sum;
}
return lc->get(L, R) + rc->get(L, R);
}
};
void solve() {
const int inf = 1e9 + 37;
int Q, C = 0;
cin >> Q;
Node* root = new Node(0, inf);
while(Q--) {
int qt, x, y;
cin >> qt >> x >> y;
x += C, y += C;
if(qt == 1) {
debug("getting");
C = root->get(x, y);
cout << C << '\n';
}
else if(qt == 2){
debug("adding");
root->add(x, y, 1);
}
else {
assert(false);
}
}
}
signed main(){
#ifdef LOCAL
freopen("test.err", "w", stderr);
#endif
cin.tie(0)->sync_with_stdio(0);
signed T = 1;
// cin >> T;
for(signed test = 1; test <= T; ++test){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |