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(很快)

05-26 07:00