Codeforces817 F. MEX Queries（线段树，01序列同时维护翻转laz和覆盖laz）

题意：

解法：

考虑权值线段树直接维护01序列,求mex只需要在树上二分.数据范围太大,显然先离散化.操作1和操作2可以看作是区间覆盖为1和0.
操作3可以看作是01序列的区间翻转.难点是需要同时维护翻转laz和覆盖laz,
因为同时存在两种标记会出现操作顺序的问题.正确的维护方法是保证同一时间同一个节点只存在一种laz:
1.在给带翻转laz的节点打覆盖标记时,由于覆盖标记的优先级大,可以直接清空翻转标记.
2.在给带覆盖laz的节点打翻转标记时,直接对覆盖标记翻转即可.上述方法可以保证每个节点最多只有一种标记,这样就不会出现操作顺序的问题了.

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=2e6+5;
struct QQ{int op,l,r;
}e[maxm];
int xx[maxm],num;
struct Node{int a[maxm<<2];int laz1[maxm<<2];//addint laz2[maxm<<2];//revinline void pp(int node){a[node]=a[node*2]+a[node*2+1];}inline void pd1(int node,int l,int r){//区间覆盖if(laz1[node]!=-1){int mid=(l+r)/2;a[node*2]=(mid-l+1)*laz1[node];a[node*2+1]=(r-mid)*laz1[node];laz1[node*2]=laz1[node];laz1[node*2+1]=laz1[node];laz1[node]=-1;//laz1优先级高,有laz1可以去掉laz2laz2[node*2]=0;laz2[node*2+1]=0;//}}inline void pd2(int node,int l,int r){//区间翻转if(laz2[node]){int mid=(l+r)/2;a[node*2]=(mid-l+1)-a[node*2];a[node*2+1]=(r-mid)-a[node*2+1];//当有laz1时,laz2直接翻转laz1if(laz1[node*2]!=-1){laz1[node*2]^=1;}else{laz2[node*2]^=1;}if(laz1[node*2+1]!=-1){laz1[node*2+1]^=1;}else{laz2[node*2+1]^=1;}laz2[node]=0;}}void add(int st,int ed,int val,int l,int r,int node){if(st<=l&&ed>=r){laz1[node]=val;laz2[node]=0;a[node]=(r-l+1)*val;return ;}pd1(node,l,r);pd2(node,l,r);int mid=(l+r)/2;if(st<=mid)add(st,ed,val,l,mid,node*2);if(ed>mid)add(st,ed,val,mid+1,r,node*2+1);pp(node);}void rev(int st,int ed,int l,int r,int node){if(st<=l&&ed>=r){if(laz1[node]!=-1)laz1[node]^=1;else laz2[node]^=1;a[node]=(r-l+1)-a[node];return ;}pd1(node,l,r);pd2(node,l,r);int mid=(l+r)/2;if(st<=mid)rev(st,ed,l,mid,node*2);if(ed>mid)rev(st,ed,mid+1,r,node*2+1);pp(node);}int ask(int l,int r,int node){if(l==r)return l;pd1(node,l,r);pd2(node,l,r);int mid=(l+r)/2;if(a[node*2]<mid-l+1)return ask(l,mid,node*2);else return ask(mid+1,r,node*2+1);}void build(int l,int r,int node){laz1[node]=-1;laz2[node]=0;a[node]=0;if(l==r)return ;int mid=(l+r)/2;build(l,mid,node*2);build(mid+1,r,node*2+1);}
}T;
void solve(){int q;cin>>q;for(int i=1;i<=q;i++){cin>>e[i].op>>e[i].l>>e[i].r;xx[++num]=e[i].l;xx[++num]=e[i].r;xx[++num]=e[i].r+1;}xx[++num]=1;sort(xx+1,xx+1+num);num=unique(xx+1,xx+1+num)-xx-1;for(int i=1;i<=q;i++){e[i].l=lower_bound(xx+1,xx+1+num,e[i].l)-xx;e[i].r=lower_bound(xx+1,xx+1+num,e[i].r)-xx;}T.build(1,num,1);for(int i=1;i<=q;i++){int op=e[i].op,l=e[i].l,r=e[i].r;if(op==1){T.add(l,r,1,1,num,1);}else if(op==2){T.add(l,r,0,1,num,1);}else if(op==3){T.rev(l,r,1,num,1);}int ans=T.ask(1,num,1);cout<<xx[ans]<<endl;}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}