http://codeforces.com/contest/817/problem/F
无限长的数组，刚开始每一位是0，三种操作，1，把（l，r）之间不是1的变成1，2，把（l，r）之间不是0的变成0，3，把0变成1，1变成0，每次操作都要查询该数组的mex（最小的没有在集合中出现的数）
解法：很明显的线段树，lazy标记有3个，分别代表3中操作的，当pushdown的时候如果lazy为1或2都直接下传，但是当lazy是3的时候，不能直接下传，因为1，2操作优先级更大，所以pushdown时特判一下这种情况即可（当儿子的lazy为1时，刚好需要先全变1然后翻转就是2操作1了，lazy为2同理，lazy为3的话直接翻转两次等同于没有翻转），查询的话，直接查询左右区间，如果左区间是满的，那么右边，否则查询左侧，注意hash的时候把1加上去，每个点左右两个点也要加进去，不然会出现断层！！
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-9; const int N=1200000+10,maxn=100000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; struct qu{ int t; ll l,r; }q[N]; int lazy[N<<2],value[N<<2]; int cnt; ll Hash[N<<2]; void pushup(int rt) { value[rt]=value[rt<<1]+value[rt<<1|1]; } void pushdown(int l,int r,int rt) { int m=(l+r)>>1; if(lazy[rt]==1) { value[rt<<1]=m-l+1; value[rt<<1|1]=r-m; lazy[rt<<1]=lazy[rt<<1|1]=1; } else if(lazy[rt]==2) { value[rt<<1]=value[rt<<1|1]=0; lazy[rt<<1]=lazy[rt<<1|1]=2; } else if(lazy[rt]==3) { value[rt<<1]=m-l+1-value[rt<<1]; value[rt<<1|1]=r-m-value[rt<<1|1]; lazy[rt<<1]=3-lazy[rt<<1]; lazy[rt<<1|1]=3-lazy[rt<<1|1]; } lazy[rt]=0; } void build(int l,int r,int rt) { value[rt]=0,lazy[rt]=0; if(l==r)return ; int m=(l+r)>>1; build(ls);build(rs); } void update(int L,int R,int op,int l,int r,int rt) { if(L<=l&&r<=R) { if(op==1) { value[rt]=r-l+1; lazy[rt]=op; } else if(op==2) { value[rt]=0; lazy[rt]=op; } else { if(lazy[rt])pushdown(l,r,rt); value[rt]=r-l+1-value[rt]; lazy[rt]=op; } return ; } pushdown(l,r,rt); int m=(l+r)>>1; if(L<=m)update(L,R,op,ls); if(m<R)update(L,R,op,rs); pushup(rt); } int query(int l,int r,int rt) { if(l==r)return l; pushdown(l,r,rt); int m=(l+r)>>1; if(value[rt<<1]==m-l+1)return query(rs); else return query(ls); } void add(ll x) { if(x!=0)Hash[cnt++]=x; } int main() { int n; cnt=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%lld%lld",&q[i].t,&q[i].l,&q[i].r); add(q[i].l-1),add(q[i].l),add(q[i].l+1); add(q[i].r-1),add(q[i].r),add(q[i].r+1); } Hash[cnt++]=1; sort(Hash,Hash+cnt); cnt=unique(Hash,Hash+cnt)-Hash; // for(int i=0;i<cnt;i++)printf("%lld ",Hash[i]); // puts(""); build(1,cnt,1); for(int i=0;i<n;i++) { int op=q[i].t; int tel=lower_bound(Hash,Hash+cnt,q[i].l)-Hash; int ter=lower_bound(Hash,Hash+cnt,q[i].r)-Hash; update(tel+1,ter+1,q[i].t,1,cnt,1); int ans=query(1,cnt,1); // printf("%d %d %d ",tel,ter,ans); printf("%lld ",Hash[ans-1]); } return 0; } /******************** 1 2 854690110384167294 954215012997404774 ********************/