记录编号	173289	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2015-07-28 14:38:49	内存使用	0.43 MiB

#include<cstdio>
#include<cstdlib>
#include<ctime>

using namespace std;

struct Treap{
    int w,weight,fix,size;
    Treap *left,*right;
    Treap()
    {
        left=right=NULL;
    }
    inline int lsize(){return left ? left->size:0;}
    inline int rsize(){return right?right->size:0;}
};

Treap *root;
int n,m,a[31000],b,c;

void Treap_left(Treap *&a)
{
     Treap *d=a->right;
     a->right=d->left;
     d->left=a;
     a=d;
     d=a->left;
     d->size=d->lsize()+d->rsize()+d->weight;
     a->size=a->lsize()+a->rsize()+a->weight;
}

void Treap_right(Treap *&a)
{
     Treap *d=a->left;
     a->left=d->right;
     d->right=a;
     a=d;
     d=a->right;
     d->size=d->lsize()+d->rsize()+d->weight;
     a->size=a->lsize()+a->rsize()+a->weight;
}


void insert(Treap *&p,int value)
{
    if(p==NULL)
    {
        p=new Treap;
        p->weight=1;
        p->w=value;
        p->size=1;
        p->fix=rand();
        return;
    }
    else
        if(p->w==value)
        {
            p->weight++;
            p->size++;
            return;
        }
        else
            if(value<p->w)
            {
                insert(p->left,value);
                p->size++;
                if(p->left->fix<p->fix)
                    Treap_right(p);
            }
            else
            {
                insert(p->right,value);
                p->size++;
                if(p->right->fix<p->fix)
                    Treap_left(p);
            }
}

Treap *query(Treap *p,int k)
{
    if(k<p->lsize()+1)
        return query(p->left,k);
    else
        if(k>p->lsize()+p->weight)
            return query(p->right,k-p->lsize()-p->weight);
        else
            return p;
}

int main()
{
    freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
    srand((unsigned)time(NULL));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b);
        for(int j=c+1;j<=b;j++)
            insert(root,a[j]);
        printf("%d\n",query(root,i)->w);
        c=b;
    }
}