DYNAMIC SEGMENT TREE FOR MEX - STATIC

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int MAXN = 1e5;
const int LOG = 60;
const int64 VMAX = 1e18L;

struct node {
  int64 sum, l, r;
  int lSon, rSon;
  short lazy_set;
  bool lazy_xor;
  node() : sum(0), lSon(-1), rSon(-1), lazy_set(-1), lazy_xor(false) {}
} tree[MAXN * LOG];

int nodes = 1;

void add_left(int x) {
  int64 mid = (tree[x].l + tree[x].r) >> 1;
  if (tree[x].lSon == -1) {
    tree[x].lSon = ++nodes;
    tree[nodes].l = tree[x].l;
    tree[nodes].r = mid;
  }
}

void add_right(int x) {
  int64 mid = (tree[x].l + tree[x].r) >> 1;
  if (tree[x].rSon == -1) {
    tree[x].rSon = ++nodes;
    tree[nodes].l = mid + 1;
    tree[nodes].r = tree[x].r;
  }
}

void propagate(int x) {
  if (tree[x].lazy_set != -1) {
    add_left(x);
    int son = tree[x].lSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) * tree[x].lazy_set;
    tree[son].lazy_xor = 0;
    tree[son].lazy_set = tree[x].lazy_set;
    add_right(x);
    son = tree[x].rSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) * tree[x].lazy_set;
    tree[son].lazy_xor = 0;
    tree[son].lazy_set = tree[x].lazy_set;
    tree[x].lazy_set = -1;
  }
  if (tree[x].lazy_xor) {
    add_left(x);
    int son = tree[x].lSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) - tree[son].sum;
    tree[son].lazy_xor ^= 1;
    add_right(x);
    son = tree[x].rSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) - tree[son].sum;
    tree[son].lazy_xor ^= 1;
    tree[x].lazy_xor = 0;
  }
}

void update_sum(int x) {
  tree[x].sum = 0;
  if (tree[x].lSon != -1)
    tree[x].sum += tree[tree[x].lSon].sum;
  if (tree[x].rSon != -1)
    tree[x].sum += tree[tree[x].rSon].sum;
}

void range_set(int x, int64 st, int64 dr, bool val) {
  if (st <= tree[x].l && tree[x].r <= dr) {
    tree[x].sum = (tree[x].r - tree[x].l + 1) * val;
    tree[x].lazy_xor = 0;
    tree[x].lazy_set = val;
    return;
  }
  propagate(x);
  int64 mid = (tree[x].l + tree[x].r) >> 1;
  if (st <= mid) {
    add_left(x);
    range_set(tree[x].lSon, st, dr, val);
  }
  if (mid < dr) {
    add_right(x);
    range_set(tree[x].rSon, st, dr, val);
  }
  update_sum(x);
}

void range_xor(int x, int64 st, int64 dr) {
  if (st <= tree[x].l && tree[x].r <= dr) {
    tree[x].sum = (tree[x].r - tree[x].l + 1) - tree[x].sum;
    tree[x].lazy_xor ^= 1;
    return;
  }
  propagate(x);
  int64 mid = (tree[x].l + tree[x].r) >> 1;
  if (st <= mid) {
    add_left(x);
    range_xor(tree[x].lSon, st, dr);
  }
  if (mid < dr) {
    add_right(x);
    range_xor(tree[x].rSon, st, dr);
  }
  update_sum(x);
}

int64 query(int x) {
  if (tree[x].l == tree[x].r)
    return tree[x].l;
  propagate(x);
  int64 mid = (tree[x].l + tree[x].r) >> 1;
  add_left(x);
  int son = tree[x].lSon;
  if (tree[son].sum == 0)
    return tree[son].l;
  if (tree[son].sum < tree[son].r - tree[son].l + 1)
    return query(son);
  add_right(x);
  son = tree[x].rSon;
  if (tree[son].sum == 0)
    return tree[son].l;
  if (tree[son].sum < tree[son].r - tree[son].l + 1)
    return query(son);
  return VMAX + 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N;
  cin >> N;
  tree[1].sum = 0;
  tree[1].l = 1;
  tree[1].r = VMAX;
  for (int i = 0; i < N; ++i) {
    int t;
    int64 l, r;
    cin >> t >> l >> r;
    if (t < 3)
      range_set(1, l, r, (t == 1));
    else range_xor(1, l, r);
    cout << query(1) << '\n';
  }
  return 0;
}