题目链接:

咕咕咕

闲扯

在Yali经历几天折磨后信心摧残,T1数据结构裸题考场上连暴力都TM没打满

分析

观察到点值巨大,离散化即可

但是注意到\(1,l+1,r+1\)都是会产生答案的,也需要离散化,同时注意数组大小

然后区间异或线段树,为了查询我们记录一个数组\(sum0[now]\)表示now区间0的个数

同时相应的记录的一个\(sum1[now]\)表示区间1的个数方便各种操作的转换

下传标记时需要注意的就不多说了,也不用注意挺多,还挺好码的

但是注意数组别开小了!!!我们一条区间最多拓展四个点!

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define ll long long #define ri register int using std::min;using std::max;using std::swap;using namespace __gnu_pbds;template 
            
             inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x;return ;}const int maxn=400005;//数组一定要开大,线段树最多是平常的四倍const int inf=0x7fffffff;int L,R,dta;int pos=-1;struct Segment_Tree{ int sum1[maxn<<2],sum0[maxn<<2]; int tag[maxn<<2],set[maxn<<2]; inline void pushup(int now){ sum0[now]=sum0[now<<1]+sum0[now<<1|1]; sum1[now]=sum1[now<<1]+sum1[now<<1|1]; return ; } void build(int now,int l,int r){ set[now]=-1,tag[now]=0; if(l==r){ sum0[now]=1,sum1[now]=0; return ; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); pushup(now); } inline void pushdown(int now,int ln,int rn){ if(tag[now]){ if(set[now]==-1){ if(set[now<<1]!=-1)set[now<<1]^=1; if(set[now<<1|1]!=-1)set[now<<1|1]^=1; //tag[now<<1]^=1,tag[now<<1|1]^=1; swap(sum1[now<<1],sum0[now<<1]); swap(sum1[now<<1|1],sum0[now<<1|1]); } tag[now]=0; } if(set[now]!=-1){ tag[now<<1]=tag[now<<1|1]=0; set[now<<1]=set[now<<1|1]=set[now]; if(set[now]==1){ sum1[now<<1]=ln,sum0[now<<1]=0; sum1[now<<1|1]=rn,sum0[now<<1|1]=0; } else{ sum1[now<<1]=0,sum0[now<<1]=rn; sum1[now<<1|1]=0,sum0[now<<1|1]=rn; } set[now]=-1; } return ; } void update_s1(int now,int l,int r){ if(L<=l&&r<=R){ set[now]=1; tag[now]=0; sum0[now]=0,sum1[now]=(r-l+1); return ; } int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if(L<=mid)update_s1(now<<1,l,mid); if(mid
             
              <<1|1,mid+1,r); pushup(now); } void update_s0(int now,int l,int r){ if(L<=l&&r<=R){ set[now]=0; tag[now]=0; sum0[now]=(r-l+1),sum1[now]=0; return ; } int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if(L<=mid)update_s0(now<<1,l,mid); if(mid
              
               <<1|1,mid+1,r); pushup(now); return ; } void update_xor(int now,int l,int r){ if(L<=l&&r<=R){ if(set[now]!=-1){ set[now]^=1; } else tag[now]^=1; swap(sum0[now],sum1[now]); return ; } int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if(L<=mid)update_xor(now<<1,l,mid); if(mid
               
                <<1|1,mid+1,r); pushup(now); return ; } void query(int now,int l,int r){ if(sum0[now]==0)return ; if(l==r){ pos=l; return ; } int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if(sum0[now<<1]!=0)query(now<<1,l,mid); if(pos!=-1)return; if(sum0[now<<1|1]!=0)query(now<<1|1,mid+1,r); pushup(now); return ; }}T;struct OP{ int ty;ll l,r;}op[maxn];int n;ll f[maxn<<2];int tot=0;gp_hash_table 
                
                  h;int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); read(n); f[++tot]=1; for(ri i=1;i<=n;i++){ read(op[i].ty),read(op[i].l),read(op[i].r); f[++tot]=op[i].l,f[++tot]=op[i].r; f[++tot]=op[i].l+1; f[++tot]=op[i].r+1; } std::sort(f+1,f+1+tot); tot=std::unique(f+1,f+1+tot)-(f+1); for(ri i=1;i<=tot;i++){ h[f[i]]=i; } T.build(1,1,tot); //tot=1000; for(ri i=1;i<=n;i++){ L=h[op[i].l],R=h[op[i].r]; //L=op[i].l,R=op[i].r; //printf("%d %d\n",L,R); if(op[i].ty==1){ T.update_s1(1,1,tot); } if(op[i].ty==2){ T.update_s0(1,1,tot); } if(op[i].ty==3){ T.update_xor(1,1,tot); } pos=-1; T.query(1,1,tot); //printf("--%d--\n",pos); printf("%lld\n",f[pos]); } return 0;}