根据题意卡常数
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; int n,m; unsigned A,B,C; unsigned x,y,z; map <int,unsigned> M; unsigned rng61() {unsigned t;x ^= x << 16;x ^= x >> 5;x ^= x << 1;t = x;x = y;y = z;z = t ^ x ^ y;return z; } unsigned a[11234567]; struct querry {int id;int q;unsigned ans; }b[200]; bool cmpq(querry x,querry y) {return x.q > y.q; } bool cmpid(querry x,querry y) {return x.id < y.id; } int part(int low, int high) {swap(a[high],a[(low+high)/2]);unsigned pivot = a[high];while(low < high){while(low < high&&a[low] <= pivot) low++;a[high] = a[low];while(low < high&&a[high] >= pivot) high--;a[low] = a[high];}a[high]=pivot;return high; } unsigned quicksort(int l, int r, int k){int pos = part(l,r);if(pos == k) return a[pos];else if(pos > k) return quicksort(l,pos-1,k);else return quicksort(pos+1,r,k); } int main() {int cas = 0;while (~scanf("%d%d%u%u%u",&n,&m,&A,&B,&C)){M.clear();x = A, y = B, z = C;for (int i = 1; i<=n; i++){a[i] = rng61();}for (int i = 1; i<=m; i++){scanf("%d",&b[i].q);b[i].id = i;}sort(b+1,b+m+1,cmpq);int last = n;for (int i = 1; i <= m;i++){if (M.find(b[i].q+1)!=M.end()) b[i].ans = M[b[i].q+1];else b[i].ans = quicksort(1,last,b[i].q+1);M[b[i].q+1] = b[i].ans;last = b[i].q+1;}sort(b+1,b+m+1,cmpid);printf("Case #%d:",++cas);for (int i = 1; i<=m;i++)printf(" %u",b[i].ans) ;puts("");}return 0; }
从最大的取值到最小的取值依次使用近似线性复杂度的求第 kk 小的方法即可，该方法的思想与快排相似，可以保证前 k - 1k−1 小的元素都放置在第 kk 小元素的前面，这样枚举的时候就可以依次减少每次的枚举量。
http://bestcoder.hdu.edu.cn/blog/
