CF817F MEX Queries

线段树+离散化

一开始所求的这个集合啥都没有。

• 操作 $1$ 就是把 $l$ 到 $r$ 之间的数的数量全部变为 $1$ （区间修改

• 操作 $2$ 就是把 $l$ 到 $r$ 之间的数的数量全部变为 $0$ （区间修改

• 操作 $3$ 就是把 $l$ 到 $r$ 之间 $0$ 变为 $1$ ，$1$ 变为 $0$ （区间反转（？

一开始 $l$ 和 $r$ 所处的大集合就是整个正整数集，反正是区间操作，线段树的下标数 $id$ 在正整数集合里面对应的就是 $id$ ，如果在线段树里为 $1$ 那就是集合中有这个数否则没有，所以直接离散化好了（有很多数根本不会用到啊

把 $r+1$ 离散化是因为如果左右端点都在一起了，那我什么也没查找到啊，（即 $l$ == $r$ ），那岂不是直接返回我自己了...

维护三个 $tag$ ，分别是区间和，区间是否为 $0$ 和区间反转。操作时直接修改这三个 $tag$ 就好了，这三个 $tag$ 就是方便下传到 $lson$ 和 $rson$ 时修改他们的值的（和普通线段树一样

查询的时候直接查询 $l$ 到 $r$ 区间里没有出现过的最小的正整数呗，那不直接从 $1$ 开始找找到最左端为 $0$ 的数啊。。。如果左儿子的大小小于它应该有的大小那 $0$ 显然在左儿子啊。。。

#include <bits/stdc++.h>
#define ll long long
#define maxn 200001
using namespace std;
ll n;
ll t[maxn<<2],cnt,tree[maxn<<2];
ll lazytag[maxn<<2],rev[maxn<<2];
struct Node{
    ll l,r,op;
}a[maxn];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void build(ll l,ll r,ll f){
    lazytag[f]=-1;
    if(l==r)    return;
    ll mid=(l+r)>>1;
    build(l,mid,f<<1);
    build(mid+1,r,f<<1|1);
}

 inline void mark(ll l,ll r,ll f,ll x){
    if(x==1){
        tree[f]=(r-l+1);
        lazytag[f]=1;
        rev[f]=0;
    }
    else if(x==2){
        tree[f]=0;
        lazytag[f]=0;
        rev[f]=0;
    }
    else{
        tree[f]=(r-l+1)-tree[f];
        if(lazytag[f]!=-1)
            lazytag[f]^=1;
        else
            rev[f]^=1;
    }
}

inline void pushdown(ll l,ll r,ll f){
    ll mid=(l+r)>>1;
    if(lazytag[f]==1){
       mark(l,mid,f<<1,1);
       mark(mid+1,r,f<<1|1,1);
        lazytag[f]=-1;
    }
    else if(lazytag[f]==0){
       mark(l,mid,f<<1,2);
       mark(mid+1,r,f<<1|1,2);
        lazytag[f]=-1;
    }
    if(rev[f]){
       mark(l,mid,f<<1,3);
       mark(mid+1,r,f<<1|1,3);
        rev[f]=0;
    }
}
    
inline void add(ll l,ll r,ll f,ll cl,ll cr,ll x){
    ll mid=(l+r)>>1;
    if(l==r){
        if(x==1)        tree[f]=1;
        else if(x==2)   tree[f]=0;
        else            tree[f]^=1;
        return;
    }
    if(cl<=l&&r<=cr){
       mark(l,r,f,x);
        return;
    }
    pushdown(l,r,f);
    if(cl<=mid)     add(l,mid,f<<1,cl,cr,x);
    if(mid<cr)      add(mid+1,r,f<<1|1,cl,cr,x);  
    tree[f]=tree[f<<1]+tree[f<<1|1];
}

inline ll query(ll l,ll r,ll f){
    ll mid=(l+r)>>1;
    if(l==r)    return l;
    pushdown(l,r,f);
    if(tree[f<<1]<(mid-l+1))
        return query(l,mid,f<<1);
    else
        return query(mid+1,r,f<<1|1);
}

int main(){
   n=read();
   t[++cnt]=1;
    for(register int i=1;i<=n;++i){
        a[i].op=read();a[i].l=read();a[i].r=read();
        t[++cnt]=a[i].l;
        t[++cnt]=a[i].r;
        t[++cnt]=a[i].r+1;
    }
   sort(t+1,t+cnt+1);
   cnt=unique(t+1,t+cnt+1)-t-1;
   build(1,cnt,1);
   for(register int i=1;i<=n;++i){
       a[i].l=lower_bound(t+1,t+cnt+1,a[i].l)-t;
       a[i].r=lower_bound(t+1,t+cnt+1,a[i].r)-t;
       add(1,cnt,1,a[i].l,a[i].r,a[i].op);
       printf("%lld\n",t[query(1,cnt,1)]);
   }
    return 0;
}