RT

下面是珂朵丽树的代码

#include<cstdio>
#include<algorithm>
#include<set>

#define Iter std::set<Node>::iterator

typedef long long ll;

const int N=1e5;

struct Node
{
	ll l,r;
	mutable bool v;

	Node(ll _l,ll _r=0,bool _v=0):l(_l),r(_r),v(_v){}
};

inline bool operator<(const Node& x,const Node& y)
{
	return x.l<y.l;
}

std::set<Node> s;
ll n;

inline void read(ll& x)
{
	x=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
}

inline Iter split(ll pos)
{
	Iter it=s.lower_bound(Node(pos));
	if(it->l==pos&&it!=s.end())return it;
	it--;
	ll l=it->l,r=it->r;
	bool v=it->v;
	s.erase(it);
	s.insert(Node(l,pos-1,v));
	return s.insert(Node(pos,r,v)).first;
}

inline void assign(ll l,ll r,bool v)
{
	Iter itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(Node(l,r,v));
}

inline void reverse(ll l,ll r)
{
	Iter itr=split(r+1),itl=split(l);
	for(Iter it=itl;it!=itr;it++)
		it->v^=1;
}

inline ll query()
{
	for(Iter it=s.begin();it!=s.end();it++)
		if(it->v==0)return it->l;
	return -1;
}

int main()
{
	read(n);
	s.insert(Node(1,1e18,0)); // 先插入一个 1e18 的区间
	while(n--)
	{
		ll opt,l,r;
		read(opt),read(l),read(r);
		if(opt==1)assign(l,r,1);
		if(opt==2)assign(l,r,0);
		if(opt==3)reverse(l,r);
		printf("%lld\n",query());
	}
	return 0;
}