POJ 1442 平衡树Treap模板_平衡树第k大模板-程序员宅基地

技术标签： ＝＝数据结构＝＝  treap  

点击打开链接

题意：输入m个数，询问n个数，第一个数如果是3，就输出在m的第三个数输入完成后第1大的数，第二个就输出第二大的数，但前提都是在输入完U[i]个数后

思路：用平衡树Treap进行插入和查询第K大的数，模版题

[html]  view plain   copy
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #include <stdlib.h>  
  4. #include <iostream>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. typedef long long ll;  
  8. const int inf=0x3f3f3f3f;  
  9. const int maxn=100010;  
  10. class Treap{  
  11.     public:  
  12. struct Treap_Node{  
  13.     Treap_Node *left,*right;  
  14.     int value,fix,weight,size;//fix为修正值，是随机产生的，保证二叉树不会退化的重要环节，wweight为权值，size为子树大小  
  15. }*root,*null;  
  16. Treap(){  
  17.     null=new struct Treap_Node;  
  18.     null->size=0;  
  19.     null->weight=0;  
  20.     null->value=inf;  
  21.     null->left=null;  
  22.     null->right=null;  
  23.     null->fix=inf;  
  24.     root=null;  
  25. }  
  26. void Treap_Print(Treap_Node *P){//从小到大输出  
  27.     if(P!=null){  
  28.         Treap_Print(P->left);  
  29.         printf("%d\n",P->value);  
  30.         Treap_Print(P->right);  
  31.     }  
  32. }  
  33. void Treap_Left_Rotate(Treap_Node *&a){//左旋之后仍不改变二叉树性质  
  34.     Treap_Node *b=a->right;  
  35.     a->right=b->left;  
  36.     b->left=a;  
  37.     b->size=a->size;  
  38.     a->size=a->left->size+a->right->size+a->weight;  
  39.     a=b;  
  40. }  
  41. void Treap_Right_Rotate(Treap_Node *&a){//右旋之后仍不改变二叉树性质  
  42.     Treap_Node *b=a->left;  
  43.     a->left=b->right;  
  44.     b->right=a;  
  45.     b->size=a->size;  
  46.     a->size=a->left->size+a->right->size+a->weight;  
  47.     a=b;  
  48. }  
  49. int Treap_Find(Treap_Node *P,int value){//查找有没有value这个数  
  50.     if(P==null) return 0;  
  51.     if(P->value==value) return 1;  
  52.     else if(value<P->value) return Treap_Find(P->left,value);  
  53.     else return Treap_Find(P->right,value);  
  54. }  
  55. void Treap_Insert(Treap_Node *&P,int value){//插入一个数  
  56.     if(P==null){  
  57.         P=new Treap_Node;  
  58.         P->left=P->right=null;//左右儿子均为空  
  59.         P->value=value;  
  60.         P->fix=rand();  
  61.         P->weight=1;  
  62.         P->size=1;  
  63.     }else if(value==P->value){  
  64.         P->weight++;  
  65.     }  
  66.     else if(value<P->value){  
  67.         Treap_Insert(P->left,value);  
  68.         if(P->left->fix<P->fix)  
  69.             Treap_Right_Rotate(P);  
  70.     }else{  
  71.         Treap_Insert(P->right,value);  
  72.         if(P->right->fix<P->fix)  
  73.             Treap_Left_Rotate(P);  
  74.     }  
  75.     P->size=P->left->size+P->right->size+P->weight;  
  76. }  
  77. void Treap_Delete(Treap_Node *&P,int value){//删除一个数  
  78.     if(P==null) return ;  
  79.     if(value<P->value) Treap_Delete(P->left,value);  
  80.     else if(value>P->value) Treap_Delete(P->right,value);  
  81.     else if(P->weight>1) P->weight--;  
  82.     else if((P->left==NULL)&&(P->right==NULL)){  
  83.         delete P;  
  84.         P=NULL;  
  85.     }else{  
  86.         if(P->left->fix<P->right->fix) Treap_Left_Rotate(P);  
  87.         else Treap_Right_Rotate(P);  
  88.         Treap_Delete(P,value);  
  89.     }  
  90.     P->size=P->left->size+P->right->size+P->weight;  
  91. }  
  92. int Treap_pred(Treap_Node *P,int value,Treap_Node *optimal){//前驱  
  93.     if(P==null||value==P->value) return optimal->value;  
  94.     if(P->value<value) return Treap_pred(P->right,value,P);  
  95.     else return Treap_pred(P->left,value,optimal);  
  96. }  
  97. int Treap_succ(Treap_Node *P,int value,Treap_Node *optimal){//后继  
  98.     if(P==null||value==P->value) return optimal->value;  
  99.     if(P->value>value) return Treap_succ(P->left,value,P);  
  100.     else return Treap_succ(P->right,value,optimal);  
  101. }  
  102. int Treap_Findkth(Treap_Node *P,int k){//求第K大的数  
  103.     if(P==null) return 0;  
  104.     int t=P->left->size;  
  105.     if(k<t+1) return Treap_Findkth(P->left,k);  
  106.     else if(k>t+P->weight) return Treap_Findkth(P->right,k-(t+P->weight));  
  107.     else return P->value;  
  108. }  
  109. int Treap_Rank(Treap_Node *P,int value,int cur){//求这个数的排名  
  110.     int t=P->left->size;  
  111.     if(value==P->value) return t+cur+1;  
  112.     else if(value<P->value) return Treap_Rank(P->left,value,cur);  
  113.     else return Treap_Rank(P->right,value,t+cur+P->weight);  
  114. }  
  115. void Treap_erase(Treap_Node *&P) {//将树清空  
  116.         if(P->left!=null)  
  117.             Treap_erase(P->left);  
  118.         if(P->right!=null)  
  119.             Treap_erase(P->right);  
  120.         delete P;  
  121. }  
  122. };  
  123. int num[30010],num1[50010];  
  124. int main(){  
  125.     int n,a,b,m;  
  126.     while(scanf("%d%d",&n,&m)!=-1){  
  127.         Treap tree;  
  128.         for(int i=1;i<=n;i++) scanf("%d",&num[i]);  
  129.         int t=1,k=1;  
  130.         for(int i=1;i<=m;i++) scanf("%d",&num1[i]);  
  131.         while(t<=m){  
  132.             while(k<=num1[t]){  
  133.                 tree.Treap_Insert(tree.root,num[k]);  
  134.                 k++;  
  135.             }  
  136.             int ans=tree.Treap_Findkth(tree.root,t++);  
  137.             printf("%d\n",ans);  
  138.         }  
  139.     }  
  140.     return 0;  
  141. }  
[html]  view plain   copy
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #include <stdlib.h>  
  4. #include <iostream>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. typedef long long ll;  
  8. typedef unsigned long long ull;  
  9. const int inf=0x3f3f3f3f;  
  10. const ll INF=0x3f3f3f3f3f3f3f3fll;  
  11. const int maxn=15010;  
  12. struct Node{  
  13.     Node *ch[2];  
  14.     int r,v,s;  
  15.     Node(int v):v(v){ch[0]=ch[1]=NULL;r=rand();s=1;}  
  16.     int cmp(int x){  
  17.         if(x==v) return -1;  
  18.         return x<v? 0:1;  
  19.     }  
  20.     void maintain(){  
  21.         s=1;  
  22.         if(ch[0]!=NULL) s+=ch[0]->s;  
  23.         if(ch[1]!=NULL) s+=ch[1]->s;  
  24.     }  
  25. };  
  26. void Rotate(Node* &o,int d){  
  27.     Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;  
  28.     o->maintain();k->maintain();o=k;  
  29. }  
  30. void Insert(Node* &o,int x){  
  31.     if(o==NULL) o=new Node(x);  
  32.     else{  
  33.         int d=x<(o->v)? 0:1;  
  34.         Insert(o->ch[d],x);  
  35.         if(o->ch[d]->r>o->r) Rotate(o,d^1);  
  36.     }  
  37.     o->maintain();  
  38. }  
  39. void Remove(Node* &o,int x){  
  40.     int d=o->cmp(x);  
  41.     if(d==-1){  
  42.         Node* u=o;  
  43.         if(o->ch[0]!=NULL&&o->ch[1]!=NULL){  
  44.             int d2=(o->ch[0]->r>o->ch[1]->r?1:0);  
  45.             Rotate(o,d2);Remove(o->ch[d2],x);  
  46.         }else{  
  47.             if(o->ch[0]==NULL) o=o->ch[1];  
  48.             else o=o->ch[0];  
  49.             delete u;  
  50.         }  
  51.     }else Remove(o->ch[d],x);  
  52.     if(o!=NULL) o->maintain();  
  53. }  
  54. int Kth(Node* &o,int k){//第K大的值  
  55.     if(o==NULL||k<=0||k>o->s) return 0;  
  56.     int s=(o->ch[0]==NULL?0:o->ch[0]->s);  
  57.     if(k==s+1) return o->v;  
  58.     else if(k<=s) return Kth(o->ch[0],k);  
  59.     else return Kth(o->ch[1],k-s-1);  
  60. }  
  61. int Rank(Node* &o,int x){//x的排名  
  62.     if(o==NULL) return -1;//未找到  
  63.     int num=o->ch[0]==NULL?0:o->ch[0]->s;  
  64.     if(x==o->v) return num+1;  
  65.     else if(x<o->v) return Rank(o->ch[0],x);  
  66.     else return Rank(o->ch[1],x)+num+1;  
  67. }  
  68. void deletetree(Node* &o){  
  69.     if(o->ch[0]!=NULL) deletetree(o->ch[0]);  
  70.     if(o->ch[1]!=NULL) deletetree(o->ch[1]);  
  71.     delete o;o=NULL;  
  72. }  
  73. int num[30010],num1[50010];  
  74. int main(){  
  75.     int n,m,a,b;  
  76.     while(scanf("%d%d",&n,&m)!=-1){  
  77.         Node* root=NULL;  
  78.         for(int i=1;i<=n;i++) scanf("%d",&num[i]);  
  79.         for(int i=1;i<=m;i++) scanf("%d",&num1[i]);  
  80.         int t=1,k=1;  
  81.         while(t<=m){  
  82.             while(k<=num1[t]){  
  83.                 Insert(root,num[k]);  
  84.                 k++;  
  85.             }  
  86.             int ans=Kth(root,t++);  
  87.             printf("%d\n",ans);  
  88.         }  
  89.         deletetree(root);  
  90.     }  
  91.     return 0;  
  92. } 
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/The_star_is_at/article/details/59110418

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时，向何处发送表单中的数据，地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios

如何将EXCEL表导入plsql数据库中-程序员宅基地

文章浏览阅读5.3k次。方法一：用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头，使全列成选中状态，然后粘贴，最后commit提交即可。（前提..._excel导入pl/sql

Git常用命令速查手册-程序员宅基地

文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，包括untracked的文件...

分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120-程序员宅基地

文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120

【C++缺省函数】 空类默认产生的6个类成员函数_空类默认产生哪些类成员函数-程序员宅基地

文章浏览阅读1.8k次。版权声明：转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数

推荐文章

热门文章

相关标签