用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:整体二分

这是本文档旧的修订版!


整体二分

算法简介

一种同时对所有询问进行二分答案的离线算法,时间复杂度一般为 $O(n\log n\log v)$。

算法例题

动态区间第 $k$ 小

题意

给定一个长度为 $n$ 的序列,支持两种操作:

  1. 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
  2. 将位置 $x$ 的数值修改为 $y$

题解

先考虑没有操作 $2$ 的情况。

可以二分答案 $mid$,使用树状数组维护序列前 $x$ 个位置中有多少个数不超过 $mid$,由此可以快速计算出每个询问区间中 $mid$ 的名次 $r$。

对每个询问 $i$,如果 $k_i\le r$,则说明询问 $i$ 答案在左区间,直接转移到左区间处理。

否则询问 $i$ 答案在右区间,于是将 $k_i$ 减去 $r$,转移到右区间处理。

显然不能二分过程中总是遍历整个序列,考虑转移询问的同时将序列的每个元素也转移到对应的区间。

具体的,如果元素 $v\le mid$,则转移到左区间,否则转移到右区间。

于是不考虑操作 $2$ 的情况下的问题已经得到解决。

接下来考虑如何处理操作 $2$,发现每个操作 $2$ 可以理解为删除和插入,而序列元素的初值可以考虑为直接插入。

于是考虑不是将每个序列元素转移,而是将每个修改操作转移,同时也用树状数组维护。

考虑到修改对查询会产生影响,于是需要注意维护时间序的相对不变性,具体见代码。

2020-2021/teams/legal_string/jxm2001/整体二分.1596094005.txt.gz · 最后更改: 2020/07/30 15:26 由 jxm2001