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 30005

using namespace std;

int cnt=,rt=;

int n,m,a[MAXN],u[MAXN];

struct Tree

{

    int key, size, pri, son[];

    void set(int x, int y, int z)

    {

        key=x;

        pri=y;

        size=z;

        son[]=son[]=;

    }

}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 == )

        T[x = cnt++].set(key, rand(), );

    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[]].size+)

        return T[x].key;

    if(p > T[T[x].son[]].size+)

        find(p-T[T[x].son[]].size-, T[x].son[]);

    else

        find(p, T[x].son[]);

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i=; i<n; i++)

        scanf("%d", &a[i]);

    for(int i=; i<=m; i++)

    {

        scanf("%d", &u[i]);

        for(int j=u[i-]; j<u[i]; j++)

            ins(a[j], rt);

        printf("%d\n", find(i, rt));

    }

    return ;

}