本文主要是介绍Educational Codeforces Round 23 F. MEX Queries（离散化+线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/817/problem/F
这个题的难度不像是F啊。。。
然而
我好蠢啊。。。
最开始发现，其实很多区间可以合并在一起，就写了一个延时更新的[1，1e18]的线段树，MLE 21到死。。。
后来发现，离散化一下好像很清真啊？
由于只有0和1两个值，然后发现操作3就是个异或的操作，下放的时候可以同时对1的个数和lazy标记同时进行处理。离散化的时候，注意，对于区间[L,R]，需要多离散化一个R+1这个节点，因为这个点可能作为某次查询的答案（别问我为啥离散化L-1，大概是蠢吧），然后就是个水题啊？
（那我为什么写了这么久啊？）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct seg
{ll tot;bool rev;int lazy;bool ro;seg *lson,*rson;seg(){}seg(int _rev):rev(_rev){lson=rson=NULL;lazy=-1;tot=0;ro=false;}ll gettot(){return tot;}void pushup(){ll ret=0;if(lson!=NULL)ret+=lson->gettot();if(rson!=NULL)ret+=rson->gettot();tot=ret;}int getid(){return lazy^rev;}void pushlazy(ll l,ll r){ll mid=(l+r)>>1;if(lson==NULL)lson=new seg(0);if(rson==NULL)rson=new seg(0);if(ro){lson->rev^=1;lson->ro=!lson->ro;lson->tot=(mid-l+1)-lson->tot;rson->rev^=1;rson->ro=!rson->ro;rson->tot=(r-(mid+1)+1)-rson->tot;ro=false;}if(lazy!=-1){lson->lazy=(getid()^lson->rev);lson->tot=(mid-l+1)*lson->getid();rson->lazy=(getid()^rson->rev);rson->tot=(r-(mid+1)+1)*rson->getid();lazy=-1;}}void update(ll L,ll R,int val,bool we,ll l,ll r){if(L<=l&&r<=R){if(!we){lazy=val^rev;tot=(r-l+1)*getid();}else{ro=!ro;rev^=1;tot=r-l+1-tot;}return ;}pushlazy(l,r);ll mid=(l+r)>>1;if(mid>=L){lson->update(L,R,val,we,l,mid);}if(mid<R){rson->update(L,R,val,we,mid+1,r);}pushup();}ll query(ll l,ll r){if(gettot()==0)return l;ll mid=(l+r)>>1;seg tmp=*this;pushlazy(l,r);if(lson->gettot()<(mid-l+1))return lson->query(l,mid);elsereturn rson->query(mid+1,r);}
}*root;
const int MAXN=1e5+5;
int tot;
ll Hash[MAXN*4];
struct qu
{int op;ll l,r;
}sv[MAXN];
int fi(ll now)
{int ret=lower_bound(Hash,Hash+tot,now)-Hash;return ret;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);root=new seg(0);tot=0;Hash[tot++]=1000000000000000001LL;Hash[tot++]=1;int n;scanf("%d",&n);for(int i=1;i<=n;i++){int op;ll l,r;scanf("%d%lld%lld",&sv[i].op,&sv[i].l,&sv[i].r);Hash[tot++]=sv[i].l;Hash[tot++]=sv[i].r;if(sv[i].l!=1)Hash[tot++]=sv[i].l-1;Hash[tot++]=sv[i].r+1;}sort(Hash,Hash+tot);tot=unique(Hash,Hash+tot)-Hash;for(int i=1;i<=n;i++){sv[i].l=fi(sv[i].l);sv[i].r=fi(sv[i].r);}for(int i=1;i<=n;i++){if(sv[i].op==1){root->update(sv[i].l,sv[i].r,1,false,0,tot-1);}if(sv[i].op==2){root->update(sv[i].l,sv[i].r,0,false,0,tot-1);}if(sv[i].op==3){root->update(sv[i].l,sv[i].r,0,true,0,tot-1);}int ret=root->query(0,tot-1);ll ans;ans=Hash[ret];printf("%lld\n",ans);}return 0;
}这篇关于Educational Codeforces Round 23 F. MEX Queries（离散化+线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
