POJ 1442 Black Box(treap練習)

タイトルリンク:http://poj.org/problem?id=1442
題意:1つの数列を与えて、2つの操作:(1)1つの数字を加えて、それを挿入して数列を下げないようにします;(2)i番目に大きい数字を尋ねる.
考え方:ノードは左側のノードの個数、右側のノードの個数と自身の個数(同じ数字があるため)を記録します.この問題は実際にSTLの優先キューで数行のコードしか書かないので、後ろに貼っておきました.

struct node

{

    int L,R,key,pri,cntL,cntR,cnt;

};



class treap

{

public:

    node p[N];

    int size,root;



    void init()

    {

        srand(time(0));

        size=root=-1;

    }



    void rotL(int &x)

    {

        int y=p[x].R;

        p[x].R=p[y].L;

        p[x].cntR=p[y].cntL;

        p[y].L=x;

        p[y].cntL=p[x].cntL+p[x].cntR+p[x].cnt;

        x=y;

    }



    void rotR(int &x)

    {

        int y=p[x].L;

        p[x].L=p[y].R;

        p[x].cntL=p[y].cntR;

        p[y].R=x;

        p[y].cntR=p[x].cntL+p[x].cntR+p[x].cnt;

        x=y;

    }



    void insert(int &k,int key)

    {

        if(k==-1)

        {

            k=++size;

            p[k].L=p[k].R=-1;

            p[k].cnt=1;

            p[k].cntL=p[k].cntR=0;

            p[k].key=key;

            p[k].pri=rand();

        }

        else if(key<p[k].key)

        {

            p[k].cntL++;

            insert(p[k].L,key);

            if(p[p[k].L].pri>p[k].pri) rotR(k);

        }

        else if(key==p[k].key)

        {

            p[k].cnt++;

        }

        else

        {

            p[k].cntR++;

            insert(p[k].R,key);

            if(p[p[k].R].pri>p[k].pri) rotL(k);

        }

    }





    int find(int k,int cnt)

    {

        if(cnt<=p[k].cntL)  return find(p[k].L,cnt);

        cnt-=p[k].cntL;

        if(cnt<=p[k].cnt) return p[k].key;

        cnt-=p[k].cnt;

        return find(p[k].R,cnt);

    }

};





treap a;

int n,m,b[N];



int main()

{

    Rush(n)

    {

        RD(m); a.init();

        int i;

        FOR1(i,n) RD(b[i]);

        i=1;

        int x,t=0;

        while(m--)

        {

            RD(x); t++;

            while(i<=x) a.insert(a.root,b[i++]);

            PR(a.find(a.root,t));

        }

    }

    return 0;

}

　

#include <stdio.h>

#include <queue>

using namespace std;



int a[30005],b[30005],n,m;



int main()

{

	int i,j,k;

	priority_queue<int> Qmin,Qmax;



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

	for(i=1;i<=n;i++) scanf("%d",&a[i]);

	for(i=1;i<=m;i++) scanf("%d",&b[i]);

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

	{

		for(j=b[i-1]+1;j<=b[i];j++)

		{

			Qmin.push(a[j]);

			k=-Qmin.top();

			Qmin.pop();

			Qmax.push(k);

		}

		k=-Qmax.top();

		Qmax.pop();

		Qmin.push(k);

		printf("%d
",Qmin.top());

	}

	return 0;

}