「SCOI2014」方伯伯的 OJ 解题报告

「SCOI2014」方伯伯的 OJ

和列队有点像，平衡树点分裂维护即可

但是需要额外用个set之类的对编号查找点的位置

插入完了后记得splay，删除时注意特判好多东西

---

Code:

#include <cstdio>

#include <cctype>

#include <set>

const int N=2e5+10;

template <class T>

void inline read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

int siz[N],ch[N][2],L[N],R[N],par[N],tot,root;

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

int identity(int now){return ch[fa][1]==now;}

void updata(int now){siz[now]=siz[ls]+siz[rs]+R[now]+1-L[now];}

void Rotate(int now)

{

	int p=fa,typ=identity(now);

	connect(p,ch[now][typ^1],typ);

	connect(par[p],now,identity(p));

	connect(now,p,typ^1);

	updata(p),updata(now);

}

void splay(int now,int to)

{

	to=par[to];

	if(!to) root=now;

	for(;fa!=to;Rotate(now))

		if(par[fa]!=to)

			Rotate(identity(now)^identity(fa)?now:fa);

}

struct yuucute

{

	int x,id;

	yuucute(){}

	yuucute(int X,int Id){x=X,id=Id;}

	bool friend operator <(yuucute a,yuucute b){return a.x<b.x;}

	bool friend operator ==(yuucute a,yuucute b){return a.x==b.x;}

};

std::set <yuucute> s;

std::set <yuucute>::iterator it;

#define yuulovely 1

int New(int l,int r)

{

    siz[++tot]=r+1-l,L[tot]=l,R[tot]=r;

    return tot;

}

int getnum(int x)

{

	it=--s.upper_bound(yuucute(x,yuulovely));

	return it->id;

}

void split(int now,int x)

{

    if(L[now]==R[now]) return;

	s.erase(yuucute(L[now],yuulovely));

	s.insert(yuucute(x,now));

	int lson=ls,rson=rs;

	if(L[now]<x)

	{

		int lp=New(L[now],x-1);

		s.insert(yuucute(L[now],lp));

		connect(now,lp,0);

		connect(lp,lson,0);

		updata(lp);

	}

	if(x<R[now])

	{

		int rp=New(x+1,R[now]);

		s.insert(yuucute(x+1,rp));

		connect(now,rp,1);

		connect(rp,rson,1);

		updata(rp);

	}

	L[now]=R[now]=x;

}

void insl(int now,int ins)

{

	++siz[now];

	if(ls) insl(ls,ins);

	else connect(now,ins,0);

}

void insr(int now,int ins)

{

	++siz[now];

	if(rs) insr(rs,ins);

	else connect(now,ins,1);

}

int getlef(int now)

{

	if(ls) return getlef(ls);

	return now;

}

void erase(int now)

{

	if(!rs) {par[root=ls]=0,ls=0,updata(now);return;}

	splay(root=getlef(rs),rs);

	connect(root,ls,0);

	updata(root),par[root]=0;

	ls=rs=0,updata(now);

}

int getrank(int now,int &x)

{

	if(siz[ls]>=x) return getrank(ls,x);

	x-=siz[ls];

	if(x<=R[now]-L[now]+1) return now;

	x-=R[now]-L[now]+1;

	return getrank(rs,x);

}

int main()

{

    freopen("data.in","r",stdin);

    freopen("data.out","w",stdout);

	int n,m;

	read(n),read(m);

	root=New(1,n);

	s.insert(yuucute(1,root));

	int op,x,y,las=0;

	for(int i=1;i<=m;i++)

	{

		read(op),read(x);

		x-=las;

		if(op==1)

		{

			read(y),y-=las;

			int now=getnum(x);

			splay(now,root);

			printf("%d\n",las=siz[ls]+x+1-L[now]);

			split(now,x);

			L[now]=R[now]=y;

			s.erase(yuucute(x,yuulovely));

			s.insert(yuucute(y,now));

		}

		else if(op==2)

		{

			int now=getnum(x);

			splay(now,root);

			printf("%d\n",las=siz[ls]+x+1-L[now]);

			split(now,x);

			erase(now);

			insl(root,now);

			splay(now,root);

		}

		else if(op==3)

		{

			int now=getnum(x);

			splay(now,root);

			printf("%d\n",las=siz[ls]+x+1-L[now]);

			split(now,x);

			erase(now);

			insr(root,now);

			splay(now,root);

		}

		else

		{

			int now=getrank(root,x);

			printf("%d\n",las=x+L[now]-1);

			splay(now,root);

		}

	}

	return 0;

}

---

2019.2.23