总起 修炼了2天，终于差不多完成基础了，数据结构都是很灵活的，不仅是应用，而且写代码也是有很多值得思考的地方。而在平衡树中，旋转是核心的核心。
先总结一下吧。
先说明一些概念 键值，所谓的key，我一般用val表示，就是当前点存的值。
ind(ex)，引索，就是用平衡树要维护的东西，可能还用wei(ght)来表示。相当于普通序列中的下标。
虚拟节点：第n+1个点，放在所有点之前，让平衡树有头；第n+2个点，放在最后，让平衡树有尾。这两个点没有实际意义，用作连接。
siz(e)，以当前点为根的子树的点的个数，不包括虚拟点。
cnt，有时候不离散化要来统计相同key的点个数。
root或top，平衡树的根。
Treap 之前感觉splay有点难搞，所以先打一发treap。
treap的核心，就是每一个点的weight。它在保持搜索树同时，要维护weight，保持一个weight的小根堆。其中weight是随机生成的。（随机这种东西要记住啊！！！）
几个操作简介
1，旋转。只有单旋，很朴素，没什么好讲的；
2，插入一个点X。先像普通BST一样插入，然后当X成为了叶节点的时候，一步步把它像栈up上去，保持父亲的weight比儿子的大。
3，删除一个点X。其实有两种。1)把 X down到底下做成叶节点，直接删除，很简洁；2)把X up到顶分裂合并，这个比较麻烦。
4，分裂。即把一棵treap分成左右两边，其中满足BST的性质。这个后面splay再说。
5，合并。其实就是分裂反过来。
6，查找。可以利用size来查。也可以直接用BST的方式查。查找第K大，找元素都很方便。
优点是很明显的：十分容易调，超级简洁。很多都是递归完成，核心也很少。还能可持久化。
缺点：没有吧···
排序的应用代码
#include
#include
#include
using namespace std;
#define fo(i,j,k) for(i=j;
i<=k;
i++)
typedef long long ll;
const int N=2000005,mx=100000007;
const ll pri=1000007,mo=6451342;
//0 left 1 right
int siz[N],tr[N][2],up[N],wei[N],key[N],a[N],n,i,j,cnt[N],top,t1,pos,ans[N];
int pd(int x)
{
return (tr[up[x]][1]==x);
}
void update(int x)
{
siz[x]=siz[tr[x][0]]+siz[tr[x][1]]+cnt[x];
if (siz[39]==30)
{
pos=i;
}
}
void rotate(int x)
{
int y=up[x],z=pd(x);
up[x]=up[y];
if (up[y]) tr[up[y]][pd(y)]=x;
tr[y][z]=tr[x][1-z];
if (tr[x][1-z]) up[tr[x][1-z]]=y;
tr[x][1-z]=y;
up[y]=x;
if (top==y) top=x;
update(y);
update(x);
}
void insert(int x,int y,int z)
{
if (z==key[x])
{
siz[x]++;
cnt[x]++;
return;
}
if (x!=0) siz[x]++;
if (x==0)
{
t1++;
key[t1]=z;
wei[t1]=(ll)(z+100)*pri%mo;
siz[t1]=1;
up[t1]=y;
cnt[t1]++;
int kan=(z 应用在排序容易检验各种操作的正确性，容易拍。在最后的求答案中，怎么样求答案都是行的。比如分离后又合并等。
【平衡树学习小记】treap让我逐步建立了对于平衡树的思维方式。
Splay 数据结构优美的特点在于函数化，只要函数正确，维护的代码是很可打的。而Splay很灵活，操作很多，需要用脑想，去简洁化，然后就可以写得又爽又快。
splay没有什么拘束，ind或者说weight的值不一定要刻意维护，自己想怎么玩弄它就怎么玩，想想就很爽！
Splay的核心：单旋转与双旋转
单旋转 不管是左儿子还是右儿子旋转上去，我们都可以直接用一段代码完成，很明了，不记得了就画个图，找找套路。
void rotate(int x)
{
int y=up[x],z=pd(x);
//pd函数为判断节点X是它父亲的左儿子或者右儿子
down(y);
//下传懒标记
down(x);
//下传懒标记
up[x]=up[y];
if (up[y]) tr[up[y]][pd(y)]=x;
tr[y][z]=tr[x][1-z];
if (tr[y][z]) up[tr[y][z]]=y;
up[y]=x;
tr[x][1-z]=y;
update(y);
//更新节点信息
update(x);
//注意两个update的顺序
}双旋转 这是精华吧，网上的叙述很完备了，值得注意的是Zig-Zig时要先旋转父亲，再旋转儿子。
下面的splay函数，包括了双旋与单旋，而实质上都是单旋构成的。
void splay(int x,int y)
{
while (up[x]!=y)
{
if (up[up[x]]!=y)
if (pd(x)==pd(up[x])) rotate(up[x]);
else rotate(x);
rotate(x);
}
if (!y) root=x;
}插话：维护序列
splay维护序列，实际上就是把序列下标作为BST的ind，然后就可以乱搞了。想一想：如果要让一颗子树只包含下标为l~r要怎么搞。
其他重要操作
这一部分要学好，我觉得要操作和题目配合着看，效果更好，但限于时间只能打点操作了。
1，合并x,y。 两颗splay合起来，保证x的所有元素的ind比y的大（注：有时候，ind的值不用记的，也不用刻意维护，看情况用），只需要让x进行“光头处理”，即让x的根节点（谁做根没关系）只有左儿子。
这之后x直接把y的根作为右儿子就行了，同时注意总根为x的根。
就算对y进行光头处理再类似地做也是一点问题都没有的。
2，分离 随便搞搞，看题目来。
3，找最值 我们类似于线段树一样，给每个点x都定义一个minium，或者maxinum，表示以x为根的子树，key值的最值。
4，玩弄序列时，在不维护index的情况下找原序列下标为K的元素 我们不是有siz吗？对于根的左边，ind即使没有记录，我们也知道左子树的所有点ind比根小，所以实际上已经是有序的了。细节比较难以表述，其实挺容易想懂，不写了~~~
5，不维护index，翻转序列 我们要把原序列中下标为l~r的元素下标全部翻转，即r变成l，r-1变为l+1····很简单，只需要把l~r搞在一棵子树里，然后对于每个点直接交换左右子树位置即可。当然了，为了保证时间复杂度，打懒标记，到时候碰到才下传。
6，区间修改和单点修改 7，···· 感受
学了一会，就喜欢上了splay、treap，他们变化多端，splay可以搞LCT，treap可以可持久化，他们还都可以树套树···平时没事干，多多在脑海里splay一下，treap更新一下，会有收获。每次打的平衡树，都会根据实际情况变化，实在是有趣。
切题
JZOJ1149：又是排序，这次放splay
要记得每次操作都要SPLAY
#include
#include
#include
using namespace std;
#define fo(i,j,k) for(i=j;
i<=k;
i++)
typedef long long ll;
const int N=500005;
int tr[N][2],siz[N],up[N],key[N],index[N],i,j,n,root,t1,a[N],ans,kan;
int pd(int x)
{
return (tr[up[x]][1]==x);
}
void rotate(int x)
{
int y=up[x],z=pd(x);
up[x]=up[y];
if (up[x]) tr[up[x]][pd(y)]=x;
tr[y][z]=tr[x][1-z];
if (tr[x][1-z]) up[tr[x][1-z]]=y;
up[y]=x;
tr[x][1-z]=y;
}
void insert(int x,int y,int z,int bef)
{
if (!x)
{
t1++;
key[t1]=y;
index[t1]=z;
up[t1]=bef;
if (!bef) return;
if (t1>=34858)
{
t1=t1+1-1;
}
if (y JZOJ1960 最大值2，区间修改，区间询问。
#include
#include
#include
using namespace std;
#define fo(i,j,k) for(i=j;
i<=k;
i++)
typedef long long ll;
const int N=200005;
const int inf=2147483646;
int tr[N][2],val[N],ind[N],siz[N],mx[N],up[N],n,i,j,k,root,t1,last,a[N],x,y,kase,tmp,tp,pos,m,des[N],z;
void down(int x)
{
if (!x||!des[x]) return;
if (tr[x][0]) des[tr[x][0]]+=des[x];
if (tr[x][1]) des[tr[x][1]]+=des[x];
mx[x]+=des[x];
val[x]+=des[x];
des[x]=0;
}
void update(int x)
{
down(x);
down(tr[x][0]);
down(tr[x][1]);
mx[x]=max(val[x],max(mx[tr[x][0]],mx[tr[x][1]]));
}
int pd(int x)
{
return tr[up[x]][1]==x;
}
void rotate(int x)
{
int y=up[x],z=pd(x);
update(y);
update(x);
up[x]=up[y];
if (up[y]) tr[up[x]][pd(y)]=x;
tr[y][z]=tr[x][1-z];
if (tr[y][z]) up[tr[x][1-z]]=y;
up[y]=x;
tr[x][1-z]=y;
update(y);
update(x);
}
void splay(int x,int y)
{
while (up[x]!=y)
{
if (up[up[x]]!=y)
if (pd(x)==pd(up[x])) rotate(up[x]);
else
rotate(x);
rotate(x);
}
if (!y) root=x;
}
int find(int x,int y)
{
while (ind[x]!=y)
{
down(x);
if (y JZOJ3599 机械臂排序，涉及翻转
#include
#include
#include
using namespace std;
#define fo(i,j,k) for(i=j;
i<=k;
i++)
typedef long long ll;
const int N=200005,inf=2147483646;
struct re
{
int a,b;
}b[N];
int mn[N],tr[N][2],siz[N],val[N],up[N],n,i,j,l,r,root,t1,last,a[N],x,tmp,tp,z,des[N],dep[N],dur,base;
void down(int x)
{
if (!x) return;
if (des[x])
{
int z=tr[x][0];
tr[x][0]=tr[x][1];
tr[x][1]=z;
if (tr[x][0]) des[tr[x][0]]^=1;
if (tr[x][1]) des[tr[x][1]]^=1;
des[x]=0;
}
}
void update(int x)
{
down(tr[x][0]);
down(tr[x][1]);
mn[x]=min(mn[tr[x][0]],min(mn[tr[x][1]],val[x]));
siz[x]=siz[tr[x][0]]+siz[tr[x][1]]+dep[x];
}
int pd(int x)
{
return tr[up[x]][1]==x;
}
void rotate(int x)
{
int y=up[x],z=pd(x);
update(y);
update(x);
up[x]=up[y];
if (up[y]) tr[up[y]][pd(y)]=x;
tr[y][z]=tr[x][1-z];
if (tr[y][z]) up[tr[y][z]]=y;
up[y]=x;
tr[x][1-z]=y;
update(y);
update(x);
}
void splay(int x,int y)
{
while (up[x]!=y)
{
if (up[up[x]]!=y)
if (pd(x)==pd(up[x])) rotate(up[x]);
else rotate(x);
rotate(x);
}
if (!y) root=x;
}
int find(int x,int y)
{
int ret=0;
while (y==0||y!=0)
{
down(x);
if (ret+siz[tr[x][0]]+dep[x]>y)
x=tr[x][0];
else
if (ret+siz[tr[x][0]]+dep[x]==y)
break;
else
{
ret+=siz[tr[x][0]]+dep[x];
x=tr[x][1];
}
}
return x;
}
int getmin(int x)
{
down(x);
int ret=0;
while (val[x]!=mn[x]||(val[x]==mn[x]&&mn[tr[x][0]]==mn[x]))
{
if (!x) break;
if (mn[tr[x][0]]==mn[x]) x=tr[x][0];
else
{
ret+=siz[tr[x][0]]+dep[x];
x=tr[x][1];
}
down(x);
}
dur=val[x];
return ret+siz[tr[x][0]]+dep[x];
}
bool cmp(re a,re b)
{
return (a.a 题目不断更新···
