动态开点线段树板题求调
  • 板块CF817F MEX Queries
  • 楼主Orwell
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/3/20 14:52
  • 上次更新2024/3/20 18:21:48
查看原帖
动态开点线段树板题求调
1034022
Orwell楼主2024/3/20 14:52

RT,WA on 1515。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN=1000000000000000001ll;
ll q;
ll cnt;
int rt;
struct tree
{
	ll sz;
	bool cover,clean,reverse;
	int son[2];
	#define ls(id) tr[id].son[0]
	#define rs(id) tr[id].son[1]
}tr[10000005];
//cover清空clean、reverse标记
//clean清空cover、reverse标记
//reverse正常执行即可
void add_cover(ll id,ll l,ll r)
{
	tr[id].clean=tr[id].reverse=0;
	tr[id].cover=1;tr[id].sz=r-l+1;
}
void add_clean(ll id,ll l,ll r)
{
	tr[id].cover=tr[id].reverse=0;
	tr[id].clean=1;tr[id].sz=0;
}
void add_reverse(ll id,ll l,ll r)
{
	if(tr[id].clean)
		add_cover(id,l,r);
	else if(tr[id].cover)
		add_clean(id,l,r);
	else
	{
	tr[id].reverse^=1;
	tr[id].sz=r-l+1-tr[id].sz;	
	}
}
void pushdown(ll id,ll l,ll r)
{
	ll mid=l+r>>1ll;
	if(tr[id].cover)
	{
		if(!ls(id))ls(id)=++cnt;
		if(!rs(id))rs(id)=++cnt;
		add_cover(ls(id),l,mid);
		add_cover(rs(id),mid+1,r);
		tr[id].cover=0;
	}
	if(tr[id].clean)
	{
		if(!ls(id))ls(id)=++cnt;
		if(!rs(id))rs(id)=++cnt;
		add_clean(ls(id),l,mid);
		add_clean(rs(id),mid+1,r);
		tr[id].clean=0;
	}
	if(tr[id].reverse)
	{
		if(!ls(id))ls(id)=++cnt;
		if(!rs(id))rs(id)=++cnt;
		add_reverse(ls(id),l,mid);
		add_reverse(rs(id),mid+1,r);
		tr[id].reverse=0;
	}
}
void pushup(ll id)
{
	tr[id].sz=tr[ls(id)].sz+tr[rs(id)].sz;
}
void update(int &id,ll l,ll r,ll ml,ll mr,ll opt)
{
	if(!id)id=++cnt;
	if(ml<=l&&r<=mr)
	{
		if(opt==1)add_cover(id,l,r);
		else if(opt==2)add_clean(id,l,r);
		else add_reverse(id,l,r);
		return;
	}
	pushdown(id,l,r);
	ll mid=l+r>>1ll;
	if(ml<=mid)update(ls(id),l,mid,ml,mr,opt);
	if(mr>mid)update(rs(id),1+mid,r,ml,mr,opt);
	pushup(id);
}
ll query(ll id,ll l,ll r)
{
	if(l==r)return l;
	if(!id)return l;
	pushdown(id,l,r);
	ll mid=l+r>>1ll,res=0;
	if(tr[ls(id)].sz==mid-l+1)
	res=query(rs(id),mid+1,r);
	else res=query(ls(id),l,mid);
	pushup(id);
	return res;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>q;
	ll l,r,opt;
	while(q--)
	{
		cin>>opt>>l>>r;
		update(rt,1,MAXN,l,r,opt);
		if(tr[rt].sz!=0)
		cout<<query(rt,1,MAXN)<<'\n';
		else cout<<"1\n";
	}
}
2024/3/20 14:52
加载中...