题解 P1801 【黑匣子_NOI导刊2010提高（06）】

看到这个题面，不断加入元素，每次查询第k大，我就立刻想到了平衡树……

然后又不会手码，于是想到了pbds的tree

然后就轻松的码出了30分的代码……

问了别人才知道原来有重复元素，而且pbds的tree是不能插入重复元素的

那么，我们怎么解决呢？

我想到了hash。

我们对每个元素维护一个二元组$\left(x,h\right)$，$x$表示元素本来的值，而$h$是我们通过hash搞出的一个唯一的随机值。

然后对每个u把没加进tree的元素加进去，然后直接利用tree求kth。

代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
struct User{
    int x,h;
    inline bool operator < (const User&p)const{return x!=p.x?x<p.x:h<p.h;}
}a[200005];//我们的二元组，注意，一定要满足单升，即：必须对任意两个元素的大小定义死
tree<User,null_type,less<User>,rb_tree_tag,tree_order_statistics_node_update> t;//定义一个pbds的红黑树
map<int,bool> mp;//判断一个hash值是否出现过了
int m,n,i,u[200005],last=1,hh;
inline int Hash(int x){
    while(mp[x])x=x+rand();
    return x;
}//对每个x生成一个唯一的值h
int main(){
	scanf("%d%d",&m,&n);
    for (int j=1;j<=m;j++){
        scanf("%d",&a[j].x);
        hh=Hash(a[j].x);
        a[j].h=hh,mp[hh]=1;
    }//读入的同时预处理好每个二元组
    for (int j=1;j<=n;j++)scanf("%d",&u[j]);//读入的u实际上已经拍好序了
    for (int j=1;j<=n;j++){
        for (;last<=u[j];last++)t.insert(a[last]);//插♂入
        printf("%d\n",(*t.find_by_order(i++)).x);//直接查kth，返回的是地址，我们要先取*再加.
        //注意！tree中查第k个元素实际上是find_by_order(k-1)
    }
}