新学习了fhq treap,厉害了
先贴个神犇的版,
from memphis
/*
Treap[Merge,Split]
by Memphis
*/ #include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
#define maxn 2000005
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i) struct Treap{
Treap *l,*r;
int fix,key,size;
Treap(int key_):fix(rand()),key(key_),l(NULL),r(NULL),size(){} inline void updata(){
size=+(l?l->size:)+(r?r->size:);
}
}*root;
typedef pair<Treap*,Treap*> Droot;//用来Split返回两个根 inline int Size(Treap *x){return x?x->size:;}//这样求size可以防止访问空指针 Treap *Merge(Treap *A,Treap *B){//合并操作
if(!A)return B;
if(!B)return A;
if(A->fix<B->fix){
A->r=Merge(A->r,B);
A->updata();
return A;
}else{
B->l=Merge(A,B->l);
B->updata();
return B;
}
} Droot Split(Treap *x,int k){//拆分操作
if(!x)return Droot(NULL,NULL);
Droot y;
if(Size(x->l)>=k){
y=Split(x->l,k);
x->l=y.second;
x->updata();
y.second=x;
}else{
y=Split(x->r,k-Size(x->l)-);
x->r=y.first;
x->updata();
y.first=x;
}
return y;
} Treap *Build(int *a){//建造操作
static Treap *stack[maxn],*x,*last;
int p=;
rep(i,,a[]){
x=new Treap(a[i]);
last=NULL;
while(p && stack[p]->fix>x->fix){
stack[p]->updata();
last=stack[p];
stack[p--]=NULL;
}
if(p) stack[p]->r=x;
x->l=last;
stack[++p]=x;
}
while(p) stack[p--]->updata();
return stack[];
} int Findkth(int k){//查找第K小
Droot x=Split(root,k-);
Droot y=Split(x.second,);
Treap *ans=y.first;
root=Merge(Merge(x.first,ans),y.second);
return ans->key;
} int Getkth(Treap *x,int v){//询问一个数是第几大
if(!x)return ;
return v<x->key?Getkth(x->l,v):Getkth(x->r,v)+Size(x->l)+;
} void Insert(int v){//插入操作
int k=Getkth(root,v);
Droot x=Split(root,k);
Treap *n=new Treap(v);
root=Merge(Merge(x.first,n),x.second);
} void Delete(int k){//删除操作
Droot x=Split(root,k-);
Droot y=Split(x.second,);
root=Merge(x.first,y.second);
} int a[maxn],M,x,y; int main(){
freopen("bst.in","r",stdin);
freopen("bst.out","w",stdout); scanf("%d",a);
rep(i,,a[]) scanf("%d",a+i);
sort(a+,a++a[]);
root=Build(a); scanf("%d",&M);
while(M--){
char ch=getchar();
while(ch!='Q' && ch!='A' && ch!='D') ch=getchar();
scanf("%d",&x);
if(ch=='Q') printf("%d\n",Findkth(x));
if(ch=='A') Insert(x);
if(ch=='D') Delete(x);
}
}
未完待续~~~
fhq treap最终模板的更多相关文章
-
Luogu P3835 【模板】可持久化平衡树(fhq Treap)
P3835 [模板]可持久化平衡树 题意 题目背景 本题为题目普通平衡树的可持久化加强版. 题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本 ...
-
洛谷P3369 【模板】普通平衡树(FHQ Treap)
题面 传送门 题解 写了一下\(FHQ\ Treap\) //minamoto #include<bits/stdc++.h> #define R register #define inl ...
-
FHQ Treap及其可持久化与朝鲜树式重构
FHQ Treap,又称无旋treap,一种不基于旋转机制的平衡树,可支持所有有旋treap.splay等能支持的操作(只有在LCT中会比splay复杂度多一个log).最重要的是,它是OI中唯一一种 ...
-
[BZOJ 3173] [TJOI 2013] 最长上升子序列(fhq treap)
[BZOJ 3173] [TJOI 2013] 最长上升子序列(fhq treap) 题面 给定一个序列,初始为空.现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置.每插入一个数 ...
-
NOI 2002 营业额统计 (splay or fhq treap)
Description 营业额统计 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司的账本,账本上记录了公司成立以来每 ...
-
FHQ Treap摘要
原理 以随机数维护平衡,使树高期望为logn级别 不依靠旋转,只有两个核心操作merge(合并)和split(拆分) 因此可持久化 先介绍变量 ; int n; struct Node { int v ...
-
在平衡树的海洋中畅游(四)——FHQ Treap
Preface 关于那些比较基础的平衡树我想我之前已经介绍的已经挺多了. 但是像Treap,Splay这样的旋转平衡树码亮太大,而像替罪羊树这样的重量平衡树却没有什么实际意义. 然而类似于SBT,AV ...
-
浅谈fhq treap
一.简介 fhq treap 与一般的treap主要有3点不同 1.不用旋转 2.以merge和split为核心操作,通过它们的组合实现平衡树的所有操作 3.可以可持久化 二.核心操作 代码中val表 ...
-
fhq treap抄袭笔记
目录 碎碎念 点一下 注意!!! 模板 fhq treap 碎碎念 我咋感觉合并这么像左偏树呢 ps:难道你们的treap都是小头堆的吗 fhq真的是神人 现在看以前学的splay是有点恶心,尤其是压 ...
随机推荐
-
mysql 中的数据类型
unsigned 既为非负数,用此类型可以增加数据长度! 例如如果 tinyint最大是127,那 tinyint unsigned 最大 就可以到 127 * ...
-
【PAT】1012. The Best Rank (25)
题目链接: http://pat.zju.edu.cn/contests/pat-a-practise/1012 题目描述: To evaluate the performance of our fi ...
-
jquery easyui datagrid动态改变title的值
title:'<input type="text" id="txtTitle1" style="background:none;border:n ...
-
SQL Server 增加链接服务器
exec sp_addlinkedserver '名称' , '' , 'SQLOLEDB' , '10.102.29.xxx' exec sp_addlinkedsrvlogin '名称' , 'f ...
-
Python科学计算结果的存储与读取
Python科学计算结果的存储与读取 总结于2019年3月17日 荆楚理工学院 计算机工程学院 一.前言 显然,作为一名工科僧,执行科学计算,需用Python.PS:快忘记Matlab吧.我用了二十 ...
-
WCF开发实战系列二:使用IIS发布WCF服务
WCF开发实战系列二:使用IIS发布WCF服务 (原创:灰灰虫的家http://hi.baidu.com/grayworm) 上一篇中,我们创建了一个简单的WCF服务,在测试的时候,我们使用VS200 ...
-
Android Studio 遇到 No Debuggable Applications 的解决方案
一.在菜单的Tools -> Android -> 勾选 Enable ADB Integration 二.在工程的build.gradle(Module:app)里加上一行代码
-
Ubuntu 14.04(64bit)使用mentohust连接校园网
ubuntu14.04系统安装成功之后,需要连接上网络才可以对更新系统以及安装一些必须包.而在学校中,经常遇到的情况需要通过锐捷客户端来连接校园网. 更新: 在Ubuntu14.04下面不用装ment ...
-
9.spring:事务管理(下):声明式事务管理
声明式事务管理 sprin的声明式事务是管理AOP技术实现的事务管理,其本质是是对方法前后进行拦截,然后 在目标方法开始之前创建或者加入一个事务,在执行完成目标方法之后根据执行情况提交或者回滚事务. ...
-
30、Flask实战第30天:cms模版抽离和个人信息页面完成
cms模版抽离 新建一个cms_base.html文件作为基础模板,把cms_index.html的内容拷贝到cms_base.html中. 编辑 cms_base.html,把在不同页面会变动的部分 ...