COGS 2387.[HZOI 2016]2387题解

题目大意：

给定一个有n个元素的数组，有m个操作，分为两种，分别是询问第k个x的下标和把下标为x的数修改为k。

题目设置了强制在线，故无法预先得知所有操作数。

思路：

有三种思路。

第一种：平衡树

by std（也就是我）

为每一个数建一个平衡树，平衡树中储存的是这个数出现的每个下标，则询问操作对应名次树的查询k小数操作，单点修改直接维护一个数组记录每个位置上的值，把原来的数对应的下标从平衡树里删除，再把新数的平衡树中加入这个下标即可。

实现时开一个从int到平衡树的map，这样预处理复杂度O(nlogn)，查询和单点修改复杂度均为O(logn)，总复杂度即为O((m+n)logn)，满足题目需求。

std写的是AVL树，代码共249行。

第二种：线段树

by 溪哥（ymx）

为每一个数建一个动态开点线段树，节点存储的是对应区间中这个数出现的次数，那么查询操作对应的就是在线段树里寻找第k小的数出现的位置，单点修改对应的就是在原线段树中对应位置-1并在新线段树中对应位置+1。

实现时也是用map套动态开点线段树（因为节点太多，不用动态开点会爆内存），复杂度和平衡树法相同，满足题目需求。

溪哥的代码也就80行……

第三种：分块

by Aglove（ad）

这个就是暴力了，每个块中用什么东西（Aglove神犇用的是O(1)哈希表）记录每个数出现的次数，查询时暴力跳块，修改时直接修改并更新对应块即可。

预处理复杂度O(n)，查询操作O(sqrt(n))，单点修改复杂度O(1)，总的复杂度为O(n+m*sqrt(n))，对于200000的数据规模实在是悬，不过Aglove神犇卡了卡常就过了。

总之这题还是初级版，只增加了单点修改操作，至于区间修改、区间增量、区间查询第k个x等等更加复杂的操作还没有加入。

以后可能会出个加强版。

The End.

16.7.28 Thu.

巴特西