第一次写splay。。

首先你必须要明确一些事情 -> 坚信splay不难， 好吧， 下面推荐一篇， 作为入门， 之后再做一下这道题(其实并不需要splay)， 就可以开始splay之路了

这道题没什么好解释， 裸题， 中文的， 不需要解释了

参考了cxlove的博客

code->

#include 
     
      using namespace std;#define N 100005#define oo 1<<30#define rep(i, s, t) for(int i = s; i <= t; ++i)int n, tot, root, key[N];struct Splay{	int fa[N], ch[N][2];	void newnode(int &r, int father, int w) {		r = ++tot;		fa[r] = father;		key[r] = w;		ch[r][0] = 0;		ch[r][1] = 0;	}	void rotate(int x, int kind) {		int y = fa[x];		ch[y][!kind] = ch[x][kind]; fa[ch[y][!kind]] = y;		if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y] = x;		fa[x] = fa[y]; fa[y] = x; ch[x][kind] = y;	}	void splay(int u) {		while(fa[u]) {			if(!fa[fa[u]]) rotate(u, ch[fa[u]][0] == u);			else {				int v = fa[u];				int kind = ch[fa[v]][0]==v;				if(ch[v][kind] == u) rotate(u, !kind), rotate(u, kind);				else rotate(v, kind), rotate(u, kind);			}		}		root = u;	}	int insert(int k) {		int u = root;		if(key[root] ^ k) {			while(ch[u][key[u]