【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6040
【题目大意】
给出一个随机数生成器，有m个询问，问第bi小的元素是啥
询问中对于bi<bk,bj<bk,有bi+bj<=bk
【题解】
(By Claris)对于所有的数字，我们将其按照高位分类，统计每个高16位有几个数字，
然后定位每个询问的高16位是什么，因为只有100个高16位是被询问到的，
把这100个高16位的数放入桶里，每次暴力查找，因为数据随机，
因此每个高16位期望n/65536=153个数，一共只有15300个数字有用
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
int T,n,m,k[200],pos[200];
unsigned s[10000010],b[10000010],x,y,z;
unsigned q[65536],cnt[65536],u[65536],tot[65536];
unsigned xorshf96(){
unsigned t;
x^=x<<16;
x^=x>>5;
x^=x<<1;
t=x; x=y; y=z;
z=t^x^y;
return z;
}
int getpos(int x){for(int i=0;;i++)if(tot[i]>=x)return i;}
unsigned query(int k,int p){
int i=p?tot[p-1]:0,m=0;
for(k-=++i;i<=tot[p];i++)q[m++]=b[i];
nth_element(q,q+k,q+m);
return q[k];
}
int Cas=1;
int main(){
while(~scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)){
for(int i=0;i<65536;i++)cnt[i]=u[i]=0;
for(int i=1;i<=n;i++){s[i]=xorshf96();cnt[s[i]>>16]++;}
for(int i=1;i<65536;i++)cnt[i]+=cnt[i-1];
for(int i=0;i<65535;i++)tot[i]=cnt[i];
for(int i=1;i<=m;i++){
scanf("%d",&k[i]);
pos[i]=getpos(++k[i]);
u[pos[i]]=1;
}for(int i=1;i<=n;i++)if(u[s[i]>>16])b[cnt[s[i]>>16]--]=s[i];
printf("Case #%d:",Cas++);
for(int i=1;i<=m;i++)printf(" %u",query(k[i],pos[i]));
puts("");
}return 0;
}