DYNAMIC SEGMENT TREE FOR MEX

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int64 VMAX = 1e18L;

struct node {
  int64 sum, l, r;
  node *lSon, *rSon;
  short lazy_set;
  bool lazy_xor;
  node() : sum(0), lSon(nullptr), rSon(nullptr), lazy_set(-1), lazy_xor(false) {}
};

int nodes = 1;

void add_left(node *&x) {
  if (x->lSon == nullptr) {
    x->lSon = new node();
    int64 mid = (x->l + x->r) >> 1;
    x->lSon->l = x->l;
    x->lSon->r = mid;
  }
}

void add_right(node *&x) {
  if (x->rSon == nullptr) {
    x->rSon = new node();
    int64 mid = (x->l + x->r) >> 1;
    x->rSon->l = mid + 1;
    x->rSon->r = x->r;
  }
}

void propagate(node *&x) {
  if (x->lazy_set != -1) {
    add_left(x);
    x->lSon->sum = (x->lSon->r - x->lSon->l + 1) * x->lazy_set;
    add_right(x);
    x->rSon->sum = (x->rSon->r - x->rSon->l + 1) * x->lazy_set;
    x->lSon->lazy_xor = x->rSon->lazy_xor = 0;
    x->lSon->lazy_set = x->rSon->lazy_set = x->lazy_set;
    x->lazy_set = -1;
  }
  if (x->lazy_xor) {
    add_left(x);
    x->lSon->sum = (x->lSon->r - x->lSon->l + 1) - x->lSon->sum;
    x->lSon->lazy_xor ^= 1;
    add_right(x);
    x->rSon->sum = (x->rSon->r - x->rSon->l + 1) - x->rSon->sum;
    x->rSon->lazy_xor ^= 1;
    x->lazy_xor = 0;
  }
}

void update_sum(node *&x) {
  x->sum = 0;
  if (x->lSon != nullptr)
    x->sum += x->lSon->sum;
  if (x->rSon != nullptr)
    x->sum += x->rSon->sum;
}

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

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

int64 query(node *&x) {
  if (x->l == x->r)
    return x->l;
  propagate(x);
  add_left(x);
  if (x->lSon->sum == 0)
    return x->lSon->l;
  if (x->lSon->sum < x->lSon->r - x->lSon->l + 1)
    return query(x->lSon);
  add_right(x);
  if (x->rSon->sum == 0)
    return x->rSon->l;
  if (x->rSon->sum < x->rSon->r - x->rSon->l + 1)
    return query(x->rSon);
  return VMAX + 1;
}

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