BZOJ4104 [Thu Summer Camp 2015]解密运算

题面在这里

​

此题太妙了……

考虑给定的序列\(a_i\)，\(i\)表示 以\(a_i\)后面那个数为开头的后缀的排名

其实这是求后缀数组中用到的\(rank\)数组

如果我们知道 以\(a_i\)为开头的后缀的排名，就可以知道答案

考虑字符串是怎么排序的，先比第一位，再比下一位

也就是以\(a_i\)为第一关键字，\(i\)为第二关键字排序（考虑i的意义）

然后就好了

​

示例程序：

#include<cstdio>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
using namespace std;

const int maxn=200005;
int n,m;
pair<int,int> a[maxn];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=0;i<=n;i++) scanf("%d",&a[i].X),a[i].Y=i;
	sort(a,a+1+n);
	int t=a[0].Y;
	for (int i=1;i<=n;i++)
	 printf("%d ",a[t].X),t=a[t].Y;
	return 0;
}