首页 > 代码库 > POJ 1442 treap
POJ 1442 treap
裸treap。
只需增加一个size记录其儿子个数便可找到第k大数。
#include <cstdio>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 30005using namespace std;int cnt=1,rt=0;int n,m,a[MAXN],u[MAXN];struct Tree{ int key, size, pri, son[2]; void set(int x, int y, int z) { key=x; pri=y; size=z; son[0]=son[1]=0; }}T[MAXN];void rotate(int p, int &x){ int y=T[x].son[!p]; T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size; T[x].son[!p]=T[y].son[p]; T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size; T[y].son[p]=x; x=y;}void ins(int key, int &x){ if(x == 0) T[x = cnt++].set(key, rand(), 1); else { T[x].size++; int p=key < T[x].key; ins(key, T[x].son[!p]); if(T[x].pri < T[T[x].son[!p]].pri) rotate(p, x); }}int find(int p, int &x){ if(p == T[T[x].son[0]].size+1) return T[x].key; if(p > T[T[x].son[0]].size+1) find(p-T[T[x].son[0]].size-1, T[x].son[1]); else find(p, T[x].son[0]);}int main(){ scanf("%d%d", &n, &m); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=1; i<=m; i++) { scanf("%d", &u[i]); for(int j=u[i-1]; j<u[i]; j++) ins(a[j], rt); printf("%d\n", find(i, rt)); } return 0;}
POJ 1442 treap
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。