洛谷 P3165 [CQOI2014]排序机械臂

  • 2018-10-10
  • 10
  • 1

Description:

为了把工厂中高低不等的物品按从低到高排好序,工程师发明了一种排序机械臂。它遵循一个简单的排序规则,第一次操作找到高度最低的物品的位置 P_1 ,并把左起第一个物品至 P_1 间的物品 (即区间 [1,P_1] 间的物品) 反序;第二次找到第二低的物品的位置 P_2 ,并把左起第二个至 P_2 间的物品 (即区间 [2,P_2] 间的物品) 反序……最终所有的物品都会被排好序。

上图给出有六个物品的示例,第一次操作前,高度最低的物品在位置 4 ,于是把第一至第四的物品反序;第二次操作前,第二低的物品在位罝六,于是把第二至六的物品反序……

你的任务便是编写一个程序,确定一个操作序列,即每次操作前第 i 低的物品所在位置 P_i ,以便机械臂工作。需要注意的是,如果有高度相同的物品,必须保证排序后它们的相对位置关系与初始时相同。

Input:

第一行包含正整数n,表示需要排序的物品数星。

第二行包含n个空格分隔的整数P_i,表示每个物品的高度。

Output:

输出一行包含n个空格分隔的整数Pi。

Sample Input:

6
3 4 5 1 6 2

Sample Output:

4 6 4 5 6 6

题目链接

将输入的物品高度结合其下标按照规则排序(之后物品高度就没用了),建立伸展树(Splay Tree)进行操作。

对于每一步操作直接把目标节点Splay到根节点,之后其左子树大小+1即为结果,第N步直接输出N即可。

AC代码:

评论