题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是Treap 你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存 用vector就很舒服 然后对于第三个操作,其实只要每次进入平衡树的元素查找下前驱后继与它本身作差取最小值即可(这里的前驱后继是非严格的) 对于第…

题目链接 题解 这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的 然后就用splay来写,发现思路自然了许多 引用自FlierKing 平衡树，需支持五个操作： 1. 将某元素置顶：将元素旋到根，然后将左子树合并到该元素的后继 2. 将某元素置底：将元素旋到根，然后将右子树合并到该元素的前驱 3. 将某元素提前/滞后1位：直接与该元…

题目链接 题解 这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果) 考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置 输入存在a数组里,按高度排序,每次我们就取出a[i].id,它的位置作为右边界,每次输出它的size 由于每次都单独地splay(a[i].id,rt) ,所以旋转的…