1.CF817F - MEX Queries

维护两个标记，
    1.区间覆盖(置0，置1)，覆盖时，翻转标记清除
    2.区间翻转，翻转时，如果有覆盖标记，直接翻转覆盖标记，否则，翻转标记取反
维护一个信息：区间和
线段树上二分，区间和小于区间长度，则有0。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,M=N*3;

typedef long long ll;

int n;
struct node{
    int op;
    ll l,r;
}in[N];
vector<ll> alls;

struct node2{
    int la,lb;
    int cnt;
    node2():la(-1),lb(0),cnt(0){}
}tr[M<<2];

int find(ll x){
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void down(int p,int l,int r){
    if(tr[p].la!=-1){
        tr[p<<1].la=tr[p<<1|1].la=tr[p].la;
        tr[p<<1].lb=tr[p<<1|1].lb=0;

        int mid=(l+r)>>1;

        if(tr[p].la==1){
            tr[p<<1].cnt=mid-l+1;
            tr[p<<1|1].cnt=r-mid;
        }
        else tr[p<<1].cnt=tr[p<<1|1].cnt=0;
        tr[p].la=-1;
    }

    if(tr[p].lb){
        int mid=(l+r)>>1;

        if(tr[p<<1].la!=-1) tr[p<<1].la^=1;
        else tr[p<<1].lb^=1;
        tr[p<<1].cnt=mid-l+1-tr[p<<1].cnt;

        if(tr[p<<1|1].la!=-1) tr[p<<1|1].la^=1;
        else tr[p<<1|1].lb^=1;
        tr[p<<1|1].cnt=r-mid-tr[p<<1|1].cnt;
        tr[p].lb=0; 
    }

}

void modify(int p,int l,int r,int L,int R,int op){
    if(L<=l&&r<=R){
        if(op==1){
            tr[p].lb=0;
            tr[p].la=1;
            tr[p].cnt=r-l+1;
        }
        else if(op==2){
            tr[p].lb=0;
            tr[p].la=0;
            tr[p].cnt=0;
        }
        else{
            if(tr[p].la!=-1) tr[p].la^=1;
            else tr[p].lb^=1;
            tr[p].cnt=r-l+1-tr[p].cnt;
        }
        return;
    }

    down(p,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) modify(p<<1,l,mid,L,R,op);
    if(R>=mid+1) modify(p<<1|1,mid+1,r,L,R,op);

    tr[p].cnt=tr[p<<1].cnt+tr[p<<1|1].cnt;
}

int ask(int p,int l,int r){
    if(l==r) {
        return l;   
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(tr[p<<1].cnt<mid-l+1) return ask(p<<1,l,mid);
    return ask(p<<1|1,mid+1,r);
}

int ask2(int p,int l,int r,int x){
    printf("%d %d %d\n",l,r,tr[p].cnt);
    if(l==r) {
        printf("%d, %d\n",alls[l],tr[p].cnt);
        return l;   
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) ask2(p*2,l,mid,x);
    else ask2(p*2+1,mid+1,r,x);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int op;
        ll l,r;
        scanf("%d%lld%lld",&op,&l,&r);
        in[i]={op,l,r};
        alls.push_back(l);
        alls.push_back(r);
        alls.push_back(r+1);
    }
    alls.push_back(1);

    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<n;i++){
        auto &u=in[i];
        int l=find(u.l), r=find(u.r);
        modify(1,0,alls.size()-1,l,r,u.op);
        int p=ask(1,0,alls.size()-1);
        printf("%lld\n",alls[p]);
    }

    return 0; 
}