前言
其实本来是用来练习线段树上二分的。
结果这个懒标记互相覆盖和累加的性质搞了我好久（虽然只是个板子
一开始WA on #8 死活调不过。
重构了一遍才过。
题解
详见：https://www.luogu.com.cn/blog/184549/solution-cf817f
就是对懒标记下传时分类讨论。
如果是区间赋值/清零就可以直接覆盖。
如果是区间反转就根据原来的懒标记分类讨论：
- 原来是区间赋值，改成区间清零。
- 原来是区间清零，改成区间赋值。
- 原来是区间反转，改成啥也不干。
- 原来是啥也不干，改成区间反转。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FCC fclose(stdin),fclose(stdout)
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
const int INF = 0x3f3f3f3f,N = 4e5+10;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,tot;
struct ask
{
int op;
ll l,r;
}q[N];
ll p[N<<1],a[N<<1],cnt;
ll rnk[N<<1];
struct Segtree
{
int sum[N<<2];
int lazy[N<<2];
void init_lazy(){memset(lazy,-1,sizeof(lazy));}
inline void add(int k,int l,int r,int v)
{
//lazy/vl：初始-1，区间覆盖1，区间清除0
//rev/vr: 初始0，区间反转1
if(v==1||v==0) lazy[k]=v,sum[k]=(r-l+1)*v;
else
{
sum[k]=r-l+1-sum[k];
if(lazy[k]==-1) lazy[k]=v;
else if(lazy[k]==1) lazy[k]=0;
else if(!lazy[k]) lazy[k]=1;
else lazy[k]=-1;
}
}
inline void pushdown(int k,int l,int r)
{
if(lazy[k]==-1) return;
add(ls,l,mid,lazy[k]);
add(rs,mid+1,r,lazy[k]);
lazy[k]=-1;
}
void modify(int k,int l,int r,int x,int y,int vl)
{
if(x<=l&&r<=y) {add(k,l,r,vl);return;}
pushdown(k,l,r);
if(x<=mid) modify(ls,l,mid,x,y,vl);
if(y>mid) modify(rs,mid+1,r,x,y,vl);
sum[k]=sum[ls]+sum[rs];
}
int find(int k,int l,int r,int x,int y)
{
if(sum[k]==r-l+1) return 0;
if(!sum[k]) return l;
pushdown(k,l,r);
int ret=find(ls,l,mid,x,y);
if(ret) return ret;
return find(rs,mid+1,r,x,y);
}
}str;
void discrete()
{
sort(p+1,p+cnt+1);
tot=unique(p+1,p+cnt+1)-p-1;
for(int i=1;i<=cnt;i++)
{
int newl=lower_bound(p+1,p+tot+1,a[i])-p;
// printf("new %d:[%d,%d]\n",i,newl,newr);
rnk[newl]=a[i];
}
for(int i=1;i<=n;i++)
{
int newl=lower_bound(p+1,p+tot+1,q[i].l)-p;
int newr=lower_bound(p+1,p+tot+1,q[i].r)-p;
// printf("new %d:[%d,%d]\n",i,newl,newr);
q[i].l=newl,q[i].r=newr;
}
return;
}
void work()
{
str.init_lazy();
for(int i=1;i<=n;i++)
{
if(q[i].op==1) //区间赋值
str.modify(1,1,tot,q[i].l,q[i].r,1);
else if(q[i].op==2)//区间清零
str.modify(1,1,tot,q[i].l,q[i].r,0);
else //区间反转
str.modify(1,1,tot,q[i].l,q[i].r,2);
int pos=str.find(1,1,tot,q[i].l,q[i].r);
// printf("pos=%d\n",pos);
// if(!pos) printf("%lld\n",rnk[tot]+1);
printf("%lld\n",rnk[pos]);
}
}
int main()
{
n=read();
cnt++,p[cnt]=a[cnt]=1;
for(int i=1;i<=n;i++)
q[i].op=read(),
cnt++,p[cnt]=a[cnt]=q[i].l=read(),
cnt++,p[cnt]=a[cnt]=q[i].r=read(),
cnt++,p[cnt]=a[cnt]=q[i].r+1;
discrete();
work();
return 0;
}