P3369 【模板】普通平衡树 题解（Splay/FHQ）
2024-08-31 01:01:46
题目链接
解题思路1：Splay
注意查询的时候大于小于等于号千万不要搞错了；注意适时伸展
AC代码1
#include<stdio.h>
#define root t[0].s[1]
struct Tree{
int s[2];//son
int sum;//总 数字 数
int cnt;//frequence
int f;//father
int data;
}t[200010];
int size,tot;//最大节点序号，总 数字 数
void upd(int x){
t[x].sum=t[t[x].s[0]].sum+t[t[x].s[1]].sum+t[x].cnt;//更新节点
}
int id(int x){//查询该节点为左儿子还是右儿子
return x==t[t[x].f].s[0]?0:1;
}
void connect(int x,int fa,int son){//x->fa,fa.son->x
t[x].f=fa;
t[fa].s[son]=x;
}
void rotate(int x){//x为中心的旋转
int y=t[x].f,idx=id(x),idy=id(y),B=t[x].s[idx^1],R=t[y].f;
connect(B,y,idx);
connect(y,x,idx^1);
connect(x,R,idy);
upd(y);upd(x);
}
void splay(int now,int to){//把now转为to的父亲的孩子节点（转到to的位置）
to=t[to].f;
while(to!=t[now].f){
int up=t[now].f;
if(to==t[up].f)rotate(now);//只能翻上去一次
else if(id(now)==id(up)){
rotate(up);
rotate(now);
}
else{
rotate(now);
rotate(now);
}
}
}
int create(int v,int fa){//建立节点
t[++size].data=v;
t[size].f=fa;
t[size].cnt=t[size].sum=1;
return size;
}
void push(int v){//找到插入的位置插入
int sign=0,nxt;
tot++;
if(!root)root=create(v,0);
else{
int now=root;
while(now){
t[now].sum++;
if(t[now].data==v){
t[now].cnt++,sign=now;
break;
}
nxt=t[now].data<v?1:0;
if(!t[now].s[nxt]){
sign=t[now].s[nxt]=create(v,now);
break;
}
now=t[now].s[nxt];
}
}
splay(sign,root);
}
int find(int v){
int now=root,nxt;
while(now){
if(t[now].data==v){
splay(now,root);
return now;
}
nxt=t[now].data<v?1:0;
now=t[now].s[nxt];
}
return 0;
}
void destroy(int x){//删除节点
t[x].cnt=t[x].data=t[x].f=t[x].sum=t[x].s[0]=t[x].s[1]=0;
if(x==size)size--;
}
void pop(int v){
int node=find(v);
if(!node)return;
tot--;
if(t[node].cnt>1){
t[node].cnt--,t[node].sum--;
return;
}
if(!t[node].s[0])root=t[node].s[1],t[root].f=0;
else{
int mx=t[node].s[0],B=t[node].s[1];
while(t[mx].s[1])mx=t[mx].s[1];//找到左子树最大点，翻上来
splay(mx,root);
connect(B,mx,1);
connect(mx,0,1);
upd(mx);
}
destroy(node);
}
int rank(int v){
int ans=0,now=root,nxt;
while(now){
if(t[now].data==v){
int r=ans+t[t[now].s[0]].sum+1;
splay(now,root);
return r;
}
nxt=t[now].data<v?1:0;
if(nxt)ans+=t[t[now].s[0]].sum+t[now].cnt;
now=t[now].s[nxt];
}
return ans;
}
int value(int x){
int now=root,les,res;
while(1){
les=t[t[now].s[0]].sum;
res=les+t[now].cnt;
if(res<x)now=t[now].s[1],x-=res;
else if(les>=x)now=t[now].s[0];
else{splay(now,root);return t[now].data;}
}
}
int upper(int v){
int now=root,res=1e9;
while(now){
if(t[now].data>v&&t[now].data<res)res=t[now].data;
now=t[now].s[t[now].data>v?0:1];
}
return res;
}
int lower(int v){
int now=root,res=-1e9;
while(now){
if(t[now].data<v&&t[now].data>res)res=t[now].data;
now=t[now].s[t[now].data>=v?0:1];//注意大于等于
}
return res;
}
int main(){
int i,n,opt,num;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&opt,&num);
if(opt==1)push(num);
else if(opt==2)pop(num);
else if(opt==3)printf("%d\n",rank(num));
else if(opt==4)printf("%d\n",value(num));
else if(opt==5)printf("%d\n",lower(num));
else printf("%d\n",upper(num));
}
return 0;
}
解题思路2：FHQ
AC代码2
#include<cstdio>
#include<cstdlib>
#define root t[0].s[1]
#define ls t[x].s[0]
#define rs t[x].s[1]
struct fhp{
int size,key,val,s[2];
}t[100010<<1];
int tot;
void upd(int x){
t[x].size=t[ls].size+t[rs].size+1;
}
void split(int x,int k,int &a,int &b){
if(!x){a=b=0;return;}
if(t[x].val<=k)a=x,split(rs,k,rs,b);
else b=x,split(ls,k,a,ls);
upd(x);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].key<t[y].key){rs=merge(rs,y),upd(x);return x;}
else{t[y].s[0]=merge(x,t[y].s[0]),upd(y);return y;}
}
int newnode(int v){
t[++tot].key=rand();
t[tot].val=v;
t[tot].size=1;
return tot;
}
void ins(int v){
int x,y;
split(root,v,x,y);
root=merge(merge(x,newnode(v)),y);
}
void del(int v){
int x,y,z;
split(root,v,x,y);
split(x,v-1,x,z);
z=merge(t[z].s[0],t[z].s[1]);
root=merge(x,merge(z,y));
}
void rank(int x){
int a,b;
split(root,x-1,a,b);
printf("%d\n",t[a].size+1);
root=merge(a,b);
}
void val(int x,int v){
while(1){
if(v<=t[ls].size)x=ls;
else if(v==t[ls].size+1){
printf("%d\n",t[x].val);
return;
}
else v-=t[ls].size+1,x=rs;
}
}
void pre(int v){
int x,y;
split(root,v-1,x,y);
val(x,t[x].size);
root=merge(x,y);
}
void suc(int v){
int x,y;
split(root,v,x,y);
val(y,1);
root=merge(x,y);
}
int main(){
int n,opt,num;
scanf("%d",&n);
while(n--){
scanf("%d%d",&opt,&num);
if(opt==1)ins(num);
else if(opt==2)del(num);
else if(opt==3)rank(num);
else if(opt==4)val(root,num);
else if(opt==5)pre(num);
else suc(num);
}
return 0;
}
最新文章
- Android -- 思考 -- 为什么要在项目中使用MVP模式
- Only the sqlmigrate and sqlflush commands can be used when an app has migrations.
- 解决passwd 为普通用户设密码 不成功的方法
- Window对象简介
- 【iOS】线程安全的文件读写
- Java Hour1
- java CountDownLatch
- eclispse快捷键
- 关于各种排列（dfs）
- ActiveReports 9 新功能：创新的设计分层报告
- VMware下安装Linux（CentOs6.3）操作系统
- Swift中关于任意类型的数组
- sc.exe用法详解
- SQL Server进阶（六）表表达式--派生表、公用表表达式(CTE)、视图和内联表值函数
- 关于Anaconda的环境和包管理
- Mysql模糊查询Like传递参数的语句
- 配置Sublime Text2的python运行环境（Sublime Text 3也类似）
- gdb 不同位置，函数调用参数显示差异
- 8. String to Integer （整数的溢出）
- UWP Button添加圆角阴影（一）