题解 P3369 【【模板】普通平衡树】
king_storm · · 题解
平衡树板子
其实这就是平衡树的模板，我们有两种做法，第一种就是直接手写平衡树FHQ,还有一种就是用stl，前者比较快，stl又分两种：vector和set（主要是multiset）;这里我主要讲两种FHQ和vector（主要是set不好操作qwq）。
FHQ是最近几年才流行的，是一个学生（范浩强）的大牛发明出来的，它主要涉及到两种操作哦，第一种就是分裂（split），与合并（merge），而这道题还需要多加一个函数kth求排名为k的树；不做多解释了，代码上慢慢解释——————1.
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e6+10;
int n,root,l,r,p,cnt;//（l,r,q分别表示左子树与右子树还有中间节点的根）；
struct node
{
int l,r;
int val,key;//val记录值,key记录键值（key值随机化，这样程序更加运行的稳定）
int size;//size记录当前树的节点数
}tree[M];
void update(int u)//size包括根自己
{
tree[u].size=tree[tree[u].l].size+tree[tree[u].r].size+1;//更新节点数
}
void split(int u,int x,int &l,int &r)//加个&是为了可以吧l与r同时传回去（这也不叫传，就叫记录好了）；
{//分离操作
if(!u)
{//到底了
l=r=0;
return ;
}
if(tree[u].val<=x)
{//确定左子树的根
l=u;
split(tree[u].r,x,tree[u].r,r);//递归右子树
}
if(tree[u].val>x)
{//确定右子树的根
r=u;
split(tree[u].l,x,l,tree[u].l);//递归左子树
}
update(u);//更新当前的节点
}
void adde(int x)
{//建立只有一个节点的树
cnt++;tree[cnt].size=1;
tree[cnt].l=tree[cnt].r=0;
tree[cnt].val=x;tree[cnt].key=rand();//精髓,随机化,防止数据卡一条链
}
int merge(int l,int r)
{//合并操作(可以同左偏树一起理解)
if(!l || !r)//找到叶子节点
return l+r;
//维护键值的一个小根堆
if(tree[l].key<=tree[r].key)
{//l节点是父亲节点
tree[l].r=merge(tree[l].r,r);//其左儿子为原来的左儿子,只需更新右儿子
update(l);return l;
}
if(tree[l].key>tree[r].key)
{//r节点是父亲节点
tree[r].l=merge(l,tree[r].l);//其右儿子为原来的右儿子,只需更新左儿子
update(r);return r;
}
}
int kth(int u,int k)
{//求排名第k的数
if(k<=tree[tree[u].l].size)//在左区间
return kth(tree[u].l,k);
else if(k==tree[tree[u].l].size+1)//这个数为此区间的根
return u;
else
{
k-=(tree[tree[u].l].size+1);//排名为k要减少左儿子的节点数
return kth(tree[u].r,k);//在右区间
}
}
int main()
{
scanf("%d",&n);
int opt,x;//opt为操作，x变量；
for(int i=1;i<=n;i++)
{
scanf("%d%d",&opt,&x);
if(opt==1)
{//添加操作
split(root,x,l,r);//先分离<=x和>x的两棵树
adde(x);//新建一颗只有一个节点的为x的树
root=merge(merge(l,cnt),r);//在<=x的树里面添加这棵树并且合并之前分离的>x的树
}
if(opt==2)
{//删除操作(两次分离操作)
split(root,x,l,r);//分离<=x的树和>x的树
split(l,x-1,l,p);//分离<x的树和==x的树
p=merge(tree[p].l,tree[p].r);//删除==x的树中的其中一个x,只能删一个,不能删整棵树 ，左儿子和右儿子合并后根节点就没了
root=merge(merge(l,p),r);//将<x的树,>x的树以及剩余的==x的树合并
}
if(opt==3)
{//查询数x的排名
split(root,x-1,l,r);//先分离<x的树和>=x的树
printf("%d\n",tree[l].size+1);//树x的排名即为<x的树中元素的个数+1,不能分离成<=x的树,因为x有可能不止一个
root=merge(l,r);//合并
}
if(opt==4)
{//找排名第k的数
printf("%d\n",tree[kth(root,x)].val);//kth返回的是此节点
}
if(opt==5)
{//求x的前驱
split(root,x-1,l,r);//先分离<x的树和>=x的树
printf("%d\n",tree[kth(l,tree[l].size)].val);//<x的树中 排名第 此树元素个数(size) 的数即为此树的前驱,不能分离成<=x的树,理由同上
root=merge(l,r);//合并
}
if(opt==6)
{//求x的后继
split(root,x,l,r);//先分离<=x的树和>x的树
printf("%d\n",tree[kth(r,1)].val);//>x的树中排名第一的数即为此数的后继,不能分离成>x的树,理由同上
root=merge(l,r);//合并
}
}
return 0;
}
代码也就100多行，看不懂的地方就说吧，其实也不长，几个函数也很简单；
还有一种就是vector，他非常简单，就是几个操作，但跑的是真的慢，考试的话很容易被卡，不建议大家使用（这道题范围较小，2w以内vector就可以过（应该是这样））； 献出我丑陋的代码（这份我就不作出解释了（反正也不是我主要讲的），不懂就在网上搜一下vector的用法吧）
还是给你们说吧
头文件 #include<vector>
向量的定义：
vector<int> vec；//定义一个vec型的向量a
vector<int> vec(5); //定义一个初始大小为5的向量
vector<int> vec(5,1); //初始大小为5，值都为1的向量
因为vector是可以根据插入的值的数量自动增长的，所以初始定义的时候只需要按照第一种方法定义就可以了(一维)。 很多时候我们需要开一个二维数组：
vector<vector<int>> vec(100);
Vector的下标和数组一样从0开始的
vec.size(); //返回向量的实际大小
vec.begin(); //返回向量的开始指针的位置
vec.end(); //返回向量的结束指针的下一个位置
vec.push_back(x); //在对象末尾插入数据x
vec.pop_back(); //在对象末尾删除数据
vec.clear(); //清除对象中的所有数据
vec.at(i); //访问容器中第i个数的值(推荐)
vec[i]: //访问容器中第i个数的值(不推荐) v
在第i+1个数前面插入一个数x：
vec.insert(vec.begin()+i,x);
删除第i+1个数:
vec.erase(vec.begin()+i);
这才是vector的精髓所在，以上删除，插入操作都是logn的，因为vector下标是从0开始的，所以下标为i的数实际上就是第i+1个数
以上两个操作再集合两个STL函数可以1行代码实现一个平衡树的单点操作。
include<algorithm>
这个头文件中有很多很实用的库函数，其中三个在noip范围内经常被用到
lower_bound();
upper_bound();
unique();//判重
1….lower_bound(a+1,a+n+1,x);
二分查找有序表中第一个大于等于x的数的位置
仅适用于非降序的有序表，如果是非升序的有序表，则需要重载：
lower_bound(a+1,a+n+1,x,greater<int>());
返回有序表中第一个小于等于x的数的位置，仅适用于非升序的有序表
给大家一个例子
一个长度为n的有序不下降序列，给定m次查找，如果查找的数在序列中，输出在序列中第一次出现的位置，如果不在序列中，输出他在哪两个位置之间(保证查找的数肯定在序列两个端点之间）
伪代码 ：
int t=lower_bound(a+1,a+n+1,x)-a;//查找第一个大于等于x的数的位置，返回值是地址 if(a[t]==x) //如果这个数==x
printf("%d\n",t);
else //否则就在两个数之间
printf("%d %d\n",t-1,t);
2…upper_bound(a+1,a+n+1,x);
二分查找有序表中第一个大于x的数的位置
仅适用于非降序的有序表，如果是非升序的有序表，则需要重载：
upper_bound(a+1,a+n+1,x,greater<int>());
返回有序表中第一个小于x的数的位置，仅适用于非升序的有序表
例子差不多（手动滑稽）
一个长度为n的有序不下降序列，给定m次查找，如果查找的数在序列中，输出在序列中最后一次出现的位置，如果不在序列中，输出他在哪两个位置之间(保证查找的数肯定在序列两个端点之间）
伪码子:
int t=upper_bound(a+1,a+n+1,x)-a;//查找第一个大于x的数的位置，返回值是地址
if(a[t-1]==x) //如果这个数的前一个数==x
printf("%d\n",t-1);
else //否则就在两个数之间
printf("%d %d\n",t-1,t);
3…unique(a+1,a+n+1):
STL的去重函数，他的时间复杂度和手动去重(先排序，后去重)一样，都是nlogn，但是他的原理和手动去重不一样，他是把重复的元素放到序列的末尾，序列的前k个数都是不重复的有效元素，所以输出的时候只需要输出有效长度就可以了。
就这样使用
int k=unique(a+1,a+n+1)-a;//得到有效长度
for(int i=1;i<=k;i++) //只输出有效长度
printf("%d ",a[i]);
讲的差不多了，接下来就是vector的表演时刻了！！
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100050;
vector<int> vec;
int a,b,x,n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&x);
if(a==1)
{
vec.insert(lower_bound(vec.begin(),vec.end(),x),x);
}
if(a==2)
{
vec.erase(lower_bound(vec.begin(),vec.end(),x));
}
if(a==3)
{
printf("%d\n",lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1);
}
if(a==4)
{
printf("%d\n",vec.at(x-1));
}
if(a==5)
{
printf("%d\n",vec.at(lower_bound(vec.begin(),vec.end(),x)-vec.begin()-1));
}
if(a==6)
{
printf("%d\n",vec.at(upper_bound(vec.begin(),vec.end(),x)-vec.begin()));
}
}
return 0;
}
好像stl讲的更多了？？无所谓
所以，这道题就讲完了，没搞懂的评论或者私信发给我吧，我可以帮你解答（趁我还没忘（手动滑稽））！！！！！