[CQOI2014]排序机械臂

题目链接

题解

这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果)

考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置

输入存在a数组里,按高度排序,每次我们就取出a[i].id,它的位置作为右边界,每次输出它的size

由于每次都单独地splay(a[i].id,rt) ,所以旋转的时候也要下放标记,其实以后都可以这样写,应该也不会T

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注