[BZOJ3506/Luogu3165][Cqoi2014]排序机械臂(平衡树)

发布于 2018-02-05  151 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3506/Luogu3165][Cqoi2014]排序机械臂(平衡树)

Description

为了把工厂中高低不等的物品按从低到高排好序,工程师发明了一种排序机械臂。它遵循一个简单的排序规则,第一次操作找到摄低的物品的位置P1,并把左起第一个至P1间的物品反序;第二次找到第二低的物品的位置P2,并把左起第二个至P2间的物品反序...最终所有的物品都会被排好序。
上图给出个示例,第次操作前,菝低的物品在位置4,于是把第1至4的物品反序;第二次操作前,第二低的物品在位罝6,于是把第2至6的物品反序...
你的任务便是编写一个程序,确定一个操作序列,即每次操作前第i低的物品所在位置Pi,以便机械臂工作。需要注意的是,如果有高度相同的物品,必须保证排序后它们的相对位置关系与初始时相同。

Http

BZOJ
Luogu

Tag

平衡树

解决思路

记录下位置后平衡树维护区间翻转即可。
调了好久才发现为了方便直接把找后继的代码在\(main\)里面展开了,结果没有下放标记。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3506/Luogu3165][Cqoi2014]排序机械臂(平衡树)


HNCJ OIer