【题解】HDU6040 Hints of sd0061 线性选择，STL

10组数据，给定$n(1e7)$和$n$个数，有$m(100)$次询问，每次问第$b_i$小的数是谁。

数组随机生成，且保证如果三个询问位置的大小不同，那么最大的那个一定大于等于剩下两个的和。

---

从题目的数据保证里可以知道，给所有询问排序之后，每个询问要么和上一个询问相等，要么以$b_i\ge b_{i-1}+b_{i-2}$的形式增长.

可以证明，从第三个不相等的元素开始，$b_i\ge 1.5b_{i-1}$。

也就是说，$b_i\le b_{i+1}\ast 2/3$.

有了这样的性质之后，我们可以按询问从大到小依次线性选择，每个询问在前一次询问划分好的左侧数组内查找。

总复杂度：$O(n)+O(n\ast 2/3)+O(n\ast 4/9)+....=O(n)$

因为保证数据是随机生成的，所以线性选择的速度也会很优秀，总体常数很小。

基数排序大约5n的时间花费就挂了，然而线性选择就过了

---

介绍一个$stl$函数：$std::nth\_element$.

template <class RandomAccessIterator> void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp );

$stl$对其的介绍是

Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. . The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less. . The elements are compared using operator< for the first version, and comp for the second.

也就是对于$[first,last)$内的元素做一次排列，完成

$nth$位置的元素将与【整个范围排好序时】$nth$位置的元素相同$nth$左侧所有的元素不会比$nth$位置上的元素大$nth$右侧所有的元素不会比$nth$位置上的元素小

也就是找到某个排名的元素，并以其做一次划分，复杂度平均线性。

---

线性选择做法，1622ms通过

/* LittleFall : Hello! */ #include <bits/stdc++.h> using namespace std; using ll = long long; inline unsigned read(); const int M = 10000016, MOD = 1000000007; unsigned x, y, z; inline 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 save[M]; struct Query{ int id, pos, ans; }query[128]; int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif //double t_st = clock(); int n, m, kase = 0; while(scanf("%d %d",&n,&m)!=EOF) { x = read(), y = read(), z = read(); for(int i=0; i<n; ++i) save[i] = rng61(); for(int i=0; i<m; ++i) { query[i].id = i; query[i].pos = read(); } sort(query, query+m, [](Query a, Query b){ return a.pos < b.pos; }); query[m].pos = n; for(int i=m-1; i>=0; --i) { nth_element(save, save+query[i].pos, save+query[i+1].pos); query[i].ans = save[query[i].pos]; } sort(query, query+m, [](Query a, Query b){ return a.id < b.id; }); printf("Case #%d:",++kase ); for(int i=0; i<m; ++i) printf(" %u",query[i].ans ); printf("\n"); } //printf("%.2fs\n",(clock()-t_st)/CLOCKS_PER_SEC); return 0; } inline unsigned read(){ unsigned x=0;char ch=getchar(); while(ch<'0'||ch>'9') {ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }

基数排序做法，2500ms TLE

/* LittleFall : Hello! */ #include <bits/stdc++.h> using namespace std; using ll = long long; inline unsigned read(); const int M = 10000016, MOD = 1000000007; unsigned x, y, z; inline 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 save[M], xx[M]; // 排序a[1..n]，需要等长的辅助数组b void sort(unsigned *a, unsigned *b, register int n) { register unsigned i,*j,*lim,bac1[301]={0},bac2[301]={0},bac3[301]={0},bac4[301]={0},tmp; for(j=a+1,lim=a+n+1;j!=lim;++j)++bac1[(tmp=(*j))&255],++bac2[(tmp>>8)&255],++bac3[(tmp>>16)&255],++bac4[tmp>>24]; for(i=1;i<=255;++i)bac1[i]+=bac1[i-1],bac2[i]+=bac2[i-1],bac3[i]+=bac3[i-1],bac4[i]+=bac4[i-1]; for(j=a+n;j!=a;--j)b[bac1[(*j)&255]--]=*j; for(j=b+n;j!=b;--j)a[bac2[((*j)>>8)&255]--]=*j; for(j=a+n;j!=a;--j)b[bac3[((*j)>>16)&255]--]=*j; for(j=b+n;j!=b;--j)a[bac4[(*j)>>24]--]=*j; } int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif double t_st = clock(); int n, m, kase = 0; while(scanf("%d %d",&n,&m)!=EOF) { x = read(), y = read(), z = read(); for(int i=1; i<=n; ++i) save[i] = rng61(); sort(save, xx, n); printf("Case #%d:",++kase ); for(int i=1; i<=m; ++i) printf(" %u",save[read()+1] ); printf("\n"); } printf("%.2fs\n",(clock()-t_st)/CLOCKS_PER_SEC); return 0; } inline unsigned read(){ unsigned x=0;char ch=getchar(); while(ch<'0'||ch>'9') {ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }