【XSY2484】mex 离散化 线段树

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意

给你一个无限长的数组，初始的时候都为\(0\)，有3种操作：

操作\(1\)是把给定区间\([l,r]\)设为\(1\)；

操作\(2\)是把给定区间\([l,r]\)设为\(0\)；

操作\(3\)把给定区间\([l,r]0,1\)反转；

一共\(n\)个操作，每次操作后要输出最小位置的\(0\)。

\(n\leq 100000,1\leq l\leq r\leq {10}^{18}\)

题解

本题可以用平衡树做，这样就不用离散化了

下面是线段树做法

因为\(l,r\)很大，所以要离散化。通过证（guan）明（cha）发现，答案只可能是\(1,l,r+1\)。我们把这\(2n+1\)个点拿出来离散化，然后用线段树维护区间和就行了。我维护了最左边的\(0\)和最左边的\(1\)。

时间复杂度：\(O(n\log n)\)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef int zjt_ak_noi_2018;
typedef long long ll;
typedef pair<zjt_ak_noi_2018,zjt_ak_noi_2018> pii;
struct node
{
zjt_ak_noi_2018 l,r;
zjt_ak_noi_2018 ls,rs;
zjt_ak_noi_2018 s0,s1;
zjt_ak_noi_2018 t1,t2;
node()
{
ls=rs=0;
s0=s1=0;
t1=-1;
t2=0;
}
};
node a[500010];
zjt_ak_noi_2018 rt;
zjt_ak_noi_2018 cnt=0;
zjt_ak_noi_2018 merge(zjt_ak_noi_2018 v1,zjt_ak_noi_2018 v2)
{
if(!v1||!v2)
return v1+v2;
return min(v1,v2);
}
void build(zjt_ak_noi_2018 &p,zjt_ak_noi_2018 l,zjt_ak_noi_2018 r)
{
p=++cnt;
a[p].l=l;
a[p].r=r;
if(l==r)
{
a[p].s0=l;
return;
}
zjt_ak_noi_2018 mid=(l+r)>>1;
build(a[p].ls,l,mid);
build(a[p].rs,mid+1,r);
a[p].s0=merge(a[a[p].ls].s0,a[a[p].rs].s0);
a[p].s1=merge(a[a[p].rs].s1,a[a[p].rs].s1);
}
void fill(zjt_ak_noi_2018 p,zjt_ak_noi_2018 v)
{
if(v)
{
a[p].s0=0;
a[p].s1=a[p].l;
}
else
{
a[p].s0=a[p].l;
a[p].s1=0;
}
a[p].t1=v;
a[p].t2=0;
}
void reverse(zjt_ak_noi_2018 p)
{
swap(a[p].s0,a[p].s1);
a[p].t2^=1;
}
void push(zjt_ak_noi_2018 p)
{
if(a[p].l!=a[p].r)
{
if(~a[p].t1)
{
fill(a[p].ls,a[p].t1);
fill(a[p].rs,a[p].t1);
a[p].t1=-1;
}
if(a[p].t2)
{
reverse(a[p].ls);
reverse(a[p].rs);
a[p].t2=0;
}
}
}
void fill(zjt_ak_noi_2018 p,zjt_ak_noi_2018 l,zjt_ak_noi_2018 r,zjt_ak_noi_2018 v)
{
if(l<=a[p].l&&r>=a[p].r)
{
fill(p,v);
return;
}
push(p);
zjt_ak_noi_2018 mid=(a[p].l+a[p].r)>>1;
if(l<=mid)
fill(a[p].ls,l,r,v);
if(r>mid)
fill(a[p].rs,l,r,v);
a[p].s0=merge(a[a[p].ls].s0,a[a[p].rs].s0);
a[p].s1=merge(a[a[p].ls].s1,a[a[p].rs].s1);
}
void reverse(zjt_ak_noi_2018 p,zjt_ak_noi_2018 l,zjt_ak_noi_2018 r)
{
if(l<=a[p].l&&r>=a[p].r)
{
reverse(p);
return;
}
push(p);
zjt_ak_noi_2018 mid=(a[p].l+a[p].r)>>1;
if(l<=mid)
reverse(a[p].ls,l,r);
if(r>mid)
reverse(a[p].rs,l,r);
a[p].s0=merge(a[a[p].ls].s0,a[a[p].rs].s0);
a[p].s1=merge(a[a[p].ls].s1,a[a[p].rs].s1);
}
//zjt_ak_noi_2018 query(zjt_ak_noi_2018 p,zjt_ak_noi_2018 l,zjt_ak_noi_2018 r)
//{
//if(l<=a[p].l&&r>=a[p].r)
//return a[p].s0;
//push(p);
//zjt_ak_noi_2018 mid=(a[p].l+a[p].r)>>1;
//zjt_ak_noi_2018 s=0;
//if(l<=mid)
//s=merge(s,query(a[p].ls,l,r));
//if(r>mid)
//s=merge(s,query(a[p].rs,l,r));
//return s;
//}
zjt_ak_noi_2018 op[100010];
ll l[100010];
ll r[100010];
ll d[200010];
zjt_ak_noi_2018 main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
zjt_ak_noi_2018 n,m=0;
scanf("%d",&n);
zjt_ak_noi_2018 i;
for(i=1;i<=n;i++)
{
scanf("%d%lld%lld",&op[i],&l[i],&r[i]);
d[++m]=l[i];
d[++m]=r[i]+1;
}
d[++m]=1;
sort(d+1,d+m+1);
m=unique(d+1,d+m+1)-d-1;
for(i=1;i<=n;i++)
{
l[i]=lower_bound(d+1,d+m+1,l[i])-d;
r[i]=upper_bound(d+1,d+m+1,r[i])-d-1;
}
build(rt,1,m);
for(i=1;i<=n;i++)
{
if(op[i]==1)
fill(rt,l[i],r[i],1);
else if(op[i]==2)
fill(rt,l[i],r[i],0);
else
reverse(rt,l[i],r[i]);
printf("%lld\n",d[a[rt].s0]);
}
return 0;
}