思路

下次记住，这种求mex一类哪个没有出现的都可以用值域线段树维护一个sz然后树上二分的
我为啥偏偏要维护每个节点对应区间的第一个未出现的0和1的位置啊（捂脸
我是傻逼，这样难写还难调

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
struct Node{
    int firz,firo,lson,rson,allz,allo,inv,set,lx,rx,midx;
}Seg[500000<<2];//0 特殊处理
struct Ask{
    int opt,l,r;
}qx[110000];
int Nodecnt,root,pos[500000],cnt,aft_cnt,n;
void pushup(int o){
    Seg[o].allo=Seg[Seg[o].lson].allo&&Seg[Seg[o].rson].allo;
    Seg[o].allz=Seg[Seg[o].lson].allz&&Seg[Seg[o].rson].allz;
    Seg[o].firo=min(Seg[Seg[o].lson].firo,Seg[Seg[o].rson].firo);
    Seg[o].firz=min(Seg[Seg[o].lson].firz,Seg[Seg[o].rson].firz);
}
int New_Node(int l,int mid,int r){
    ++Nodecnt;
    Seg[Nodecnt].allo=0;
    Seg[Nodecnt].allz=1;
    Seg[Nodecnt].firo=9000000000000000000LL;
    Seg[Nodecnt].firz=l;
    Seg[Nodecnt].inv=0;
    Seg[Nodecnt].lx=l;
    Seg[Nodecnt].rx=r;
    Seg[Nodecnt].set=-1;
    Seg[Nodecnt].midx=mid;
    return Nodecnt;
}
void pushdown(int o){
    if(Seg[o].inv){
        swap(Seg[Seg[o].lson].allo,Seg[Seg[o].lson].allz);
        swap(Seg[Seg[o].lson].firo,Seg[Seg[o].lson].firz);
        swap(Seg[Seg[o].rson].allo,Seg[Seg[o].rson].allz);
        swap(Seg[Seg[o].rson].firo,Seg[Seg[o].rson].firz);
        if(Seg[Seg[o].lson].set!=-1)
            Seg[Seg[o].lson].set^=1;
        else
            Seg[Seg[o].lson].inv^=1;
        if(Seg[Seg[o].rson].set!=-1)
            Seg[Seg[o].rson].set^=1;
        else
            Seg[Seg[o].rson].inv^=1;
        Seg[o].inv=0;
    }
    if(Seg[o].set!=-1){
        if(Seg[o].set==0){
            Seg[Seg[o].lson].allo=0;
            Seg[Seg[o].lson].allz=1;
            Seg[Seg[o].lson].firo=9000000000000000000LL;
            Seg[Seg[o].lson].firz=Seg[Seg[o].lson].lx;
            Seg[Seg[o].lson].set=Seg[o].set; 
            Seg[Seg[o].lson].inv=0;
            Seg[Seg[o].rson].allo=0;
            Seg[Seg[o].rson].allz=1;
            Seg[Seg[o].rson].firo=9000000000000000000LL;
            Seg[Seg[o].rson].firz=Seg[Seg[o].rson].lx;
            Seg[Seg[o].rson].set=Seg[o].set; 
            Seg[Seg[o].rson].inv=0;
        }   
        if(Seg[o].set==1){
            Seg[Seg[o].lson].allo=1;
            Seg[Seg[o].lson].allz=0;
            Seg[Seg[o].lson].firo=Seg[Seg[o].lson].lx;
            Seg[Seg[o].lson].firz=9000000000000000000LL;
            Seg[Seg[o].lson].set=Seg[o].set; 
            Seg[Seg[o].lson].inv=0;
            Seg[Seg[o].rson].allo=1;
            Seg[Seg[o].rson].allz=0;
            Seg[Seg[o].rson].firo=Seg[Seg[o].rson].lx;
            Seg[Seg[o].rson].firz=9000000000000000000LL;
            Seg[Seg[o].rson].set=Seg[o].set; 
            Seg[Seg[o].rson].inv=0;
        }
        Seg[o].set=-1;
    }
    
}
int query(int L,int R,int o){
    int l=Seg[o].lx,r=Seg[o].rx;
    if(R<l||L>r)
        return 9000000000000000000LL;
    if(L<=l&&r<=R){
        return Seg[o].firz;
    }
    int mid=Seg[o].midx;
    pushdown(o);
    int ans=9000000000000000000LL;
    if(L<=mid)
        ans=min(ans,query(L,R,Seg[o].lson));
    if(R>mid)
        ans=min(ans,query(L,R,Seg[o].rson));
    return ans;
}
void revs(int L,int R,int o){
    int l=Seg[o].lx,r=Seg[o].rx;
    if(R<l||L>r)
        return;
    if(L<=l&&r<=R){
        swap(Seg[o].allo,Seg[o].allz);
        swap(Seg[o].firo,Seg[o].firz);
        if(Seg[o].set!=-1)
            Seg[o].set^=1;
        else
            Seg[o].inv^=1;
        return;
    }
    pushdown(o);
    int mid=Seg[o].midx;
    if(L<=mid)
        revs(L,R,Seg[o].lson);
    if(R>mid)
        revs(L,R,Seg[o].rson);
    pushup(o);
}
void set0(int L,int R,int o){
    if(Seg[o].allz)
        return;
    int l=Seg[o].lx,r=Seg[o].rx;
    if(R<l||L>r)
        return;
    // printf("l=%I64d r=%I64d o=%I64d\n",l,r,o);
    if(L<=l&&r<=R){
        Seg[o].allo=0;
        Seg[o].allz=1;
        Seg[o].firo=9000000000000000000LL;
        Seg[o].firz=Seg[o].lx;
        Seg[o].set=0; 
        Seg[o].inv=0;
        return;
    }
    pushdown(o);
    int mid=Seg[o].midx;
    if(L<=mid)
        set0(L,R,Seg[o].lson);
    if(R>mid)
        set0(L,R,Seg[o].rson);
    // printf("l=%I64d r=%I64d o=%I64d firz=%I64d\n",l,r,o,Seg[o].firz);
    pushup(o);
}
void set1(int L,int R,int o){
    // printf("o=%I64d want %I64d %I64d became-1 %I64d %I64d\n",o,L,R,l,r);
    if(Seg[o].allo)
        return;
    int l=Seg[o].lx,r=Seg[o].rx;
    if(R<l||L>r)
        return;
    // printf("o=%I64d want %I64d %I64d became-1 %I64d %I64d\n",o,L,R,l,r);
    if(L<=l&&r<=R){
        // printf("ttt\n");
        Seg[o].allo=1;
        Seg[o].allz=0;
        Seg[o].firo=Seg[o].lx;
        Seg[o].firz=9000000000000000000LL;
        Seg[o].set=1; 
        Seg[o].inv=0;
        return;
    }
    // printf("ggg\n");
    pushdown(o);
    // printf("ggg!\n");
    int mid=Seg[o].midx;
    // printf("mid=%I64d\n",mid);
    if(L<=mid){
        // printf("%I64d to-L\n",o);
        set1(L,R,Seg[o].lson);}
    if(R>mid){
        // printf("%I64d to-R\n",o);
        set1(L,R,Seg[o].rson);}
    pushup(o);
}
int build(int l,int r){
    // printf("build")
    int newx=New_Node(pos[l],pos[(l+r)>>1],pos[r]);
    if(l!=r){
        int mid=(l+r)>>1;
        Seg[newx].lson=build(l,mid);
        Seg[newx].rson=build(mid+1,r);
        pushup(newx);
    }
    return newx;
}
void debug(int o){ 
    int l=Seg[o].lx,r=Seg[o].rx;
    printf("o=%I64d lson=%I64d rson=%I64d lx=%I64d rx=%I64d firz=%I64d firo=%I64d allz=%I64d allo=%I64d \n",o,Seg[o].lson,Seg[o].rson,Seg[o].lx,Seg[o].rx,Seg[o].firz,Seg[o].firo,Seg[o].allz,Seg[o].allo);
    if(l!=r){
        debug(Seg[o].lson);
        debug(Seg[o].rson);
    }
}
signed main(){
    scanf("%I64d",&n);
    pos[++cnt]=1;
    for(int i=1;i<=n;i++){
        scanf("%I64d %I64d %I64d",&qx[i].opt,&qx[i].l,&qx[i].r);
        // cout<<9000000000000000000LL<<endl;
        if(qx[i].l-1>0)
            pos[++cnt]=qx[i].l-1;
        pos[++cnt]=qx[i].l;
        pos[++cnt]=qx[i].r;
        pos[++cnt]=qx[i].r+1;
    }
    sort(pos+1,pos+cnt+1);
    aft_cnt=unique(pos+1,pos+cnt+1)-(pos)-1;
    // for(int i=1;i<=aft_cnt;i++)
    //     printf("%I64d ",pos[i]);
    // printf("\n");
    root=build(1,aft_cnt);
    // debug(root);
    // printf("\n\n\n\n");
    for(int i=1;i<=n;i++){
        if(qx[i].opt==1){
            // printf("optnum=%I64d l=%I64d r=%I64d\n",i,qx[i].l,qx[i].r);
            set1(qx[i].l,qx[i].r,root);
            // debug(root);
            // printf("\n\n\n\n");
            printf("%I64d\n",Seg[root].firz);
        }
        else if(qx[i].opt==2){
            // printf("optnum=%I64d l=%I64d r=%I64d\n",i,qx[i].l,qx[i].r);
            set0(qx[i].l,qx[i].r,root);
            // debug(root);
            // printf("\n\n\n\n");
            printf("%I64d\n",Seg[root].firz);
        }
        else{
            // printf("optnum=%I64d l=%I64d r=%I64d\n",i,qx[i].l,qx[i].r);
            revs(qx[i].l,qx[i].r,root);
            // debug(root);
            // printf("\n\n\n\n");
            printf("%I64d\n",Seg[root].firz);
        }
    }
    return 0;
}