HNOI 2012 영원히 고향 이 없다

1550 단어 데이터 구조splay
제목 링크:https://www.luogu.org/problemnew/show/P3224
splay 계발 식 통합 템 플 릿, 작은 splay 는 큰 splay 에 꽂 고 감성 적 인 이해, 한 점 은 최대 logn 회, logn, n 점, nlognlogn 을 꽂 습 니 다 ~
#include
using namespace std;
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
const int N = 2e5+10;
int n,m,a[N];
int fa[N],rt[N];
inline int getfa(int x){//          
	return x^fa[x]?fa[x]=getfa(fa[x]):x;
}
struct Splay{
	int p[N],ch[N][2];
	int cnt,vl[N],idx[N],siz[N];
	#define Ls(x) ch[x][0]
	#define rs(x) ch[x][1]
	#define maintain(x) siz[x]=siz[Ls(x)]+siz[rs(x)]+1
	inline void rotate(int x){
		int f=p[x],gf=p[f],tp=rs(f)==x,son=ch[x][!tp];
		ch[p[son]=f][tp]=son,maintain(f);
		ch[p[f]=x][!tp]=f,maintain(x);
		ch[p[x]=gf][rs(gf)==f]=x;
	}
	inline void splay(int x,int goal,int &root){
		if(x==goal)return ;
		while(p[x]^goal){
			if((p[p[x]]^goal)&&((rs(p[p[x]])==p[x])==(rs(p[x])==x)))rotate(p[x]);
			rotate(x);
		}
		if(!goal)root=x;
	}
	inline void newnode(int x,int k,int Fa,int Idx){
		idx[x]=Idx,siz[x]=1,vl[x]=k,p[x]=Fa;
	}
	inline void insert(int &x,int k,int Fa,int Idx,int &root){
		if(!x)return newnode(x=++cnt,k,Fa,Idx),splay(x,0,root),void();
		insert(ch[x][vl[x]

좋은 웹페이지 즐겨찾기