实时更新一下蒟蒻的OI学习日记：

$SB$才写$splay$，都给我写$fhq-Treap$！！！！！

$read()$注意一点不要写在函数传参里！！！

可持久化太舒服了！！！！

LCT!!

常用：

#include<bits/stdc++.h>//其实并不常用，通常都分开写，但有的时候分开写真的烦
#define ll long long
#define il inline
#define cit const int
#define cll const long long
#define vd void
#define bl bool
#define N 100010 //视题目要求
#define F(k) for(int i=1;i<=k;i++) //通常都直接用这一个，下面那个很少
//#define up(i,a,b) for(int i=a;i<=b;i++)
#define W(l) for(int i=h[l];i!=0;i=e[i].D)//图论的玩意，遍历链式前向星
#define mid(l,r) (l+r>>1)
#define Z (k<<1)//线段树
#define Y (k<<1|1)
#define ln(p) write(p),putchar(10)//带换行的输出数字
#define Cp(p) write(p),putchar(32)//带空格的输出数字
//#define int long long //过不了的时候会用，所以main函数通常都是signed
using namespace std;//事实上可以不用
il ll read(){
	ll x=0;
	bool w=1;
	char ch=getchar();
	while(ch<48||ch>57){
		if(ch==45) w=0;
		ch=getchar();
	}while(ch>47&&ch<58){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return w?x:(-x);
}
il vd write(ll x){
	if(x<0){
		putchar(45);
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+48);
}
signed main(){
	return 0;
}

$splay$蒻了，更新$LCT$!!!

struct tree{
	int fa,son[2];
	bl rev;
	ll v,xr;
	tree(){fa=son[0]=son[1]=v=xr=rev=0;}
}t[N];
struct LCT{
	tree t[N];
	int st[N],tp;
	il bl Froot(int k){return t[t[k].fa].son[0]==k||t[t[k].fa].son[1]==k;}
	il bl get(int k){return (k==t[t[k].fa].son[1]);}
	il vd pushup(int k){
		t[k].xr=t[t[k].son[0]].xr^t[t[k].son[1]].xr^t[k].v;
	}
	il vd rever(int k){
		swap(t[k].son[0],t[k].son[1]);
		t[k].rev^=1;
	}
	il vd pushdown(int k){
		if(t[k].rev){
			if(t[k].son[0]) rever(t[k].son[0]);
			if(t[k].son[1]) rever(t[k].son[1]);
			t[k].rev=0;
		}
	}
	il vd rotate(int k){
		int f=t[k].fa,ff=t[f].fa;
		bl fson=get(f),kson=get(k);
		t[k].fa=ff;
		if(Froot(f)) t[ff].son[fson]=k;
		t[t[k].son[kson^1]].fa=f,t[f].son[kson]=t[k].son[kson^1];
		t[f].fa=k,t[k].son[kson^1]=f;
		pushup(f),pushup(k);
	}
	il vd splay(int k){
		st[tp=1]=k;
		int x=k;
		while(Froot(x)) x=t[x].fa,st[++tp]=x;
		while(tp) pushdown(st[tp--]);
		while(Froot(k)){
			int f=t[k].fa;
			if(!Froot(f)) rotate(k);
			else if(get(f)==get(k)) rotate(f),rotate(k);
			else rotate(k),rotate(k);
		}
		pushup(k);
	}
	il vd access(int k){
		for(int i=0;k;i=k,k=t[k].fa){
			splay(k);
			t[k].son[1]=i;
			pushup(k);
		}
	}
	il vd makeroot(int k){
		access(k);
		splay(k);
		rever(k);
	}
	il int findroot(int k){
		access(k);
		splay(k);
		while(t[k].son[0]){
			pushdown(k);
			k=t[k].son[0];
		}
		splay(k);
		return k;
	}
	il vd split(int k,int f){
		makeroot(k);
		access(f);
		splay(f);
	}
	il vd link(int k,int f){
		makeroot(k);
		if(findroot(f)!=k) t[k].fa=f;
	}
	il vd cut(int k,int f){
		split(k,f);
		if(t[f].son[0]==k&&!t[k].son[1]){
			t[f].son[0]=0;
			t[k].fa=0;
		}
	}
}lct;

随机壁纸