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。

相关文章

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

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

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

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

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

Python程序的文件头部声明小结

《Python程序的文件头部声明小结》在Python文件的顶部声明编码通常是必须的,尤其是在处理非ASCII字符时,下面就来介绍一下两种头部文件声明,具有一定的参考价值,感兴趣的可以了解一下... 目录一、# coding=utf-8二、#!/usr/bin/env python三、运行Python程序四、
阅读更多...
Python中合并列表(list)的六种方法小结

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用
阅读更多...
Spring Boot中的YML配置列表及应用小结

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,：本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总
阅读更多...
CSS 样式表的四种应用方式及css注释的应用小结

CSS 样式表的四种应用方式及css注释的应用小结

《CSS样式表的四种应用方式及css注释的应用小结》：本文主要介绍了CSS样式表的四种应用方式及css注释的应用小结，本文通过实例代码给大家介绍的非常详细，详细内容请阅读本文，希望能对你有所帮助... 一、外部 css（推荐方式）定义：将 CSS 代码保存为独立的 .css 文件，通过 <link> 标签
阅读更多...
CSS引入方式和选择符的讲解和运用小结

CSS引入方式和选择符的讲解和运用小结

《CSS引入方式和选择符的讲解和运用小结》CSS即层叠样式表，是一种用于描述网页文档（如HTML或XML）外观和格式的样式表语言,它主要用于将网页内容的呈现（外观）和结构（内容）分离，从而实现... 目录一、前言二、css 是什么三、CSS 引入方式1、行内样式2、内部样式表3、链入外部样式表四、CSS 选
阅读更多...
$在R语言中的作用示例小结

$在R语言中的作用示例小结

《$在R语言中的作用示例小结》在R语言中,$是一个非常重要的操作符,主要用于访问对象的成员或组件,它的用途非常广泛,不仅限于数据框（dataframe）,还可以用于列表（list）、环境（enviro... 目录1. 访问数据框（data frame）中的列2. 访问列表（list）中的元素3. 访问jav
阅读更多...
Redis中HyperLogLog的使用小结

Redis中HyperLogLog的使用小结

《Redis中HyperLogLog的使用小结》Redis的HyperLogLog是一种概率性数据结构,用于统计唯一元素的数量（基数）,本文主要介绍了Redis中HyperLogLog的使用小结,感兴... 目录 一、HyperlogLog 是什么？️ 二、使用方法1. 添加数据2. 查询基数China编程3.
阅读更多...
pandas DataFrame keys的使用小结

pandas DataFrame keys的使用小结

《pandasDataFramekeys的使用小结》pandas.DataFrame.keys()方法返回DataFrame的列名,类似于字典的键,本文主要介绍了pandasDataFrameke... 目录Pandas2.2 DataFrameIndexing, iterationpandas.DataF
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2