题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6040
题意：不知道北航的同学为何解释题意之前都要想一段故事，导致刚开始题意不是很懂，题意就是给你n，m，A，B，C三个点，可以用以下这段代码生成n个随机数，赋值num[N],然后给你m个数，作为m次询问赋值给q[N]。然后问你第i次询问对于区间(0,n)这个区间中第q[i]+1小的数。
unsigned x = A, y = B, z = C;
unsigned rng61() {
unsigned t;
x ^= x << ;
x ^= x >> ;
x ^= x << ;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
思路：好吧……我是看了别人的代码，学习了这个线性求k大的姿势，就是用了一个STL的库函数nth_element(start,start+n,end);这个函数找的是[start,end)这个左闭右开区间内部第n+1大的数，感觉这个题就是为这个函数设计的。因为他是把拍完序以后应该在下标为n的位置的数归位，n左边的数比他小，右边的数比他大（不完全快排），这个题还有一个优化的地方，就是减少排序区间。我们先处理大的询问再处理小的询问。我举个例子，比如54321，现在我要求第5小的数，是5，处理完以后数组可能是43215，5是归位的但是其他数还是乱序的。然后我再在[0,4)这个区间内部去找第4小的数，和我原来要在[0,5)这个区间内部去找第四小的数结果是一样的。这样做的优点在于我们逐渐减少了，处理的区间加快了速度。这个题是个暴力题，如果没有这个优化是会超时的。
代码：
//Author: xiaowuga
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <bitset>
#include <cctype>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define mem(s,ch) memset(s,ch,sizeof(s))
#define da cout<<da<<endl
#define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl;
#define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl;
const long long N=1e7+;
using namespace std;
typedef long long LL;
unsigned x,y,z;
unsigned rng61() {
unsigned t;
x ^= x << ;
x ^= x >> ;
x ^= x << ;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
unsigned num[N];
unsigned ans[N],ca=;
pair<int,int>q[+];
int cmp(pair<int,int>a,pair<int,int>b){
return a.first<b.first;
}
int main() {
ios::sync_with_stdio(false);cin.tie();
unsigned n,m;
while(cin>>n>>m>>x>>y>>z){
for(int i=;i<n;i++) num[i]=rng61();
for(int i=;i<m;i++) {cin>>q[i].first;q[i].second=i;}
sort(q,q+m,cmp);//从小到大排序
q[m].first=n;
q[m].second=m;
for(int i=m-;i>=;i--){
//我们知道q[i+1].f是大于q[i].f的所以我们根据这个性质
//我们每次在[0,q[i+1].f)这个区间里面去找第q[i].f+1大的的数
//我们还需要知道nth_element这个函数是把第n+1大的数放在n的下标里面
nth_element(num,num+q[i].first,num+q[i+].first);
ans[q[i].second]=num[q[i].first];
}
cout<<"Case #"<<++ca<<":";
for(int i=;i<m;i++) cout<<" "<<ans[i];
cout<<endl;
}
return ;
}