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

看到这个题面，不断加入元素，每次查询第k大，我就立刻想到了平衡树…… 然后又不会手码，于是想到了pbds的tree 然后就轻松的码出了30分的代码…… 问了别人才知道原来有重复元素，而且pbds的tree是不能插入重复元素的 那么，我们怎么解决呢？ 我想到了hash。 我们对每个元素维护一个二元组$\left(x,h\right)$，$x$表示元素本来的值，而$h$是我们通过hash搞出的一个唯一的随机值。 然后对每个u把没加进tree的元素加进去，然后直接利用tree求kth。 代码： ```cpp // 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) } } ```