首页 > 代码库 > 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;}
View Code

 

POJ 1442 treap