Treap小结

2024-06-16 01:38
文章标签 小结 treap

本文主要是介绍Treap小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Treap(Tree+Heap)---是一种通过 rand() 来随机生成数字作为修正值来调整的平衡树。

基本操作：

1.旋转。

2.插入（合并重复的），删除（懒惰删除）。

3.查最值，求第k小，求排名。

4.中序遍历就是从小到大的。

5.维护附加关键字.

1.求第k小:

POJ1442

//12321199		1442	Accepted	976K	204MS	C++	2080B	2013-11-22 20:33:35静态
//12321216		1442	Accepted	1804K	329MS	C++	2125B	2013-11-22 20:39:40动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 30005
int a[MAX];
int u[MAX];
int tot;
class Node
{
public:int vol,fix;int size;Node *left;Node *right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root;//space[MAX]
void left_rotate(Node *&a)
{Node *b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void right_rotate(Node *&a)
{Node *b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void insert(Node*&p,int vol)
{if(!p){p=new Node();//p=&space[tot++];  //静态p->fix=rand();p->vol=vol;p->size=1;}else if(vol<=p->vol){insert(p->left,vol);p->size++;if(p->left->fix < p->fix)right_rotate(p);}else{insert(p->right,vol);p->size++;if(p->right->fix < p->fix)left_rotate(p);}
}
int get_kth(Node *&p,int k)
{int key=p->lsize()+1;if(k < key)return get_kth(p->left,k);else if(k > key)return get_kth(p->right,k-key);elsereturn p->vol;
}
void init()
{root=NULL;//memset(space,0,sizeof(space));静态//tot=1;
}
int main()
{srand(time(0));int n,m;while(~scanf("%d%d",&m,&n)){for(int i=1;i<=m;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&u[i]);int j=1;init();for(int i=1;i<=m;i++){insert(root,a[i]);while(j<=n&&i==u[j]){printf("%d\n",get_kth(root,j));j++;}if(j>n) break;}}return 0;
}

2.动态求最值 

//12321728		3481	Accepted	212K	282MS	C++	1857B	2013-11-22 22:26:19动态
#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
//#define MAX 10000005
class Node
{
public:int vol,fix,cus;Node* left;Node* right;
}*root;//,space[MAX]  
int tot=1;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;
}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;
}
void insert(Node*&p,int cus,int vol)
{if(!p){p=new Node();//p=&space[tot++];p->fix=rand();p->vol=vol;p->cus=cus;}else if(p->vol >= vol){insert(p->left,cus,vol);if(p->left->fix < p->fix)r_rotate(p);}else{insert(p->right,cus,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
int Min(Node*&p)
{if(!p)return 0;if(!p->left){Node*t=p;int ans=p->cus;p=p->right;delete t;return ans;}else return Min(p->left);
}
int Max(Node*&p)
{if(!p)return 0;if(!p->right){Node*t=p;int ans=p->cus;p=p->left;delete t;return ans;}else return Max(p->right);
}
int main()
{srand(time(0));int a;while(~scanf("%d",&a)&&a){if(a==1){int b,c;scanf("%d%d",&b,&c);insert(root,b,c);}else if(a==3){printf("%d\n",Min(root));}else{printf("%d\n",Max(root));}}return 0;
}

3.区间第k小: 

//12329808		2761	Accepted	3500K	1844MS	C++	3889B	2013-11-25 21:28:45静态
//12329836		2761	Accepted	3900K	3922MS	C++	3962B	2013-11-25 21:34:10动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000005
int dog[MAX];
int ans[MAX];
class Interval
{
public:int s,e,k;int id;bool operator<(const Interval a) const{return s<a.s;}
}qu[MAX];
class Node
{
public:int vol,fix,size;Node*left;Node*right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root,space[MAX];
int tot;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;/**RE在这里，不要把求size顺序搞反了*/a->size=a->lsize()+a->rsize()+1;}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;}
void insert(Node*&p,int vol)
{if(!p){p=&space[tot++];//p=new Node();p->left=NULL;p->right=NULL;p->fix=rand();p->vol=vol;p->size=1;}else if(p->vol > vol){p->size++;insert(p->left,vol);if(p->left->fix < p->fix)r_rotate(p);}else{p->size++;insert(p->right,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
void del(Node*&p,int key)
{if(!p) return ;p->size--;  /**注意size的减减**/if(key==p->vol){if(!p->left || !p->right){//Node *t=p;if(!p->left)p=p->right;elsep=p->left;//delete t;}else{if(p->right->fix < p->left->fix){l_rotate(p);p->size--;/**注意size的减减**/del(p->left,key);}else{r_rotate(p);p->size--;/**注意size的减减**/del(p->right,key);}}}else if(key < p->vol)del(p->left,key);elsedel(p->right,key);
}
int find_kth(Node*&p,int k)
{int sum=p->lsize()+1;if(k < sum){return find_kth(p->left,k);}else if(k>sum){return find_kth(p->right,k-sum);}else{return p->vol;}
}
int solve(Interval t1,Interval t2)
{for(int i=t1.s;i<=min(t2.s-1,t1.e);i++)del(root,dog[i]);if(t1.e > t2.e){for(int i=t2.e+1;i<=t1.e;i++)del(root,dog[i]);}for(int i=max(t1.e+1,t2.s);i<=t2.e;i++)insert(root,dog[i]);return find_kth(root,t2.k);
}
int main()
{srand(time(0));//int T;//scanf("%d",&T);int n,m;while(~scanf("%d%d",&n,&m)){root=NULL;tot=1;memset(space,NULL,sizeof(space));for(int i=1;i<=n;i++)scanf("%d",&dog[i]);for(int i=1;i<=m;i++){scanf("%d%d%d",&qu[i].s,&qu[i].e,&qu[i].k);if(qu[i].s > qu[i].e) swap(qu[i].s,qu[i].e);qu[i].id=i;}sort(qu+1,qu+1+m);for(int i=qu[1].s;i<=qu[1].e;i++)insert(root,dog[i]);ans[qu[1].id]=find_kth(root,qu[1].k);for(int i=2;i<=m;i++){ans[qu[i].id]=solve(qu[i-1],qu[i]);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}




这篇关于Treap小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1065160。

相关文章

C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
Python中反转字符串的常见方法小结

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函
阅读更多...
C#中Guid类使用小结

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建
阅读更多...
Redis分片集群、数据读写规则问题小结

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题？（与哨兵模
阅读更多...
SpringBoot中使用Flux实现流式返回的方法小结

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回（StreamingResponse）在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp
阅读更多...
Python打印对象所有属性和值的方法小结

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...
Java对异常的认识与异常的处理小结

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。（1）简单定义-什么是
阅读更多...
Python函数返回多个值的多种方法小结

Python函数返回多个值的多种方法小结

《Python函数返回多个值的多种方法小结》在Python中,函数通常用于封装一段代码,使其可以重复调用,有时,我们希望一个函数能够返回多个值,Python提供了几种不同的方法来实现这一点,需要的朋友... 目录一、使用元组（Tuple）:二、使用列表（list）三、使用字典（Dictionary）四、 使
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2