题目链接：https://vjudge.net/problem/HDU-6040
题目大意：
给出 (n) 个数，有 (m) 次询问，每次询问这 (n) 个数中第 (k+1) 大的数是什么。
另有附加限制：对于 (n) 个数中的任意三个数 (a,b,c)，如果满足 (a ot= b, a < c, b < c)，则有 (a + b le c).
((1 le n le 10^{7}, 1 le m le 100))
解题思路：
由附加限制不难联想到斐波那契数列，由于 (F(36) = 14930352)，所以我们不难推测将这 (m) 次询问中去重后剩下的不同询问的个数是少于 (36) 的。
在此，还要再介绍一个优秀的函数：nth_element. 其用法是：nth_element((first, nth, last, compare))；作用是：将第 (n) 大的元素放在位置 (n)（从0开始），处理完之后，默认排在它前面的元素都不比它大，排在它后面的元素都不比它小。如果有定义 (compare()) 函数的话，大小关系则由 (compare()) 定义。时间复杂度是 (O(n)).
于是，一种优秀的做法是：将 (m) 个询问排序，去重，然后从大往小处理询问，用 nth_element() 求出区间第 (k) 大的数，并且将排在第 (k) 大的数后面的数都丢掉。
最后，这是第 (1000) 题。悄悄地，为自己鼓个掌 (XD)
AC代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long LL; 5 const LL MOD=1e9+7; 6 const int MAXN=1e7+5; 7 const int LIM=1e6; 8 9 unsigned x,y,z; 10 unsigned rng61() { 11 unsigned t; 12 x ^= x << 16; 13 x ^= x >> 5; 14 x ^= x << 1; 15 t = x; 16 x = y; 17 y = z; 18 z = t ^ x ^ y; 19 return z; 20 } 21 int add,n; 22 unsigned a[MAXN],ta[MAXN]; 23 struct ask{ 24 int ind,pos; 25 }b[110]; 26 bool cmp(const ask &x,const ask &y){ 27 return x.ind<y.ind; 28 } 29 unsigned ans[110]; 30 31 int main(){ 32 // freopen("in.txt","r",stdin); 33 int m,kase=1; 34 unsigned A,B,C; 35 while(scanf("%d%d%u%u%u",&n,&m,&A,&B,&C)==5){ 36 add=0; 37 x=A,y=B,z=C; 38 for(int i=0;i<n;i++) 39 a[i]=rng61(); 40 for(int i=0;i<m;i++){ 41 scanf("%d",&b[i].ind); 42 b[i].pos=i; 43 } 44 sort(b,b+m,cmp); 45 b[m].pos=m,b[m].ind=n; 46 47 for(int i=m-1;i>=0;i--){ 48 if(b[i].ind==b[i+1].ind) 49 ans[b[i].pos]=ans[b[i+1].pos]; 50 else{ 51 nth_element(a,a+b[i].ind,a+b[i+1].ind); 52 ans[b[i].pos]=a[b[i].ind]; 53 } 54 } 55 printf("Case #%d:",kase++); 56 for(int i=0;i<m;i++) printf(" %u",ans[i]); 57 printf(" "); 58 } 59 return 0; 60 }