fhq——treap

前言

这是分裂平衡树，是范浩强神牛发明的，我觉得是一个好写，好调的平衡树，所以先%fhq 之后开始

原理

其实就是把普通的treap的旋转换成了分裂，于是他就可以实现所有平衡树的所有操作

结构体里的东东

1.val值
2.key 索引
3.l,r左右孩子编号
4.size大小

split

这是很重要的操作之一，这个是按照val把这棵树分成两个，一个全都小于等于val，一个全都大于val，代码如下

inline void split(int now,int val,int &x,int &y){
    //从哪个节点开始，值，分裂出来两棵树树 if(!now) x = y = 0;//如果不存在那么分裂出来的左右子树也不存在 else{
    if(fhq[now].val <= val){
    //这里面就是满足二叉搜索树的性质，左节点一定小于等于根节点 x = now;//这里左边的确定了但是右边不，所以递归找右边 split(fhq[now].r,val,fhq[now].r,y);//这里分裂出来的左边的一定全是小于等于Val的 ，所以这里就不会更新y 也可以理解为x已经确定，但是y不所以要把y传下去修改}else{
    y = now;split(fhq[now].l,val,x,fhq[now].l);}update(now);//分裂完之后去更新这个节点的信息 }
}//分裂 

merge

有分必有和，天下大事合久必分分久必合哈哈哈哈哈。
这个就是把两个节点个合并，比较简单，这里面合并就要用到索引来保证这个树的高度了，之后就是很简单的代码

inline int merge(int x,int y){
    //注意这里的顺序 我们要保证val-》x是小于val-》y的if(!x || !y) return x + y; 	if(fhq[x].key > fhq[y].key) {
    //这里写啥都行，只不过是随机而已 这里也就是优先级的比较，按照二叉堆，y在x下。按照二叉搜索树。有y在x右边，所以说在右下方 fhq[x].r = merge(fhq[x].r,y);update(x);return x;}else{
    fhq[y].l = merge(x,fhq[y].l);update(y);return y;}}//合并 

插入节点

这个也很简单呢，就两行呢
先按照val（节点的）分裂，之后就是随便合并合并就好了

inline void ins(int sum){
    split(root,sum,x,y);root = merge(merge(x,newnode(sum)),y);
}

删除节点

这个难一点点呢，代码要四行呢
首先按val分裂x,y，之后x按照val - 1分裂x,z，这样z里面是不是全是val了，之后把最顶上的那个删掉是不是就好了

inline void del(int val){
    split(root,val,x,z);//先按照val分两棵树x,z split(x,val - 1,x,y);//之后再按照val- 1分成两棵树x,y这样的话，y里面的是不是全部都等于val了 y = merge(fhq[y].l,fhq[y].r);//删掉y里面最顶上的点 root = merge(merge(x,y),z);//全部合并 
} //删除 

查询前驱后继

这个也很简单，直接看代码

inline void pre(int val){
    split(root,val-1,x,y);//按照val - 1分裂，那么左树的最右边一定就是val的前驱 int now = x;while(fhq[now].r){
    now = fhq[now].r;}printf("%d\n",fhq[now].val);root = merge(x,y);
}//查找前驱 inline void suf(int val){
    split(root,val,x,y);//同理树上的最左边一定是int now = y;while(fhq[now].l){
    now = fhq[now].l;}	printf("%d\n",fhq[now].val); root = merge(x,y);
}

查询值的排名

inline void getrank(int val){
    split(root,val - 1,x,y);//这样分裂的话左边的树上给的val是不是全都是小于val的printf("%d\n",fhq[x].size + 1); root = merge(x,y);
}//查询值的排名 

查询排名的值

这颗可以说是最长的，其实就是替罪羊树的那一套

inline void getnum(int ra){
    int now = root;while(now){
    if(fhq[fhq[now].l].size + 1 == ra){
    //这样就找到了 break;}	else if(fhq[fhq[now].l].size >= ra){
    //左子树里面的个数比这个排名大，那么这个数一定在左子树里 now = fhq[now].l;}else{
    ra -= fhq[fhq[now].l].size + 1;//去找右子树，记得要更新这个排名 **不要忘了还有一个加一** now = fhq[now].r;}}printf("%d\n",fhq[now].val);return ;
}//查询排名的值 

文艺平衡树

这个就是对于区间的操作，其实贯穿的是平衡树去维护区间的一个思想

首先我们考虑树上存的是啥，显然是这个节点的值对吧，那么靠什么来维护二叉搜索树的性质呢？显然不可以是值，那样我们如何去维护区间啊，那么是不是就是下标了。

那么平衡树维护区间是什么原理，其实就是通过二叉搜索树的性质，像线段树一样找到这个要修改的区间，之后进行操作，那么他的优势是啥，除了区间反转之外，其实还可以实现插入一个数，这个显然是线段树无法实现的。

而这道题其实就是一个区间反转，比较简单打个标记就好了，首先我们想一想，对于一个区间反转了，意味着啥，是不是这个的下表就不满足二叉搜索树了，我们是不是就要去更改，如何改？是不是假如我们找到了那个区间，之后直接把左右儿子互换是不是就好了，但是左右儿子的儿子是不是没有换，那么我们就打一个标记，之后有需要再换

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n,m;struct node{
    int l,r;int size;int key,val;int fg;
}fhq[maxn];
int cnt,x,y,z,root;void update(int x){
    fhq[x].size = fhq[fhq[x].l].size + fhq[fhq[x].r].size + 1;
}int nownode(int val){
    fhq[++cnt].val = val;fhq[cnt].key = rand();fhq[cnt].size = 1;return cnt;
}void down(int now){
    swap(fhq[now].l,fhq[now].r);fhq[now].fg = 0;fhq[fhq[now].l].fg ^= 1;fhq[fhq[now].r].fg ^= 1;//异或的意思是因为反转两次就抵消了
}void split(int now,int val,int &x,int &y){
    if(!now){
    x = y = 0 ;return;} if(fhq[now].fg) down(now);//这里是按照区间去分割 if(fhq[fhq[now].l].size + 1 <= val){
    x = now;split(fhq[now].r,val - fhq[fhq[now].l].size - 1,fhq[now].r,y);update(x);}else{
    y = now;split(fhq[now].l,val,x,fhq[now].l);update(y);}
}int merge(int x,int y){
    if(!x || !y) return x + y ;if(fhq[x].key > fhq[y].key){
    if(fhq[x].fg) down(x);fhq[x].r = merge(fhq[x].r,y);update(x);return x;}else{
    if(fhq[y].fg) down(y);fhq[y].l = merge(x,fhq[y].l);update(y);return y;}
}void ins(int val){
    split(root,val,x,y);root = merge(merge(x,nownode(val)),y);
}void change(int l,int r){
    split(root,r,x,y);split(x,l - 1,x,z);//这里面的z是不是就是我们找到的区间//split(root,l - 1,x,y);//split(y,r - l + 1,y,z);//or这样写 fhq[z].fg ^= 1;//这里不用改对吧，只用打一个标记root = merge(merge(x,z),y);
}void prt(int now){
    if(fhq[now].fg) down(now);if(fhq[now].l)prt(fhq[now].l);printf("%d ",fhq[now].val);if(fhq[now].r)prt(fhq[now].r);
}int main(){
    scanf("%d%d",&n,&m);for(int i = 1 ;i <= n ; i ++){
    ins(i);}int l,r;while(m--){
    scanf("%d%d",&l,&r);change(l,r);}prt(root);return 0;
}

杂题

一P1503 鬼子进村

这个首先考虑每一个删除的节点就加入树中，之后对于每一个询问查询前驱后继就行了

二P4036 [JSOI2008]火星人

神仙题目，而且我改了一晚上WA，第二天早上再交上去就ac了，大雾

首先我们发现有插入操作，那么就去考虑一下用平衡树去维护区间。

那么我们去维护什么呢？要比较字符串是不是相同是不是很简单就是哈希，那么显然平衡树去维护区间哈希，这里就用一下哈希的计算公式

是不是就可以维护了

至于可以匹配的最大值，是不是一个小小的二分就ok了，这就是一个十分经典的平衡树维护区间信息的题目

三 P5610 [Ynoi2013] 大学

又是一个神仙~题目 ， 虽然我的平衡树做法现在没发过这道题，但是这个思想 还是很值得去学习的。

首先看一下这个题里面有两个操作，显然第二个十分好实现，那么就要去考虑如何高效率去求操作一。

可以发现一个性质就是一个数最多被更改log次就会变成1，之后就再也不会更改他了，那么问题就变成了如何高效率的去找一个区间是k的倍数的数并更改。

注意到这个的值域非常小，这可能就是入手点，我开这么值域大小的平衡树，每一个节点存的是可能是这个值的序号，之后每一次我把这棵树进行分裂，找到属于这个区间的编号，之后在分裂出来的树上进行dfs，每一个数去检查一下是否满足要求，最后就只用暴力更改之后就再次建树就好了。

之后区间求和其实开一个树状数组就好了。
细节还是比较多的

代码如下