题目链接：Educational Codeforces Round 23 F. MEX Queries
题意：
一共有n个操作。
1. 将[l,r]区间的数标记为1。
2. 将[l,r]区间的数标记为0。
3. 将[l,r]区间取反。
对每个操作，输出标记为0的最小正整数。
题解：
hash后，用线段树xjb标记一下就行了。
1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<<1|1 4 #define F(i,a,b) for(int i=a;i<=b;++i) 5 using namespace std; 6 typedef long long ll; 7 8 const int N=4e5+7; 9 int n,ed,sum[N<<2],lazy[N<<2];10 ll hsh[N],mx;11 struct Node12 {13int type;14ll l,r;15 }q[N];16 17 void del(int rt)18 {19if(lazy[rt]==1||lazy[rt]==2)lazy[rt]=(lazy[rt]==1?2:1);20else if(lazy[rt]==3)lazy[rt]=0;21else lazy[rt]=3;22 }23 24 void PD(int rt,int l,int r)25 {26if(!lazy[rt])return;27int m=l+r>>1;28if(lazy[rt]==1)29{30 sum[rt<<1]=m-l+1,sum[rt<<1|1]=r-m;31 lazy[rt<<1]=lazy[rt<<1|1]=1;32}33else if(lazy[rt]==2)34{35 sum[rt<<1]=sum[rt<<1|1]=0;36 lazy[rt<<1]=lazy[rt<<1|1]=2;37}38else 39{40 sum[rt<<1]=(m-l+1)-sum[rt<<1],sum[rt<<1|1]=(r-m)-sum[rt<<1|1];41 del(rt<<1),del(rt<<1|1);42}43lazy[rt]=0;44 }45 46 void PU(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}47 48 void update(int L,int R,int v,int l=1,int r=ed,int rt=1)49 {50if(L<=l&&r<=R)51{52 if(v==1)sum[rt]=(r-l+1),lazy[rt]=1;53 else if(v==2)sum[rt]=0,lazy[rt]=2;54 else del(rt),sum[rt]=(r-l+1)-sum[rt];55 return;56}57PD(rt,l,r);58int m=l+r>>1;59if(L<=m)update(L,R,v,ls);60if(R>m)update(L,R,v,rs);61PU(rt);62 }63 64 int query(int l=1,int r=ed,int rt=1)65 {66if(l==r)return l;67int m=l+r>>1;68PD(rt,l,r);69if(m-l+1-sum[rt<<1])return query(ls);70else return query(rs);71 }72 73 74 int getid(ll x){return lower_bound(hsh+1,hsh+1+ed,x)-hsh;}75 76 int main(){77scanf("%d",&n);78F(i,1,n)79{80 scanf("%d%I64d%I64d",&q[i].type,&q[i].l,&q[i].r);81 hsh[++ed]=q[i].l,hsh[++ed]=q[i].r;82 hsh[++ed]=q[i].l+1,hsh[++ed]=q[i].r+1;83}84hsh[++ed]=1;85sort(hsh+1,hsh+1+ed),ed=unique(hsh+1,hsh+1+ed)-hsh-1;86F(i,1,n)87{88 update(getid(q[i].l),getid(q[i].r),q[i].type);89 printf("%I64d\n",hsh[query()]);90}91return 0;92 }
View Code
