HDU 3436 Queue-jumpers (splay,离散化)

题目给出一个队列,里面有n个人(n <= 1e8)(编号1-n),三种操作:
1. TOP x,将人x放到队首;
2. Query x,询问人x所在的位置;
3. Rank x, 询问位置x的人;

首先将人都离散化,只需要存下询问出现过的人,这是单个人作为一块,接着讲相邻的两个人的中间那些人全部作为一块,块的大小就是人的数量,然后根据人的位置在splay上建树,维护区间人的个数sz,对于操作1只要将x删除在插入到最小数字的左边即可,对于操作2只需要将x splay到根答案等于sz[ch[rt][0]] + 1,对于操作3只需要在splay上分治找出第x大的人,由于存在人在一块人的区间内,所以需要稍微处理下,详细见代码。

 

LEAVE A COMMENT