@

前言

\(Splay\)可以说是一个常数挺优秀的一个支持区间操作的平衡树，神奇的是在随机数据的情况下，有时候他能跑得玄学一般的快，这也取决于他复杂度玄学的证明方法，当然，他的\(O(mlogn)\)复杂度并非上限，而是均分，也就是可以卡。而我学他也只是单纯的用于LCT，因为在LCT中，他是能做到使得LCT的复杂度为\(mlogn\)的我所认知的唯一一颗平衡树。

当然，单点操作我也是用\(Splay\)，毕竟\(FHQ\)真的在单点操作的时候特别容易出锅，但同时FHQ的区间修改又比较强悍，代码短不容易出错，都是\(FHQ\)的好处，而且支持可持久化。

真正的大佬应该再学一个\(SBT\)，单点修改跑的飞快且代码听说也挺短的，我们机房就有个大佬是这样的，不过他不喜欢\(Splay\)，\(LCT\)也不打\(Splay\)，Orz。

Splay

Splay是什么，简单来说就是把一个点暴力跳到根节点来以此暴力玄学达到\(O(nlogn)\)的复杂度，听起来很玄学，实际上还是挺玄学好用的。

例题

时间限制: 2 Sec 内存限制: 128 MB 【题意】 写一种数据结构，来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，应只删除一个) 3. 查询x数的排名(若有多个相同的数，应输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数) 注意：数据保证有解，无需特判 【输入格式】 第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号。 （1<=opt<=6，n < = ， 所有数字均在-10^7到10^7内 ） 【输出格式】 对于操作3,4,5,6每行输出一个数，表示对应答案 【样例输入】 8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1 【样例输出】 2 20 20 20

学习Splay

我们考虑一个类似堆得数据结构，堆不是要求儿子节点比父亲节点大（小）就行了吗，那么平衡树就是要求左字数所有节点的关键字小于父亲节点，右字数的节点大于父亲节点，也就是说这棵树的中序遍历是按关键字从小到大排序的，很明显，关键字就是决定树的形态的一个值。

这就是一棵较为典型的平衡树的样子。

而平衡树的复杂度取决于平衡树的层数，层数越大，时间越慢。

因为Splay其实可以说得上是用了大量的翻转来实现平衡的一棵树，所以我们现在先学习翻转。

翻转

总所周知，许多树的中序遍历都是一样的，也就是说连一个序列，Splay的样子也是可能有变化的，那么我们就来学一学如何利用一棵现有的Splay转换成其他形态的Splay。

我们仍然以上张图为例：

这就是一个经典的左旋右旋的例子。

很明显是一个\(O(1)\)的操作。

而旋一个点的话，就是看他在父亲的那个儿子，在左儿子就右旋，在右儿子就左旋。

inline void update(int x){tr[x].c/*子树内点的个数*/=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+tr[x].n/*与x号点点权相同的有多少个点*/;} inline int chk(int x){return tr[tr[x].f].son[1]==x;}//判断自己是什么儿子 inline void rotate(int x) { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1/*0为左旋，1为右旋*/,son=tr[x].son[w]; int r,R; r=son;R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; update(f);update(x); }

splay

Splay的核心操作splay，QMQ。

就是把\(x\)一直旋，直到\(y\)为\(x\)的父亲，不过要求\(y\)一定是\(x\)的祖先，那么分几种情况：

1. \(x\)为\(fa_{x}\)的左（右）儿子，\(fa_{x}\)为\(fa_{fa_{x}}\)的左（右）儿子，那么就先旋\(fa_{x}\)，再旋\(x\)。
2. \(x\)为\(fa_{x}\)的右（左）儿子，\(fa_{x}\)为\(fa_{fa_{x}}\)的左（右）儿子，那么就旋\(x\)两次。
3. 如果\(y=fa_{fa_{x}}\)，那么旋一下\(x\)就行了。

很多人会不理解一操作，其实这是某大佬实验得出这样会快！

一操作的图（以一条链为例子，都是关键字为\(1\)的点旋到\(0\)的儿子，也就是根节点）：

先旋父亲，再旋儿子：

连旋两次:

我们发现，一个层数为\(4\),一个层数为\(5\)，所以先旋父亲，再旋儿子会使得Splay更平衡，其实我们可以这么想，旋转一个节点，相当于把父亲节点的东西装进我这个节点中，那么如果把一些点装进目前的父亲，一些点装进自己里面，不就会使得树更平衡了吗？

但是二操作为什么又不敢这样了呢。

二操作的情况但是先旋父亲，再旋儿子（以一条链为例子，关键字为\(1\)的点旋到\(0\)的儿子，也就是根节点）：

会发现这个节点在旋了两次的情况下，只上了一层，而且理论上将树的层数不会更优，如下图，

我们会发现不管父亲节点怎么旋转，\(4\)的层数就是不变，且树的总体层数也不变，也就是说其实旋父亲是没意义的。

但是又有人问为什么不只旋一次，有时候只旋一次以后就会出现操作一了，这样不会更优吗？

确实可能会更优，但是这是牺牲了一次判断的结果，而且最多就多一层或两层，使得慢得更慢，快得更快，而我们寻求的是一个综合性，所以旋两次也莫得多大问题。

那么这样不就好起来了吗？

inline void splay(int x,int fa) { while(tr[x].f!=fa) { int f=tr[x].f,ff=tr[f].f; if(ff==fa)rotate(x);//操作三 else rotate(chk(x)^chk(f)?x:f),rotate(x);//三目运算符缩减操作一与操作二。 } if(!fa)root=x; }

求x的排名

这不是很简单吗，跳Splay不就行了？如果跳右子树，答案就加上左子树的树的个数。

然后把找到的点splay上去。

inline int findip(int d)//找到大于d且最接近d的节点或者小于d且最接近d { int x=root; while(tr[x].d!=d) { if(!tr[x].son[tr[x].d<d])break; x=tr[x].son[tr[x].d<d]; } return x; } inline int findpaiming(int d)//这种方法仅限于存在这个数字的时候可以这么用 { int x=findip(d);splay(x,0); return tr[tr[x].son[0]].c+1; }

提一提，findip不一定会找到最接近\(d\)的点，但是能保证不会有点权是卡在\(d\)与\(tr[x].d\)之间的。

求排名为x的数字

一样子，跳一跳，跳右子树就将\(x\)减去左子树点的个数。

然后把找到的点splay上去。

inline int findkey(int d)//暴力往下跳 { int x=root; while(1) { if(d<=tr[tr[x].son[0]].c)x=tr[x].son[0]; else if(d<=tr[tr[x].son[0]].c+tr[x].n)break; else d-=tr[tr[x].son[0]].c+tr[x].n,x=tr[x].son[1]; } splay(x,0);//别忘splay维护形态 return tr[x].d; }

前驱后继

找到最接近\(d\)的点，并且splay，看看是不是前驱（后继），是就return，不是的话就往左（右）子树跳，因为是根节点，所以不需要考虑根的情况。

另外一种求法在可持久化FHQ中会写到。

inline int prep(int d)//后继 { int x=findip(d);splay(x,0); if(d<=tr[x].d && tr[x].son[0]) { //因为是最接近d的值，且把相同的点权压到了一个点上，所以不可能存在小于等于tr[x].d且大于等于d的情况，所以左儿子肯定是小于d的 x=tr[x].son[0];while(tr[x].son[1])x=tr[x].son[1]; } if(d<=tr[x].d)x=0; return tr[x].d; } inline int qian(int d)//前驱 { int x=findip(d);splay(x,0); if(d>=tr[x].d && tr[x].son[1]) { //同理 x=tr[x].son[1];while(tr[x].son[0])x=tr[x].son[0]; } if(d>=tr[x].d)x=0; return tr[x].d; }

插点

首先，如果我们找的到一个点权和新插点的点权相等，那么直接\(c,n++\)都可以，但是如果找不到的话，那么就找到最接近的点，直接添加为这个点的儿子，考虑最接近的点为\(x\)，新加点的点权为\(d\)的话，那么\(tr[x].d<d\)的话，\(d\)就会添加到右儿子，右儿子有没有可能有数字？有的话findip不就跳了吗，那可不可能跳左儿子？\(tr[x].d\)都已经小于\(d\)了，不会跳左儿子啦。

而\(tr[x].d>d\)也可以以此类推，也就是说findip一下不就可以了吗。

然后记得把新点或者相同点权的点splay一下

inline void ins(int d) { if(!root){add(d,0);root=len;return ;}//没有点 int x=findip(d); if(tr[x].d==d)tr[x].n++,update(x),splay(x,0);//相同点权 else add(d,x),update(x),splay(len,0); }

删点

这又是一个麻烦的操作，首先我们仍然findip然后splay一下。

这个点就到了根节点，如果这个点的左子树或右子树为空的话，\(root\)直接更新就行了。

但是不是的话，就会特别的麻烦，我们需要找到左子树最大的点，也就是前驱，然后把他旋到左子树的根，那么左儿子的右子树不就没了吗，那么就可以把\(root\)的右子树挪过去，然后取消左儿子与\(root\)的关联就可以了。

inline void del(int d) { int x=findip(d);splay(x,0); if(tr[x].n!=1)tr[x].n--,tr[x].c--; else if(!tr[x].son[0] && !tr[x].son[1])root=0; else if(!tr[x].son[0] && tr[x].son[1]){root=tr[x].son[1];tr[root].f=0;} else if(tr[x].son[0] && !tr[x].son[1]){root=tr[x].son[0];tr[root].f=0;}//前面都是各种简单的情况 else { int p=tr[x].son[0];while(tr[p].son[1])p=tr[p].son[1];//前驱 splay(p,x);//splay上去 tr[p].f=0;tr[p].son[1]=tr[x].son[1];update(p); tr[tr[x].son[1]].f=p; root=p;//让p当根节点 } }

代码

#include<cstdio> #include<cstring> #define N using namespace std; int root; struct node { int d,n,f,c,son[2]; }tr[N];int len; inline int chk(int x){return tr[tr[x].f].son[1]==x;} inline void update(int x){tr[x].c=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+tr[x].n;} inline void add(int d,int f) { len++; tr[len].c=tr[len].n=1;tr[len].d=d;tr[len].f=f; tr[f].son[d>tr[f].d]=len; } inline void rotate(int x)//翻转 { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1,son=tr[x].son[w]; int r,R; r=son;R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; update(f);update(x); } inline void splay(int x,int fa)//splay { while(tr[x].f!=fa) { int f=tr[x].f,ff=tr[f].f; if(ff==fa)rotate(x); else rotate(chk(x)^chk(f)?x:f),rotate(x); } if(!fa)root=x; } inline int findip(int d) { int x=root; while(tr[x].d!=d) { if(!tr[x].son[tr[x].d<d])break; x=tr[x].son[tr[x].d<d]; } return x; } inline void ins(int d) { if(!root){add(d,0);root=len;return ;} int x=findip(d); if(tr[x].d==d)tr[x].n++,update(x),splay(x,0); else add(d,x),update(x),splay(len,0); } inline void del(int d) { int x=findip(d);splay(x,0); if(tr[x].n!=1)tr[x].n--,tr[x].c--; else if(!tr[x].son[0] && !tr[x].son[1])root=0; else if(!tr[x].son[0] && tr[x].son[1]){root=tr[x].son[1];tr[root].f=0;} else if(tr[x].son[0] && !tr[x].son[1]){root=tr[x].son[0];tr[root].f=0;} else { int p=tr[x].son[0];while(tr[p].son[1])p=tr[p].son[1]; splay(p,x); tr[p].f=0;tr[p].son[1]=tr[x].son[1];update(p); tr[tr[x].son[1]].f=p; root=p; } } inline int findpaiming(int d) { int x=findip(d);splay(x,0); return tr[tr[x].son[0]].c+1; } inline int findkey(int d) { int x=root; while(1) { if(d<=tr[tr[x].son[0]].c)x=tr[x].son[0]; else if(d<=tr[tr[x].son[0]].c+tr[x].n)break; else d-=tr[tr[x].son[0]].c+tr[x].n,x=tr[x].son[1]; } splay(x,0); return tr[x].d; } inline int prep(int d) { int x=findip(d);splay(x,0); if(d<=tr[x].d && tr[x].son[0]) { x=tr[x].son[0];while(tr[x].son[1])x=tr[x].son[1]; } if(d<=tr[x].d)x=0; return tr[x].d; } inline int qian(int d) { int x=findip(d);splay(x,0); if(d>=tr[x].d && tr[x].son[1]) { x=tr[x].son[1];while(tr[x].son[0])x=tr[x].son[0]; } if(d>=tr[x].d)x=0; return tr[x].d; } int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y;scanf("%d%d",&x,&y); if(x==1)ins(y); else if(x==2)del(y); else if(x==3)printf("%d\n",findpaiming(y)); else if(x==4)printf("%d\n",findkey(y)); else if(x==5)printf("%d\n",prep(y)); else printf("%d\n",qian(y)); } return 0; }

区间操作

区间操作我都是用FHQ的，但是也提一提。

区间操作也是同样打标记，然后在splay的时候从下往上传标记，或者在其他地方。

下传标记要看情况直接修改儿子节点，比如区间加，那么我们下传\(x\)标记的时候要直接改变\(x\)左右儿子的key值，否则如果他的某个儿子没有访问到，然后update一下就出锅了，当然也有标记直接修改\(x\)的子树就行了，不用去看儿子的子树，比如翻转标记。

如果要搞区间\([l,r]\)，首先Splay维护的是位置，同时将\(l-1\)旋上根节点，然后将\(r\)旋到\(l-1\)的右儿子，那么根节点右儿子以及右儿子的左子树就是这个区间了，然后打个标记。

具体实现看你们的了，要学的话去看看其他博主的实现，在这只提供思路，就不一一赘述。

小结

可以发现，复杂度都是与层数有关的，有人证明过，Splay的复杂度为\(O(mlogn)\)，但是常数。。。

FHQ Treap

一听，treap?不就是随机数的那位？没错，Treap是在维护\(key\)为平衡树的情况下，维护随机权值（建点时随机赋予的）呈小根堆的形式，普通的Treap也是旋转实现，但是我不会QAQ，常数也挺优秀，但是Treap不能区间操作，因为不够灵活，相反，FHQ Treap就是非旋Treap，利用分裂合并来进行神奇操作，而且分裂合并的灵活性让他可以支持区间操作，也就可以维护LCT（比Splay多个\(log\)，其实只要能维护区间的树貌似都能维护LCT吧QMQ），因为不用旋转，所以共用某个节点也是可以的，所以又支持可持久化，唯一的缺点就是常数比Splay还大QAQ，但是区间操作貌似都海星。

例题

例题

题目描述： 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 插入x数 删除x数(若有多个相同的数，因只删除一个) 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 查询排名为x的数 求x的前驱(前驱定义为小于x，且最大的数) 求x的后继(后继定义为大于x，且最小的数) 输入格式： 第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1≤opt≤6) 输出格式 对于操作3,4,5,6每行输出一个数，表示对应答案 输入输出样例： 输入： 10 1  4 1 1  1  1  1 84185 1 89851 6 81968 1  5  输出：  84185  说明/提示： 时空限制：1000ms,128M 1.n的数据范围：n≤ 2.每个数的数据范围：[-10^7,10^7] 来源：Tyvj1728 原名：普通平衡树

学习FHQ Treap

平衡树的基本知识就不提了，直接进入核心操作，不过顺便提一提，我的FHQ没有合并相同的点权，也就是说左右子树有可能存在与根节点相同点权的点。

同时下面都是利用merge以及spilt的操作实现的，代码量短，常数大。

常数较小的操作详见可持久化FHQ。

每个点都有些什么

每个点有关键字，这点可以知道，但是别忘了建点的时候给每个点一个rand()值，称作val随机权值。

分裂

假设我们现在要把一棵平衡树分裂成两棵树，一棵所有节点的关键字小于等于\(k\)，另外一棵则都大于\(k\)。

先放上一个图：

请把方框中的\(9\)看成\(7.5\)这是远洋大佬博客上的图片，似乎作图的时候标错了，圆圈中的数字为关键字，旁边的小字为随机权值。

那么我们发现两棵树的方框指的是什么？

指的是如果要往树内加节点就在这个地方加，所以在实现中打了引用，这里姑且称作\(x,y\)。

而在原树中也有一个指针会从根节点一直指到叶子结点，姑且称为\(now\)。

1. \(key[now]<=k\)，那么说明这个点以及左子树都可以扔到\(x\)，那么\(x=now\)，那么\(now\)就跳到\(son[now][1]\)继续分裂，同时因为只扔了左子树给\(x\)，右子树怎么办？那么\(x\)也跳到\(son[x][1]\)，以后有子树就直接扔到\(tr[x].rc\)代替\(x\)的右子树吧。
2. \(key[now]>k\)，那么说明这个点以及右子树都可以扔到\(y\)，那么\(y=now\)，那么\(now\)就跳到\(son[now][0]\)继续分裂，同时因为只扔了右子树给\(y\)，左子树怎么办？那么\(y\)也跳到\(son[y][0]\)，以后有子树就直接扔到\(tr[y].lc\)代替\(y\)的左子树吧。

拷贝怪QMQ。

inline void update(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}//上传 void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { if(key[now]/*关键字*/<=k)x=now,spilt(son[x][1],k,son[x][1],y),update(x); else y=now,spilt(son[y][0],k,x,son[y][0]),update(y); } }

合并

如果说分裂是用关键字。

合并就是用随机权值，我们仍然用两个指针\(x,y\)，指向要合并的两棵树的根节点，同时严格要求第一棵树内的节点的关键字小于等于第二棵树内的节点的关键字。

继续以上图为例（\(9\)看做\(7.5\)）：

我们比较随机权值，如果\(val[x]<=val[y]\)的话，那么就把\(x\)的左子树即\(x\)加入到树中，同时\(son[x][1]=merge(son[x][1],y)\)，且\(return\) \(x\)。

\(val[x]>val[y]\)则反之。

int merge(int A,int B) { if(!A || !B)return A+B;//返回非0的那个数字 else { if(val[A]<=val[B])son[A][1]=merge(son[A][1],B); else son[B][0]=merge(A,son[B][0]),A^=B^=A^=B/*返回的时候交换一下，省代码量*/; update(A);return A; } }

查询k的排名

我们spilt(root,k-1,x,y)，然后返回size[x]+1。

int findkey(int d) { int x,y;spilt(root,d-1,x,y); int ans=size[x];root=merge(x,y); return ans+1; }

查询排名为k的数字

可以再打个\(spilt\)表示的是按照排名分裂（也就是看看左子树的个数+1有没有小于\(k\)，如果是，就分裂然后跳右儿子，同时\(k\)减一下，否则跳左儿子，\(k\)不减，因为满足合并要求，不用多打合并），但是太麻烦，代码量差不多又慢，那么我们采取Splay的方法。

int findpaiming(int d) { int x=root; while(1) { if(d<=size[son[x][0]])x=son[x][0]; else if(d<=size[son[x][0]]+1)break; else d-=size[son[x][0]]+1,x=son[x][1]; } return key[x]; }

前驱后继

前驱就按d-1分裂成\(x,y\)，然后在\(x\)中找最大值。

后继就按\(d\)分裂，然后在\(y\)中找最小值。

int findqian(int d) { int x,y;spilt(root,d-1,x,y); int p=x;while(son[p][1])p=son[p][1]; root=merge(x,y); return key[p]; } int findhou(int d) { int x,y;spilt(root,d,x,y); int p=y;while(son[p][0])p=son[p][0]; root=merge(x,y); return key[p]; }

插入

以\(d\)插入要怎么插？

我们只要新增一个节点\(z\)，然后按\(d\)分裂成\(x,y\)，然后合并\(x,z\)，再把\(y\)合并进去。

void ins(int d) { len++; key[len]=d;val[len]=rand();size[len]=1; int x,y;spilt(root,d,x,y); x=merge(x,len);root=merge(x,y); }

删除

这里的删除舒服的一批，只要按\(d-1\)、\(d\)分别分成\(x,y,z\)，然后\(y=merge(son[y][0],son[y][1])\)，就完美的将一个\(d\)抹除了，然后再合并回去。

void del(int d) { int x,y,z;spilt(root,d-1,x,y);spilt(y,d,y,z); y=merge(son[y][0],son[y][1]);root=merge(merge(x,y),z); }

代码

时间复杂度：\(O(mlogn)\)

#include<cstdio> #include<cstring> #include<cstdlib> #define N using namespace std; int key[N],val[N],son[N][2],n,size[N],len,root; inline void update(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;} void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { if(key[now]<=k)x=now,spilt(son[x][1],k,son[x][1],y),update(x); else y=now,spilt(son[y][0],k,x,son[y][0]),update(y); } } int merge(int A,int B) { if(!A || !B)return A+B;//返回非0的那个数字 else { if(val[A]<=val[B])son[A][1]=merge(son[A][1],B); else son[B][0]=merge(A,son[B][0]),A^=B^=A^=B/*返回的时候交换一下，省代码量*/; update(A);return A; } } void ins(int d) { len++; key[len]=d;val[len]=rand();size[len]=1; int x,y;spilt(root,d,x,y); x=merge(x,len);root=merge(x,y); } void del(int d) { int x,y,z;spilt(root,d-1,x,y);spilt(y,d,y,z); y=merge(son[y][0],son[y][1]);root=merge(merge(x,y),z); } int findpaiming(int d) { int x=root; while(1) { if(d<=size[son[x][0]])x=son[x][0]; else if(d<=size[son[x][0]]+1)break; else d-=size[son[x][0]]+1,x=son[x][1]; } return key[x]; } int findkey(int d) { int x,y;spilt(root,d-1,x,y); int ans=size[x];root=merge(x,y); return ans+1; } int findqian(int d) { int x,y;spilt(root,d-1,x,y); int p=x;while(son[p][1])p=son[p][1]; root=merge(x,y); return key[p]; } int findhou(int d) { int x,y;spilt(root,d,x,y); int p=y;while(son[p][0])p=son[p][0]; root=merge(x,y); return key[p]; } int main() { srand(999); scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y;scanf("%d%d",&x,&y); if(x==1)ins(y); else if(x==2)del(y); else if(x==4)printf("%d\n",findpaiming(y)); else if(x==3)printf("%d\n",findkey(y)); else if(x==5)printf("%d\n",findqian(y)); else printf("%d\n",findhou(y)); } return 0; } 

区间操作

什么不是分裂出来以后打标记再合并回去不能解决的事情？

同时在merge和spilt下传标记。

下传标记要看情况直接修改儿子节点，比如区间加，那么我们下传\(x\)标记的时候要直接改变\(x\)左右儿子的key值，否则如果他的某个儿子没有访问到，然后update一下就出锅了，当然也有标记直接修改\(x\)的子树就行了，不用去看儿子的子树，比如翻转标记。

在后面的实现中会有的。

可持久化FHQ！！！

其实所有的可持久化都大同小异，都是建个链，然后寄生一下原来的节点什么的，主席树也是。

例题

例题

题目背景 本题为题目 普通平衡树 的可持久化加强版。 数据已经经过强化 感谢@Kelin 提供的一组hack数据 题目描述 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）： 插入x数 删除x数(若有多个相同的数，因只删除一个，如果没有请忽略该操作) 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 查询排名为x的数 求x的前驱(前驱定义为小于x，且最大的数，如不存在输出-) 求x的后继(后继定义为大于x，且最小的数，如不存在输出) 和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化） 每个版本的编号即为操作的序号（版本0即为初始状态，空树） 输入格式 第一行包含一个正整数N，表示操作的总数。 接下来每行包含三个整数，第 i 行记为 vi, opti, xi vi表示基于的过去版本号（0≤vi<i)，opti表示操作的序号(1≤opt≤6 )，xi表示参与操作的数值 输出格式 每行包含一个正整数，依次为各个3,4,5,6操作所对应的答案 输入输出样例 输入 10 0 1 9 1 1 3 1 1 10 2 4 2 3 3 9 3 1 2 6 4 1 6 2 9 8 6 3 4 5 8 输出 9 1 2 10 3 说明/提示 数据范围： 对于28%的数据满足：1≤n≤10 对于44%的数据满足：1≤n≤2*10^2 对于60%的数据满足：1≤n≤3*10^3 对于84%的数据满足：1≤n≤10^5 对于92%的数据满足：1≤n≤2*10^5 对于100%的数据满足：1≤n≤5⋅10^5，-10^9≤xi≤10^9 经实测，正常常数的可持久化平衡树均可通过，请各位放心 样例说明： 共10次操作，11个版本，各版本的状况依次是： 0.[] 1.[9] 2.[3,9] 3.[9,10] 4。[3,9] 5.[9,10] 6.[2,9,10] 7.[2,9,10] 8.[2,10] 9.[2,10] 10.[3,9] 

学习可持久化

分裂合并

建链

在这里，我们规定如果分裂合并就要新增节点，同时规定3、4、5、6操作不用分裂合并。

那怎么办搞？

分裂我们就对那些被分裂的节点（就是分裂时\(now\)指向的节点）建新点等于原来的点，然后在新点上继续分裂。

那么进行玩这种操作会发现你多建了一条链出来，但是只用了\(logn\)的空间就完成了个操作，不是很棒棒吗？

合并的话。

对那些被\(x,y\)指向的点新建点，你会发现在合并后的树也是新建了一条链出来。

这里图就不画了。反正也不好看

要看可以去参照可持久化主席树。

优化

我们会发现每次来回spilt再merge回去，新建的节点很大概率相同，那么怎么办呢？我们就想到了时间戳。

那么每次我们可以通过判断时间戳来省空间，有时候可以省掉一半的内存，而每个位置只用开一个位置记录下时间戳，使得原本耗内存的可持久化又小了一点，而且代码也不多。

具体实现

//以前的代码，要现在我可以压的更短一点QMQ inline int copynew(int x)//新建节点 { if(a[x].times!=now_times) { a[++cnt]=a[x]; a[cnt].times=now_times;//直接记录时间戳 return cnt; } else return x; } void spilt(int now,int k,int &x,int &y) { if(!now)x=y=0; else { if(a[now].key<=k) { x=copynew(now); spilt(a[x].son[1],k,a[x].son[1],y); update(x); } else { y=copynew(now); spilt(a[y].son[0],k,x,a[y].son[0]); update(y); } } } int merge(int x,int y) { if(!x || !y)return x+y; else { if(a[x].val<=a[y].val) { x=copynew(x);//利用这种方法就可以不重复的建新点了。 a[x].son[1]=merge(a[x].son[1],y); update(x); return x; } else { y=copynew(y); a[y].son[0]=merge(x,a[y].son[0]); update(y); return y; } } } 

查询排名为x的数

因为这里我们要卡常，而分裂合并又会加内存，那么我们就愉快的直接暴力跳吧。

虽然这样子可能会慢，但是既然出题人卡得掉暴力跳的做法（没有用merge和spilt调整树的形态），那么调整的做法也可以卡内存，要这么想你就不做了吧，所以这里采用的是splay的方法，而且分裂合并常数巨大。

//这里可以打成非递归版的，会快，不知道我当时就为什么这么ZZ，打递归版的。 int findpai(int now,int k) { if(now==0)return 1; else if(a[now].key<k)return a[a[now].son[0]].size+1+findpai(a[now].son[1],k); else return findpai(a[now].son[0],k); } 

前驱后继

这里讲了会教新方法的，就教吧。

方法很简单，我们只需要从根节点开始，像启发式搜索那样，暴力跳，同时用ans记录一下就行了。

//你想不到会如此暴力吧。 int houji(int x,int k) { int ans=; while(x!=0) { if(a[x].key<=k)x=a[x].son[1]; else ans=a[x].key,x=a[x].son[0]; } return ans; } int qianqu(int x,int k) { int ans=-; while(x!=0) { if(a[x].key<k)ans=a[x].key,x=a[x].son[1]; else x=a[x].son[0]; } return ans; } 

代码

别忘了3、4、5、6不要建新点。

#include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int N=; struct node { int son[2]; int size,val,key,times; }a[N*30];int root[N],cnt,n,now_times; inline void update(int x){a[x].size=a[a[x].son[0]].size+a[a[x].son[1]].size+1;} inline int copynew(int x) { if(a[x].times!=now_times) { a[++cnt]=a[x]; a[cnt].times=now_times; return cnt; } else return x; } int insert_new(int x) { cnt++; a[cnt].size=1;a[cnt].val=rand();a[cnt].key=x;a[cnt].times=now_times; return cnt; } void spilt(int now,int k,int &x,int &y) { if(!now)x=y=0; else { if(a[now].key<=k) { x=copynew(now); spilt(a[x].son[1],k,a[x].son[1],y); update(x); } else { y=copynew(now); spilt(a[y].son[0],k,x,a[y].son[0]); update(y); } } } int merge(int x,int y) { if(!x || !y)return x+y; else { if(a[x].val<=a[y].val) { x=copynew(x); a[x].son[1]=merge(a[x].son[1],y); update(x); return x; } else { y=copynew(y); a[y].son[0]=merge(x,a[y].son[0]); update(y); return y; } } } void insert(int now,int k) { int x,y;x=y=0; spilt(root[now],k,x,y); root[now]=merge(merge(x,insert_new(k)),y); } void Delete(int now,int k) { int x,y,z;x=y=z=0; spilt(root[now],k,x,z);spilt(x,k-1,x,y); y=merge(a[y].son[0],a[y].son[1]); root[now]=merge(merge(x,y),z); } int findKth(int x,int k) { while(1) { if(a[a[x].son[0]].size+1==k)return a[x].key; else if(a[a[x].son[0]].size<k)k-=a[a[x].son[0]].size+1,x=a[x].son[1]; else x=a[x].son[0]; } } //这里可以打成非递归版的，会快，不知道我当时就为什么这么ZZ，打递归版的。 int findpai(int now,int k) { if(now==0)return 1; else if(a[now].key<k)return a[a[now].son[0]].size+1+findpai(a[now].son[1],k); else return findpai(a[now].son[0],k); } int houji(int x,int k) { int ans=; while(x!=0) { if(a[x].key<=k)x=a[x].son[1]; else ans=a[x].key,x=a[x].son[0]; } return ans; } int qianqu(int x,int k) { int ans=-; while(x!=0) { if(a[x].key<k)ans=a[x].key,x=a[x].son[1]; else x=a[x].son[0]; } return ans; } int main() { srand(999); scanf("%d",&n); for(now_times=1;now_times<=n;now_times++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); root[now_times]=root[x];//3、4、5、6操作不会merge和spilt。 if(y==1)insert(now_times,z); else if(y==2)Delete(now_times,z); else if(y==3)printf("%d\n",findpai(root[now_times],z)); else if(y==4)printf("%d\n",findKth(root[now_times],z)); else if(y==5)printf("%d\n",qianqu(root[now_times],z)); else if(y==6)printf("%d\n",houji(root[now_times],z)); } return 0; } 

你只要会压行的话代码会更短的QMQ。

残忍树套树

【题意】 写一种数据结构，来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数) 【输入格式】 第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示有序序列 下面有m行，opt表示操作标号 若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-) 若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继(后继定义为严格大于x，且最小的数，若不存在输出) 【输出格式】 对于操作1,2,4,5各输出一行，表示查询结果 【样例输入】 9 6 4 2 2 1 9 4 0 1 1 2 1 4 3 3 4 10 2 1 4 3 1 2 5 9 4 3 9 5 5 2 8 5 【样例输出】 2 4 3 4 9 【来源】Tyvj 1730 【数据范围】n,m<=50000 ，序列中的数始终为不大于10^8的非负整数。 

手段残忍，树套树还没有可持久化呢。

首先，我们考虑一下外面套个动态开点权值线段树，然后里面套个FHQ记录在这个值域的有多少个数字，代码再长也长不到哪里去，但是要怎么做？

考虑第1问，我们只需要在树上找k的位置，跳右儿子并且问问左儿子的FHQ在这个区间的有多少个数，注意，如果没有这个数字，那么我们就要当有这个数字，然后计算他的排名。

第2问，也是问左儿子，然后考虑跳左跳右。

修改就暴力删数，然后再插数。

前驱后继呢？

前驱的话，我们只需要查询\(k\)的排名\(d\)，然后找排名为\(d-1\)的数字。

后继的话，查询\(k+1\)的排名\(d\)，然后查排名为\(d\)的数字。

时间复杂度是：\(O(mlog\)值域\(logn)\)，常数极大，可以打离散化优化。

//目前是我们班上最短的代码，但是因为常数问题。。。 #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #define N using namespace std; inline void gets(int &x) { char c=getchar();x=0; while('0'>c || c>'9')c=getchar(); while('0'<=c && c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } int n,m; int ke[N],size[N],son[N][2],val[N],len; inline void update(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;} void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { if(ke[now]<=k)x=now,spilt(son[x][1],k,son[x][1],y),update(x); else y=now,spilt(son[y][0],k,x,son[y][0]),update(y); } } int merge(int a,int b) { if(!a || !b)return a+b; else { if(val[a]<=val[b])son[a][1]=merge(son[a][1],b),update(a); else son[b][0]=merge(a,son[b][0]),update(b),a^=b^=a^=b; return a; } } inline void ins(int &now,int d) { len++;ke[len]=d;size[len]=1;val[len]=rand(); int x,y;spilt(now,d,x,y); now=merge(merge(x,len),y); } inline void del(int &now,int d) { int x,y,z;spilt(now,d-1,x,y);spilt(y,d,y,z); now=merge(x,z); } inline int findip(int now,int d) { int x=now,ans=0; while(x) { if(ke[x]<=d)ans+=size[son[x][0]]+1,x=son[x][1]; else x=son[x][0]; } return ans; } struct node { int lc,rc,rt,c; }tr[N];int trlen,root; void link(int &now,int l,int r,int key,int id) { if(!now)now=++trlen; tr[now].c++; ins(tr[now].rt,id); if(l==r)return ; int mid=(l+r)/2; if(key<=mid)link(tr[now].lc,l,mid,key,id); else link(tr[now].rc,mid+1,r,key,id); } int findpaiming(int now,int l,int r,int id,int ll,int rr) { if(!tr[now].c)return 1; if(l==r)return 1; int ans=0; int mid=(l+r)/2; if(mid<id) { ans=findip(tr[tr[now].lc].rt,rr)-findip(tr[tr[now].lc].rt,ll-1); return ans+findpaiming(tr[now].rc,mid+1,r,id,ll,rr); } else return findpaiming(tr[now].lc,l,mid,id,ll,rr); } int findkey(int now,int l,int r,int d,int ll,int rr) { if(l==r)return l; int ans=findip(tr[tr[now].lc].rt,rr)-findip(tr[tr[now].lc].rt,ll-1); if(d<=ans)return findkey(tr[now].lc,l,(l+r)/2,d,ll,rr); else return findkey(tr[now].rc,(l+r)/2+1,r,d-ans,ll,rr); } void ddel(int now,int l,int r,int c,int d) { tr[now].c--; del(tr[now].rt,d); if(l!=r) { int mid=(l+r)/2; if(c<=mid)ddel(tr[now].lc,l,mid,c,d); else ddel(tr[now].rc,mid+1,r,c,d); } } int a[51000]; int main() { srand(999); gets(n);gets(m); for(int i=1;i<=n;i++) { gets(a[i]); link(root,0,1e8,a[i],i); } for(int i=1;i<=m;i++) { int x,y,z,k;scanf("%d",&x); if(x==1) { scanf("%d%d%d",&y,&z,&k); printf("%d\n",findpaiming(root,0,1e8,k,y,z)); } else if(x==2) { scanf("%d%d%d",&y,&z,&k); printf("%d\n",findkey(root,0,1e8,k,y,z)); } else if(x==3) { scanf("%d%d",&y,&z);k=a[y]; ddel(root,0,1e8,k,y);link(root,0,1e8,z,y); a[y]=z; } else if(x==4) { scanf("%d%d%d",&y,&z,&k); int ans=findpaiming(root,0,1e8,k,y,z); if(ans==1)printf("-\n"); else printf("%d\n",findkey(root,0,1e8,ans-1,y,z)); } else if(x==5) { scanf("%d%d%d",&y,&z,&k);int ans=findpaiming(root,0,1e8,k+1,y,z); if(ans==z-y+2)printf("\n"); else printf("%d\n",findkey(root,0,1e8,ans,y,z)); } } return 0; } 

如此良心毒瘤的代码

练习

1

时间限制: 1 Sec 内存限制: 128 MB 给出n个数，每个数的最小波动值 = min{ | a[i]-a[j] | , 1<=j<i }，求n个数的最小波动值之和。 【输入格式】 正整数n(n<=10^5)，接下来的n个整数ai(ai<=10^9),a[1]保证为正数 【输出格式】 一个正整数，即n个数的最小波动值之和，小于2^31 【样例输入】 6 5 1 2 5 4 6 【样例输出】 12 【数据提示】 结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12 

一道查前驱后继的SB题

这里用的是Splay。

#include<cstdio> #include<cstring> #define N using namespace std; int root; struct node { int d,n,c,f,son[2]; }tr[N];int len; void update(int x){tr[x].c=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+tr[x].n;} void add(int d,int f) { len++; tr[len].c=tr[len].n=1;tr[len].f=f;tr[len].d=d; tr[f].son[d>tr[f].d]=len; } int chk(int x){return tr[tr[x].f].son[1]==x;} void rotate(int x) { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1,son=tr[x].son[w]; int r,R; r=son;R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; update(f);update(x); } void splay(int x,int y) { while(tr[x].f!=y) { int f=tr[x].f,ff=tr[f].f; if(ff==y)rotate(x); else rotate(chk(x)^chk(f)?x:f),rotate(x); } if(!y)root=x; } int findip(int d) { int x=root; while(tr[x].d!=d) { if(!tr[x].son[d>tr[x].d])break; x=tr[x].son[d>tr[x].d]; } return x; } void ins(int d) { if(!root){add(d,0);root=len;return ;} int x=findip(d); if(tr[x].d==d)tr[x].n++,tr[x].c++,splay(x,0); else add(d,x),update(x),splay(len,0); } void del(int d) { int x=findip(d);splay(x,0); if(tr[x].n!=1)tr[x].n--; else if(!tr[x].son[0] && !tr[x].son[1])root=0; else if(!tr[x].son[0] && tr[x].son[1])root=tr[x].son[1],tr[root].f=0; else if(!tr[x].son[1] && tr[x].son[0])root=tr[x].son[0],tr[root].f=0; else { int p=tr[x].son[0];while(tr[p].son[1])p=tr[p].son[1]; splay(p,x); tr[p].f=0;tr[p].son[1]=tr[x].son[1];update(p); tr[tr[x].son[1]].f=p; root=p; } } int qian(int d) { int x=findip(d);splay(x,0); if(tr[x].d>d && tr[x].son[0]) { x=tr[x].son[0];while(tr[x].son[1])x=tr[x].son[1]; } if(tr[x].d>d)return -; return tr[x].d; } int prep(int d) { int x=findip(d);splay(x,0); if(tr[x].d<d && tr[x].son[1]) { x=tr[x].son[1];while(tr[x].son[0])x=tr[x].son[0]; } if(tr[x].d<d)return ; return tr[x].d; } int n; inline int mymin(int x,int y){return x<y?x:y;} int main() { int ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int d;scanf("%d",&d); if(i==1)ans+=d; else ans+=mymin(d-qian(d),prep(d)-d);//快乐查前驱后继 ins(d); } printf("%d\n",ans); return 0; } 

2

题面

时间限制: 1 Sec 内存限制: 128 MB

有一个数列，在初始时，数列为空。

名称	格式	作用
I命令	I_k	添加一个点，初始值为k。如果该点的值低于min，它将马上删除（不计入删除 的数目）；
A命令	A_k	给现存每个点加上k；
S命令	S_k	把每个点减少k（减少之后，如果有点的值低于min，则这些点马上删除；
F命令	F_k	查询第k大的点的值；

_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。

【输入格式】
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。
【输出格式】
输出文件的行数为F命令的条数加一。
对于每条F命令，输出一行，仅包含一个整数，为当前第k大的值，如果k大于目前点的数目，则输出-1。
输出最后一行包含一个整数，为总共删除的点的总数。
【样例输入】
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
【样例输出】
10
20
-1
2
【数据提示】
I命令的条数不超过
A命令和S命令的总条数不超过100
F命令的条数不超过
每次调整的调整量不超过1000
新添加的点的值不超过

题解

这道题你绝对想不到。

就是一个很裸的暴力，每次暴力加减。

当时我还想了好久，被同学抢了QAQ。

采用FHQ Treap。

#include<cstdio> #include<cstring> #include<cstdlib> #define N using namespace std; int key[N],size[N],val[N],son[N][2],root,len; int n,m; void update(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;} void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { if(key[now]<=k)x=now,spilt(son[x][1],k,son[x][1],y),update(x); else y=now,spilt(son[y][0],k,x,son[y][0]),update(y); } } int merge(int x,int y) { if(!x || !y)return x+y; if(val[x]<=val[y])son[x][1]=merge(son[x][1],y),update(x); else son[y][0]=merge(x,son[y][0]),update(y),x^=y^=x^=y; return x; } void ins(int d) { len++;key[len]=d;val[len]=rand();size[len]=1; int x,y;spilt(root,d,x,y); root=merge(merge(x,len),y); } void del(int d) { int x,y,z;spilt(root,d-1,x,y);spilt(y,d,y,z); root=merge(merge(x,merge(son[y][0],son[y][1])),z); } int findkey(int d) { int x=root; while(1) { if(d<=size[son[x][0]])x=son[x][0]; else if(d<=size[son[x][0]]+1)break; else d-=size[son[x][0]]+1,x=son[x][1]; } return key[x]; } int ans=0,list[N],tail; void adl(int x,int d) { if(x) { key[x]+=d; adl(son[x][0],d); adl(son[x][1],d); if(key[x]<m)list[++tail]=x; } } int main() { // freopen("testdata.in","r",stdin); // freopen("hehe.out","w",stdout); srand(999); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { char st[10];int x;scanf("%s",st+1);scanf("%d",&x); if(st[1]=='I') { if(x>=m)ins(x); } else if(st[1]=='A')adl(root,x); else if(st[1]=='S') { tail=0;adl(root,-x);//暴力DFS加减 ans+=tail; while(tail>0) { del(key[list[tail]]);//删点 tail--; } } else { if(x<=len-ans)printf("%d\n",findkey((len-ans)-x+1)); else printf("-1\n"); } } printf("%d\n",ans); return 0; } 

3

【题意】 时间限制: 1 Sec 内存限制: 128 MB 一个房子里，陆续来了一些人和数字。一开始房子什么都没有。 每个人都希望得到和自己期望的值最接近的数字。 1、当房子有数字时，假若来一个人，这个人期望的值为a，那么它将会得到现存的一个最接近a的数字。如果有两个数字距离a相等，那么小的数字会被人领走（这时这个人和这个数字离开房子）。 2、当房子有人时，假若来一个数字a，那么它将会被期望值最接近a的人领走。如果有两个人期望值距离a相等，那么期望值小的人会得手。（这时这个人和这个数字离开房子）。 如果数字来了，房子没人，那么数字就呆在房子里面等待人。 如果人来了，房子没数字，那么人就呆在房子里面等待数字。 一个期望值为a的人，领走一个值为b的数字，这个人的不满意程度为abs(a-b)。 计算所有得到数字的人的不满意程度的总和。 提示：同一时间，房子里面要不都是数字，要不都是人。为什么？ 【输入格式】 第一行为一个正整数n，n<=80000，表示陆续有n个数字或人将来到房子。 接下来的n行，按到来时间的先后顺序描述了下来陆续来到房子的数字和人的情况。 每行有两个正整数a, b，其中a=0表示数字，a=1表示人，b表示数字的值或是人的期望值。这些数字和人的个数不会超过10000个。 【输出格式】 仅有一个正整数，表示所有得到数字的人的不满意程度的总和mod 以后的结果。 【样例输入】 5 0 2 0 4 1 3 1 2 1 5 【样例输出】 3 【数据提示】 (abs(3-2) + abs(2-4)=3，最后一个人没有得到) 

又是前驱后继。。。

看下主函数就可以了。

Splay

#include<cstdio> #include<cstring> #define N using namespace std; int root; struct node { int c,d,n,f,son[2]; }tr[N];int len; void update(int x){tr[x].c=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+tr[x].n;} void add(int d,int f) { len++; tr[len].n=tr[len].c=1;tr[len].d=d;tr[len].f=f; tr[f].son[d>tr[f].d]=len; } int chk(int x){return tr[tr[x].f].son[1]==x;} void rotate(int x) { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1,son=tr[x].son[w]; int r,R; r=son;R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; update(f);update(x); } void splay(int x,int y) { while(tr[x].f!=y) { int f=tr[x].f,ff=tr[f].f; if(ff==y)rotate(x); else rotate(chk(x)^chk(f)?x:f),rotate(x); } if(!y)root=x; } int findip(int d) { int x=root; while(tr[x].d!=d) { if(!tr[x].son[d>tr[x].d])break; x=tr[x].son[d>tr[x].d]; } return x; } void ins(int d) { if(!root){add(d,0),root=len;return ;} int x=findip(d); if(tr[x].d==d)tr[x].n++,tr[x].c++,splay(x,0); else add(d,x),update(x),splay(len,0); } void del(int d) { int x=findip(d);splay(x,0); if(tr[x].n!=1)tr[x].n--; else if(!tr[x].son[0] && !tr[x].son[1])root=0; else if(!tr[x].son[0] && tr[x].son[1])root=tr[x].son[1],tr[root].f=0; else if(tr[x].son[0] && !tr[x].son[1])root=tr[x].son[0],tr[root].f=0; else { int p=tr[x].son[0];while(tr[p].son[1])p=tr[p].son[1]; splay(p,x); tr[p].f=0;tr[p].son[1]=tr[x].son[1];update(p); tr[tr[x].son[1]].f=p; splay(x,0); } } int findq(int d) { int x=findip(d);splay(x,0); if(tr[x].d>d && tr[x].son[0]) { x=tr[x].son[0];while(tr[x].son[1])x=tr[x].son[1]; } if(tr[x].d>d)return -; return x; } int findh(int d) { int x=findip(d);splay(x,0); if(tr[x].d<d && tr[x].son[1]) { x=tr[x].son[1];while(tr[x].son[0])x=tr[x].son[0]; } if(tr[x].d<d)return ; return x; } int n,cnt,t,ans; inline int zabs(int x){return x<0?-x:x;} int main() { // freopen("1.in","r",stdin); scanf("%d",&n);t=-1; for(int i=1;i<=n;i++) { int x,y;scanf("%d%d",&x,&y); if(t==-1) { t=x,cnt=1,ins(y); } else if(t==x)cnt++,ins(y); else { int tx,ty; tx=findq(y),ty=findh(y); if(tx==- || (ty!= && y-tr[tx].d>tr[ty].d-y))tx^=ty^=tx^=ty; del(tr[tx].d);ans+=zabs(y-tr[tx].d);ans%=; if(cnt==1)t=-1,cnt=0; else cnt--; } } printf("%d\n",ans); return 0; } 

4

时间限制: 1 Sec 内存限制: 128 MB 【题意】 写一种数据结构，来维护一个有序数列，其中需要提供以下操作： 翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 【输入格式】 第一行为n,m （n,m < =）。 n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)；m表示翻转操作次数，接下来m行每行两个数[l,r] 数据保证 （1 < =l < = r < =n） 【输出格式】 输出一行n个数字，表示原始序列经过m次变换后的结果 【样例输入】 5 3 1 3 1 3 1 4 【样例输出】 4 3 2 1 5 

FHQ万岁，直接给区间打标记。

//快乐FHQ，其实可以给翻转单独打个函数，就不用打这么多行了。 #include<cstdio> #include<cstring> #include<cstdlib> #define N using namespace std; int val[N],size[N],son[N][2],len,n,m,root; bool lazy[N]; void update(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;} void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { if(lazy[now]==true)son[now][0]^=son[now][1]^=son[now][0]^=son[now][1],lazy[son[now][0]]^=1,lazy[son[now][1]]^=1,lazy[now]=false; if(size[son[now][0]]+1<=k)x=now,spilt(son[x][1],k-size[son[now][0]]-1,son[x][1],y),update(x); else y=now,spilt(son[y][0],k,x,son[y][0]),update(y); } } int merge(int x,int y) { if(!x || !y)return x+y; else { if(lazy[x]==true)son[x][0]^=son[x][1]^=son[x][0]^=son[x][1],lazy[son[x][0]]^=1,lazy[son[x][1]]^=1,lazy[x]=false; if(lazy[y]==true)son[y][0]^=son[y][1]^=son[y][0]^=son[y][1],lazy[son[y][0]]^=1,lazy[son[y][1]]^=1,lazy[y]=false; if(val[x]<=val[y])son[x][1]=merge(son[x][1],y),update(x); else son[y][0]=merge(x,son[y][0]),update(y),x^=y^=x^=y; return x; } } void ins(int d) { len++; val[len]=rand();size[len]=1;root=merge(root,len); } int findpaiming(int d) { int x=root; while(1) { if(lazy[x]==true)son[x][0]^=son[x][1]^=son[x][0]^=son[x][1],lazy[son[x][0]]^=1,lazy[son[x][1]]^=1,lazy[x]=false; if(d<=size[son[x][0]])x=son[x][0]; else if(d<=size[son[x][0]]+1)break; else d-=size[son[x][0]]+1,x=son[x][1]; } return x; } void dao(int l,int r) { int x,y,z;spilt(root,l-1,x,y); spilt(y,r-l+1,y,z); lazy[y]^=1; root=merge(merge(x,y),z); } int main() { srand(999); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)ins(i); for(int i=1;i<=m;i++) { int l,r;scanf("%d%d",&l,&r); dao(l,r); } for(int i=1;i<n;i++)printf("%d ",findpaiming(i)); printf("%d\n",findpaiming(n)); return 0; } 

5（一道贼恶心的区间题）

题面

这题有链接

时间限制: 1 Sec 内存限制: 128 MB

请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）

[外链图片转存失败(img-EwBwvSA0-26)(https://i.loli.net/2019/08/15/NVZEpSkMfdB9vun.png)]

【输入格式】

输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格

【输出格式】

对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占一行。

【输入输出样例】

输入

9 8 2 -6 3 5 1 -5 -3 6 3 GET-SUM 5 4 MAX-SUM INSERT 8 3 -5 7 2 DELETE 12 1 MAKE-SAME 3 3 2 REVERSE 3 6 GET-SUM 5 4 MAX-SUM 

输出

-1 10 1 10 

说明/提示

你可以认为在任何时刻，数列中至少有 1 个数。

输入数据一定是正确的，即指定位置的数在数列中一定存在。

50%的数据中，任何时刻数列中最多含有 30 000 个数；

100%的数据中，任何时刻数列中最多含有 500 000 个数。

100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。

100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。

题解

就是区间操作吗，最后一问有点难度，需要每个点维护三个值，一个是子树内从左到右的和最大子列，一个是从右到左，一个代表的是子树内和最大的子列。

//坑点：最后一个操作一定要选数字 #include<cstdio> #include<cstring> #include<cstdlib> #pragma GCC optimize("Ofast") #define N using namespace std; inline void gets(int &x) { char c=getchar();x=0;int f=1; while(c>'9' || c<'0')c=='-'?f=-1:0,c=getchar(); while(c<='9' && c>='0')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=f; } struct neicun { int sta[N],len; }zjj; inline void save(int x){zjj.sta[++zjj.len]=x;} inline int get(){return zjj.sta[zjj.len--];} int key[N],val[N],size[N],son[N][2],root; int la1[N]/*反转*/,la2[N]/*等于的标记*/; int k2[N]/*从左往右最大值*/,k3[N]/*从右到左最大值*/,k4[N]/*最大的答案*/,sum[N]; bool qwq[N]; inline int mi(int x,int y){return x<y?x:y;} inline int ma(int x,int y){return x>y?x:y;} inline void update(int x) { size[x]=size[son[x][0]]+size[son[x][1]]+1; sum[x]=sum[son[x][0]]+sum[son[x][1]]+key[x]; k2[x]=ma(k2[son[x][0]],sum[son[x][0]]+key[x]+k2[son[x][1]]); k3[x]=ma(k3[son[x][1]],sum[son[x][1]]+key[x]+k3[son[x][0]]); k4[x]=ma(ma(k4[son[x][0]],k4[son[x][1]]),k3[son[x][0]]+key[x]+k2[son[x][1]]);//统计答案 } inline void downdate(bool bk,int x) { if(qwq[x]) { key[x]=la2[x];key[x]>0?(k2[x]=k3[x]=k4[x]=key[x]*size[x]):(k2[x]=k3[x]=0,k4[x]=key[x]); sum[x]=key[x]*size[x]; la2[son[x][0]]=la2[son[x][1]]=la2[x];la2[x]=0; qwq[son[x][0]]=qwq[son[x][1]]=1;qwq[x]=0; } if(la1[x]==1) { la1[x]=0;la1[son[x][0]]^=1;la1[son[x][1]]^=1; son[x][0]^=son[x][1]^=son[x][0]^=son[x][1]; k2[x]^=k3[x]^=k2[x]^=k3[x]; } if(bk==true)//这里主要是为了把儿子的'='的标记触发，防止一个update出锅，有更好的写法，本蒟蒻SB的这么写了 { if(son[x][0])downdate(0,son[x][0]); if(son[x][1])downdate(0,son[x][1]); } } void spilt(int now,int k,int &x,int &y) { if(!now)x=0,y=0; else { downdate(1,now); if(size[son[now][0]]+1<=k)x=now,spilt(son[x][1],k-size[son[now][0]]-1,son[x][1],y); else y=now,spilt(son[y][0],k,x,son[y][0]); update(now); } } int merge(int x,int y) { if(!x || !y)return x+y; else { if(val[x]<=val[y])downdate(1,x),son[x][1]=merge(son[x][1],y); else downdate(1,y),son[y][0]=merge(x,son[y][0]),x^=y^=x^=y; update(x); return x; } } inline int ins(int c) { int now=get(); key[now]=c;size[now]=1;c>0?(k2[now]=k3[now]=c):(k2[now]=k3[now]=0);sum[now]=c;k4[now]=c;val[now]=rand(); la1[now]=la2[now]=0;qwq[now]=0; return now; } void cun(int x) { if(!x)return ; save(x); cun(son[x][0]);cun(son[x][1]); } inline void del(int l,int r) { int x,y,z; spilt(root,l-1,x,y); spilt(y,(r-l+1),y,z); root=merge(x,z); cun(y); } inline void change(int l,int r,int d) { int x,y,z;spilt(root,l-1,x,y);spilt(y,(r-l+1),y,z); la2[y]=d;qwq[y]=1;downdate(0,y); root=merge(merge(x,y),z); } inline void fanzhuan(int l,int r) { int x,y,z;spilt(root,l-1,x,y);spilt(y,(r-l+1),y,z); la1[y]^=1;downdate(0,y); root=merge(merge(x,y),z); } inline void getsum(int l,int r) { int x,y,z;spilt(root,l-1,x,y);spilt(y,(r-l+1),y,z); printf("%d\n",sum[y]); root=merge(merge(x,y),z); } int a[N]; int build(int l,int r)//手动建树 { if(l>r)return 0; int mid=(l+r)>>1,now=ins(a[mid]); son[now][0]=build(l,mid-1); son[now][1]=build(mid+1,r); update(now); return now; } int n,m; char st[20]; int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); k4[0]=-; zjj.len=;for(int i=1;i<=;i++)zjj.sta[i]=i; gets(n);gets(m); for(register int i=1;i<=n;i++)gets(a[i]); root=build(1,n); for(register int i=1;i<=m;i++) { scanf("%s",st+1); if(st[1]=='I') { int xy,cnt,rt=0;gets(xy);gets(cnt); for(register int j=1;j<=cnt;j++)gets(a[j]); rt=build(1,cnt); int x1,x2;spilt(root,xy,x1,x2); root=merge(merge(x1,rt),x2); } else if(st[1]=='D') { int xy,cnt;gets(xy);gets(cnt); del(xy,xy+cnt-1); } else if(st[1]=='M' && st[3]=='K') { int l,r,d;gets(l),gets(r),gets(d);r+=l-1; change(l,r,d); } else if(st[1]=='R') { int l,r;gets(l),gets(r);r+=l-1; fanzhuan(l,r); } else if(st[1]=='G') { int l,r;gets(l),gets(r);r+=l-1; getsum(l,r); } else printf("%d\n",k4[root]); } return 0; } 

6

题面

原题链接

时间限制 2.00s ~ 2.50s

内存限制 158.20MB

【题目描述】

Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。

经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。

在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：

• INSERT i k：在原数列的第i个元素后面添加一个新元素k；如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
• MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值
• MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）

例如一开始的序列为5,3,1。

执行操作INSERT 2 9将得到：5,3,9,1，此时MIN_GAP为2，MIN_SORT_GAP为2。

再执行操作INSERT 2 6将得到：5,3,9,6,1

注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。

于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

【输入格式】

第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。

第二行为N个整数，为初始序列。

接下来的M行每行一个操作，即INSERT i k，MIN_GAP，MIN_SORT_GAP 中的一种（无多余空格或者空行）。

【输出格式】

对于每一个MIN_GAP和MIN_SORT_GAP命令，输出一行答案即可。

【输入输出样例】

输入

输出

【说明/提示】

对于30%的数据，N≤1000 ,M≤5000
对于100%的数据，N,M≤N
对于所有的数据，序列内的整数不超过\(5*10^{8}\)。

题解

首先，第三个询问的话不管插多少个点，答案都是只减不加，所以我们可以直接用个变量统计，但是第二个问呢？

我们可以打棵平衡树，在插入数的时候删掉原来的，再插进去新的答案，NO，NO，NO，听说过一种蛇皮的可以支持删除现有数字的堆，叫二叉堆吗？其实就是两个堆，一个堆存删除掉但还没POP掉的点以及没被删的点，第二个堆存目前还没POP掉的已经删掉的点，如果两个堆堆顶一致，同时POP，不就好起来了吗？

这里用的是Splay。

还有个要注意的地方是查前驱后继的地方有点狗，全部塞到了ins里面了。

#include<cstdio> #include<cstring> #define N #define NN using namespace std; inline void getw(int &x) { char c=getchar();x=0;int f=1; while(c<'0' || c>'9')c=='-'?f=-1:0,c=getchar(); while('0'<=c && c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); c++;x=x*f; } int root; class dui//还是class好用 { public://公共 int a[N],len; void heap(int x) { int f=x>>1; while(f) { if(a[f]<=a[x])break; else a[x]^=a[f]^=a[x]^=a[f],x=f,f=(x>>1); } } void push(int d) { a[++len]=d; heap(len); } void pop() { a[1]=a[len--]; int x=1,y=x<<1; while(y<=len) { (a[y]>a[y^1] && y!=len)?y++:0; if(a[y]>=a[x])break; else a[x]^=a[y]^=a[x]^=a[y],x=y,y=(x<<1); } } bool empty(){return len==0;} int top(){return a[1];} }t1,t2; struct node { int d,f,son[2]; }tr[N];int len; inline int chk(int x){return tr[tr[x].f].son[1]==x;} void add(int d,int f) { len++; tr[len].f=f;tr[len].d=d; tr[f].son[d>tr[f].d]=len; } void rotate(int x) { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1,son=tr[x].son[w]; int r,R; r=son,R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; } void splay(int x,int y) { while(tr[x].f!=y) { int f=tr[x].f,ff=tr[f].f; if(ff==y)rotate(x); else rotate(chk(x)^chk(f)?x:f),rotate(x); } if(!y)root=x; } inline int findip(int d) { int x=root; while(tr[x].d!=d) { if(!tr[x].son[d>tr[x].d])break; x=tr[x].son[d>tr[x].d]; } return x; } int ans=; inline int mymin(int x,int y){return x<y?x:y;} inline int zabs(int x){return x<0?-x:x;} inline void ins(int d) { if(!root){add(d,0);root=len;return ;} int x=findip(d); if(tr[x].d==d)ans=0,splay(x,0); else { add(d,x),splay(len,0); ans=mymin(ans,zabs(d-tr[x].d)); if(tr[x].d<d) { x=tr[len].son[1];while(tr[x].son[0])x=tr[x].son[0]; } else { x=tr[len].son[0];while(tr[x].son[1])x=tr[x].son[1]; } ans=mymin(zabs(d-tr[x].d),ans); } } int a[NN],b[NN]; int n,m; int main() { // freopen("form6.in","r",stdin); // freopen("form32.txt","w",stdout); tr[0].d=; getw(n);getw(m); for(int i=1;i<=n;i++) { getw(a[i]); if(i!=1)t1.push(zabs(a[i]-a[i-1])); ins(a[i]);b[i]=a[i]; } for(int i=1;i<=m;i++) { char st[30];scanf("%s",st+1); if(st[1]=='I') { int x,y;getw(x);/*scanf("%d",&y);*/ getw(y); t2.push(zabs(a[x+1]-b[x]));t1.push(zabs(b[x]-y));t1.push(zabs(a[x+1]-y)); b[x]=y;ins(y); } else if(st[5]=='S')printf("%d\n",ans); else { while(t2.empty()==false && t1.top()==t2.top())t1.pop(),t2.pop(); printf("%d\n",t1.top()); } } return 0; } ],x=f,f=(x>>1); } } void push(int d) { a[++len]=d; heap(len); } void pop() { a[1]=a[len--]; int x=1,y=x<<1; while(y<=len) { (a[y]>a[y^1] && y!=len)?y++:0; if(a[y]>=a[x])break; else a[x]^=a[y]^=a[x]^=a[y],x=y,y=(x<<1); } } bool empty(){return len==0;} int top(){return a[1];} }t1,t2; struct node { int d,f,son[2]; }tr[N];int len; inline int chk(int x){return tr[tr[x].f].son[1]==x;} void add(int d,int f) { len++; tr[len].f=f;tr[len].d=d; tr[f].son[d>tr[f].d]=len; } void rotate(int x) { int f=tr[x].f,ff=tr[f].f,w=chk(x)^1,son=tr[x].son[w]; int r,R; r=son,R=f;tr[r].f=R;tr[R].son[w^1]=r; r=x;R=ff;tr[r].f=R;tr[R].son[chk(f)]=r; r=f;R=x;tr[r].f=R;tr[R].son[w]=r; } void splay(int x,int y) { while(tr[x].f!=y) { int f=tr[x].f,ff=tr[f].f; if(ff==y)rotate(x); else rotate(chk(x)^chk(f)?x:f),rotate(x); } if(!y)root=x; } inline int findip(int d) { int x=root; while(tr[x].d!=d) { if(!tr[x].son[d>tr[x].d])break; x=tr[x].son[d>tr[x].d]; } return x; } int ans=; inline int mymin(int x,int y){return x<y?x:y;} inline int zabs(int x){return x<0?-x:x;} inline void ins(int d) { if(!root){add(d,0);root=len;return ;} int x=findip(d); if(tr[x].d==d)ans=0,splay(x,0); else { add(d,x),splay(len,0); ans=mymin(ans,zabs(d-tr[x].d)); if(tr[x].d<d) { x=tr[len].son[1];while(tr[x].son[0])x=tr[x].son[0]; } else { x=tr[len].son[0];while(tr[x].son[1])x=tr[x].son[1]; } ans=mymin(zabs(d-tr[x].d),ans); } } int a[NN],b[NN]; int n,m; int main() { // freopen("form6.in","r",stdin); // freopen("form32.txt","w",stdout); tr[0].d=; getw(n);getw(m); for(int i=1;i<=n;i++) { getw(a[i]); if(i!=1)t1.push(zabs(a[i]-a[i-1])); ins(a[i]);b[i]=a[i]; } for(int i=1;i<=m;i++) { char st[30];scanf("%s",st+1); if(st[1]=='I') { int x,y;getw(x);/*scanf("%d",&y);*/ getw(y); t2.push(zabs(a[x+1]-b[x]));t1.push(zabs(b[x]-y));t1.push(zabs(a[x+1]-y)); b[x]=y;ins(y); } else if(st[5]=='S')printf("%d\n",ans); else { while(t2.empty()==false && t1.top()==t2.top())t1.pop(),t2.pop(); printf("%d\n",t1.top()); } } return 0; }