【bzoj1552/3506】[Cerc2007]robotic sort

2014年9月10日3,5742

Description

Input

输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000。第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号。

Output

输出共一行,N个用空格隔开的正整数P1,P2,P3…Pn,(1 < = Pi < = N),Pi表示第i次操作前第i小的物品所在的位置。 注意:如果第i次操作前,第i小的物品己经在正确的位置Pi上,我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

题解

由于我比较逗,所以写法的常数也很大T T

就是用splay维护序列的最小值位置以及实现翻转

找到最小值的节点,转到根,它左子树的结点个数+1就是它在序列中的位置

 

  • debuggg2016年6月23日 下午8:11 回复

    fa不吉利,应该用gen

    #1