hdu 1890
题意:每次将第i位到第i小数字所在的位置之间的位置翻转,每次输出第i小数字所在的位置
分析:
简单的splay处理区间翻转问题
有三点需要注意:
1、区间是1~n+2
2、此题里的查找有两种,一种是知道点的编号,将这个点splay,还有一种是需要将第x位置的点splay(也就是splay里排名x的点),需要区分这两者
3、splay前需要先从root开始下放(这里针对此题的特殊查找,即知道点编号的情况,不能直接splay(index,0))
hdu 3436
题意:初始1~n(n<=1e8),然后有三个操作
TOP x:将数x拿到最前面
Query x:查找数x现在所在位置
Rank x:输出现在第x个位置的数
分析:
如果n是正常范围,那么就是个很简单的splay,1e8的话肯定是离散,那么怎么离散呢?
挑出所有TOP和Query操作的点,将两个点之间的区间缩点(记录下起点和长度保存下来)
那么对于所有操作,这些操作内部的顺序并不改变,并且Rank也能由此查到
PS:将Rank操作的点也离散是没有意义的,因为Rank x这个x并不是对应准确的点的编号,是变动的
hdu 3726(平衡树的启发式合并)
题意:对于一个给定的无向图,有三个操作
1、删除一条边
2、将一个点权值改掉
3、询问一个点所在的联通块中权值第k大的权值(包括自身)
分析:先离线
对于每个集合,维护一个平衡树,那么问题就涉及到两个平衡树的合并
容易想到让小的平衡树合并到大的平衡树上,可以证明这样复杂度是O(nlog^2n)的
对于splay,其实有更好的启发式合并,那就是对于小数所在的平衡树,先遍历一边得到顺序,再按照这样的顺序插入到大树中,可以证明这样启发式合并的复杂度是O(nlogn)的
这里的实现可以set(挺方便)、treap、splay(很快)