## MEX Queries

### 题目描述

You are given a set of integer numbers, initially it is empty. You should perform $n$ queries.

There are three different types of queries:

• $1\ l\ r$ — Add all missing numbers from the interval $[l,r]$
• $2\ l\ r$ — Remove all present numbers from the interval $[l,r]$
• $3\ l\ r$ — Invert the interval $[l,r]$ — add all missing and remove all present numbers from the interval $[l,r]$
After each query you should output MEX of the set — the smallest positive ($MEX \ge 1$) integer number which is not presented in the set.

### 输入格式

The first line contains one integer number $n$ ($1 \le n \le 10^5$).
Next $n$ lines contain three integer numbers $t,l,r$ ($1 \le t \le 3$,$1 \le l \le r \le 10^{18}$) — type of the query, left and right bounds.

### 输出格式

Print $MEX$ of the set after each query.

### 样例输入1

3
1 3 4
3 1 6
2 1 3


### 样例输出1

1
3
1


### 样例输入2

4
1 1 3
3 5 6
2 4 4
3 1 6


### 样例输出2

4
4
4
1


## 题解

#include<bits/stdc++.h>
using namespace std;
int n;
struct aa{
int t;
long long l,r;
}a[500009];
int lt=1;
struct cc{
long long s;
int from;
bool k;
}to[500009];
struct bb{
int x;
int ld;
}p[4000009];
bool cmp(cc x,cc y){return x.s<y.s;}
void dn(int u,int l,int r){
if(p[u].ld&(1<<2)){
p[u*2].ld=p[u*2+1].ld=(1<<2);
p[u].x=r-l;
}
if(p[u].ld&(1<<1)){
p[u*2].ld=p[u*2+1].ld=(1<<1);
p[u].x=0;
}
if(p[u].ld&1){
p[u].x=r-l-p[u].x;
if(p[u*2].ld&(1<<2)) p[u*2].ld=(1<<1);
else if(p[u*2].ld&(1<<1)) p[u*2].ld=(1<<2);
else p[u*2].ld^=1;
if(p[u*2+1].ld&(1<<2)) p[u*2+1].ld=(1<<1);
else if(p[u*2+1].ld&(1<<1)) p[u*2+1].ld=(1<<2);
else p[u*2+1].ld^=1;
}
p[u].ld=0;
}
void dfs(int u,int l,int r,int x){
dn(u,l,r);
if(r<=a[x].l || l>=a[x].r) return;
if(l>=a[x].l && r<=a[x].r){
p[u].ld=(1<<(3-a[x].t));
dn(u,l,r);
if(r==l+1) return;
dn(u*2,l,(l+r)/2);
dn(u*2+1,(l+r)/2,r);
p[u].x=p[u*2].x+p[u*2+1].x;
return;
}
if(r==l+1) return;
dfs(u*2,l,(l+r)/2,x);
dfs(u*2+1,(l+r)/2,r,x);
p[u].x=p[u*2].x+p[u*2+1].x;
}
void fd(int u,int l,int r){
dn(u,l,r);
if(p[u].x==0){
printf("%lld\n",to[l].s);
return;
}
else if(p[u].x==r-l){
printf("%lld\n",to[r].s);
return;
}else{
dn(u*2,l,(l+r)/2);
if(p[u*2].x==(l+r)/2-l) fd(u*2+1,(l+r)/2,r);
else fd(u*2,l,(l+r)/2);
}
}
int main(){
scanf("%d",&n);
for(int j=1;j<=n;j++){
scanf("%d%lld%lld",&a[j].t,&a[j].l,&a[j].r);
a[j].r++;
to[j*2-1].s=a[j].l;
to[j*2-1].from=j;
to[j*2].s=a[j].r;
to[j*2].from=j;
to[j*2].k=1;
}
to[n*2+1].s=1;
sort(to+1,to+n*2+2,cmp);
if(to[1].k) a[to[1].from].r=1;
else a[to[1].from].l=1;
for(int j=2;j<=n*2+1;j++){
if(to[j].s!=to[lt].s) to[++lt]=to[j];
if(to[j].k) a[to[j].from].r=lt;
else a[to[j].from].l=lt;
}
for(int j=1;j<=n;j++){
dfs(1,1,lt,j);
fd(1,1,lt);
}
return 0;
}