浅谈离线分治算法

前言

分治算法,即“分而治之”,每次将当前的问题化成两个或更多相同或相似的子问题,再对每个分出的问题进行同样的操作…… 直到子问题足够地小,让我们能够方便地直接求解。归并排序便是分治算法的经典应用之一。

不过,在过去我们遇到的题目中,我们往往是对题目中所询问的数据进行分治的。那么,在允许离线算法的题目中,我们可以运用类似思想对操作和询问进行分治吗?

离线分治算法的主要思想就是把分治思想用在操作集上,而其在时间复杂度上的代价仅仅是多乘上一个 O(logn)\mathcal{O}(\log{n})。 本文将介绍两种类型的离线分治算法:

  • 基于数值的离线分治算法;
  • 基于时间的离线分治算法。

前者往往就是整体二分;而后者即为 CDQ 分治。

本文极大程度上参考了许昊然所著《浅谈数据结构题的几个非经典解法》一文以及李煜东所著《算法竞赛进阶指南(第二版)》一书(强烈安利),在此对包含两位作者在内的所有我在整理本文过程中所有参考过的文章(完整列表见文末)的作者表示衷心感谢。

基于数值的离线分治

这一算法又有一个更加广为人知的名字:整体二分

大家对于二分算法大概是非常熟悉的,但是我们接触到的传统的二分往往是针对单个询问进行二分。而整体二分则更进一步,对多个同类操作(包括修改和查询)一起二分答案,同时依据当前二分的判定值对当前操作集进行分类,再应用分治思想分而治之。而这一算法的经典应用即为区间第 kk 小。我们不妨以其作为例子来介绍整体二分。

静态区间第 k 小

例题

对于一个长度为 NN 的数列,现有 QQ 次询问。每次询问给出 l,r,kl, r, k,试求数列中下标在 [l,r][l, r] 中第 kk 小的数的数值。

数据范围

1N1051 \le N \le 10^5

1Q5×1031 \le Q \le 5 \times 10^3

题目链接

主席树裸题?

如果是对于单次查询,我们显然是可以先对区间进行预处理然后进行二分的。一种显而易见的思路就是将数值离散化然后开一个数组来记录每一个值在区间内出现的次数然后对前缀和进行二分。但是,当我们面对多个询问的时候,如果对每一个询问都进行预处理然后再二分,这样的复杂度显然是无法接受的。

不难发现对于每个询问其实预处理的过程都是大致相同的。那么我们是否可以对多个询问同时进行二分操作呢?

假设题目给定了由 nn 个询问组成的一个询问集合 QQ,并且我们知道所有出现过的数值的区间为 [l,r][l, r]。二分过程中,我们记 mid=12(l+r)mid = \frac{1}{2}(l+r)。在每一层递归中,我们首先对于 QQ 内每一个询问进行处理,求得该询问区间中数值在 [l,mid][l, mid] 范围内的值的个数 cntcnt。接下来,我们以此将 QQ 中的询问分为两类:cntkcnt \ge k 的以及 cnt<kcnt < k 的。我们用 Q1Q_1Q2Q_2 来表示这两类询问。

对于 Q1Q_1 中的询问,我们显然可以在 [l,mid][l, mid] 这一范围中求得答案。换句话说,[l,r][l, r] 中的第 kk 小即 [l,mid][l, mid] 中的第 kk 小;而对于 Q2Q_2 中的询问,我们便可以得知答案坐落于 (mid,r](mid, r] 这一范围中。显然,求 [l,r][l, r] 中的第 kk 小等价于求 (mid,r](mid, r] 中的第 kcntk - cnt 小(我们需要剔除 [l,mid)[l, mid) 中的数)。通过这种方式,我们可以把问题 QQ 拆分成 Q1Q_1Q2Q_2 两个子问题然后对它们进行分治并递归求解。递归结束于 l=rl = r,记此时的询问集为 QQ’,则 QQ’ 中的所有询问的答案即为 rr,便可以求解问题了。

我们最后需要解决的问题便是如何求得 cntcnt 了。我们可以考虑将原始数列中的数值离散化,然后用一个树状数组来维护这一信息。树状数组的第 ii 位表示数列中第 ii 位上的值是否坐落于 [l,mid][l, mid] 范围内,因此我们只需要在树状数组上求[L,R][L, R] 区间的区间和便可以得知下标 [L,R][L, R] 间有多少个数坐落于 [l,mid][l, mid] 范围内,即 cntcnt

具体实现时,我们可以在记录数列中每个数的原始下标后对数列按数值从小到大排序。我们可以通过二分搜索快速查找到 ll 的位置,接下来我们便可以轻松地对于 [l,mid][l, mid] 中的每个值更新树状数组中的信息。再求得 cntcnt 后我们再逐一撤销我们方才对树状数组进行的更改以为接下来递归中求 cntcnt 做准备。需要注意的是,撤销更改时不可以直接用 memset,若是如此每一次预处理就与原数组长度有关而并非与当前二分区间有关了,而这会导致复杂度的变化(下面会给出详细说明)。显然,这一过程复杂度是 O(mlogn)\mathcal{O}(m\log{n}) 的,其中 mm 是当前二分区间的长度。总的复杂度是 O(nlog2n)\mathcal{O}(n\log^2{n}) 级别的(下面也会给出详细说明)。

完整参考代码

复杂度分析

至于复杂度,这里引用《浅谈数据结构题的几个非经典解法》一文中的相关证明:

定义 T(C,S)T(C, S) 表示当前待二分区间长度为 CC,待二分序列长度为 SS,且记对于长度为 mm 的序列单次处理复杂度为 O(f(m))\mathcal{O}(f(m)),则在 O(f(n))n\mathcal{O}(f(n)) \ge n 的前提下有:

T(C,S)=T(C2,S)+T(C2,SS)+O(f(S))T(C, S) = T(\frac{C}{2}, S’) + T(\frac{C}{2}, S - S’) + \mathcal{O}(f(S))

解得:

T(C,S)O(f(n)logn)T(C, S) \le \mathcal{O}(f(n)\log{n})

而如果每一次处理的复杂度都与序列长度 nn 有关,则有:

T(C,S)=T(C2,S)+T(C2,SS)+O(n)T(C, S) = T(\frac{C}{2}, S’) + T(\frac{C}{2}, S - S’) + \mathcal{O}(n)

解得:

T(C,S)=O(nS)T(C, S) = \mathcal{O}(nS)

不难发现,这样一来实际上复杂度就变得与暴力没什么区别了……

那么对于这一例题中我们的做法,我们先对数值进行排序,然后在二分查找过程中我们每次直接通过二分查找来确定端点位置,其复杂的是 O(mlogm)\mathcal{O(m\log{m})} 的,其中 mm 为当前处理区间长度。总的复杂度即 O((n+Q)lognlogC)\mathcal{O}((n + Q) \log{n}\log{C}),在该题数据范围下就是 O(nlog2n)\mathcal{O}(n\log^2{n}) 级别的。


由上面的例子,我们可以初步窥见整体二分适用的问题范围。首先最基本的是,询问的答案必须具有可二分性,并且题目允许离线算法。

其次,我们注意到在上例中二分时我们每一次预处理只与当前区间长度有关。这是因为其余部分对答案的贡献是固定的。具体地阐述,假设我们计算某询问区间内的第 kk 大时,假设该区间内数值的范围为 [L,R][L, R],当我们正在二分数值区间 [l,r][l, r] 时,[l,r][l, r] 以外的数值区间(即 [L,l)[L, l)(r,R](r, R])对答案的贡献是固定不变的(询问区间内数值在这些区间内的数的个数固定),因此我们没有必要去重复计算那两个区间对答案的贡献,直接加上即可。由此,贡献也应当是可加的,并且满足交换律和结合律。

那么,如果我们需要支持的操作不仅仅有询问,同时还要有修改呢?事实上,只要加入修改操作后我们依然能够做到二分时每一次预处理只与当前区间长度有关,我们就可以继续使用整体二分。

动态区间第 k 小

例题

对于一个长度为 NN 的数列,现有两类共 QQ 次操作:

  • 将第 ii 个数的值修改为 vv
  • 询问第 ll 个数和第 rr 个数之间第 kk 小的数值。

数据范围

1N5×1041 \le N \le 5 \times 10^4

1Q1041 \le Q \le 10^4

题目链接

分析与实现

本题与上一例唯一的区别便在于新加入了修改操作,这样一来上例中的询问集 QQ 在本题中就变成可以含有询问即修改两种操作的操作集了。我们不妨把每个修改操作拆成两步:先删除该位置上原值,再在该位置上插入新值。同时,序列的初始化也可看作 nn 次在位置 ii 插入新值。

我们注意到每一次修改操作其实对答案的贡献是独立的。具体地说,假设二分过程中当前某区间值域为 [L,R][L, R],当前二分区间为 [l,r][l, r]。我们若是将该区间内某位置上的值由 aia_i 改变为 ai (lair)a_i’ \ (l \le a_i’ \le r) ,并不会改变 [l,r][l, r] 以外的区间(即 [L,l)[L, l)(r,R](r, R] 这两个区间对答案的贡献。 由此,每一次预处理的复杂度依然仅仅是与当前二分区间有关的,可以使用整体二分。

故我们依然采用与上例类似的思路对所有操作进行二分。不同之处在于,由于修改这一操作的引入,我们不能随意改变操作的顺序。因此,区别仅仅在于求 cntcnt 这一过程的实现。我们不能再像之前一样先对值排序然后二分,因为那样会改变操作的顺序。对于 QQ 内的操作,我们必须按照原顺序进行遍历,查询和修改同时进行(若操作为修改,只应用值在 [l,mid][l, mid] 区间之内的)。另外在将 QQ 分类为 Q1Q_1Q2Q_2 时也要单独开两个单独的空间来进行分类以防止改变操作之间的顺序。

完整参考代码

小结

整体二分是一种应用于允许离线具有多组询问且具有二分性问题的一种算法,其思想即将多组操作一起二分从而减小复杂度。精炼地说,整体二分实际上就是二分 + 分治二分是对于答案值的二分,而分治则是对于操作集的分治,从而达到对多个同类询问一起进行二分求解的效果。这其中最关键的地方是,我们必须确保二分过程中每一次预处理的复杂度应与当前二分区间的长度区间有关,而绝对不能与整个序列长度有关。如果我们记预处理的复杂度为 O(f(n))\mathcal{O}(f(n)),则整体二分的复杂度为 O(f(n)logn)\mathcal{O}(f(n)\log{n})


我们可以看出上述算法在对操作集进行分治时,是基于数值分治的。而这一数值,实际上就是二分过程中的判定值 midmid。如果问题不具有可二分性,使得我们难以基于数值对操作集进行分治,我们是否可以找其他基准对操作集进行分治呢?

基于时间的离线分治

对于数据结构题,我们在回答每一个询问时,其本质就是计算初始数据和本次询问之前进行的所有修改对该询问造成的影响。如果题目允许离线算法,我们就可以预先知道所有操作组成的操作序列 QQ,那么我们是否可以运用与上文类似的思想对操作序列 QQ 进行分治呢?

P.S. 其实这就是 CDQ 分治

基本思想

假设共有 nn 项操作,我们定义函数 solve(l,r)solve(l, r),其功能为:k[l,r]\forall k \in [l, r],若第 kk 项操作为询问,则计算第 [l,k1][l, k - 1] 项操作对当前询问造成的影响。我们考虑采用如下方法进行计算:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归计算 solve(l,mid)solve(l, mid)
  3. 递归计算 solve(mid+1,r)solve(mid + 1, r)
  4. 计算第 [l,mid][l, mid] 项操作中所有的修改对第 [mid+1,r][mid + 1, r] 项操作中所有询问造成的影响。

在更多情况下,这里的修改并不指数据上的修改,而是元素之间的贡献关系。比如在经典的多维偏序问题或者其它计数类问题中,我们可以把 solve(l,r)solve(l, r) 定义为:k[l,r]\forall k \in [l, r],计算第 [l,k1][l, k - 1] 项元素对第 kk 项元素的贡献(或者说,造成的影响)。例如在三维偏序问题中,我们就可以将其理解为:k[l,r]\forall k \in [l, r],计算第 [l,k1][l, k - 1] 项元素中所有维度都小于第 kk 项元素对应维度的元素个数。

递归开始于 solve(1,n)solve(1, n),且递归结束于 l=rl = r 时(此时只有一项操作)。下面引用《算法竞赛进阶指南(第二版)》一书中对其正确性的简要证明:

设第 kk 项操作是询问,那么:

  • kmidk \le mid,则 solve(l,mid)solve(l, mid) 已经计算了第 l(k1)l \sim (k - 1) 项操作中所有修改对当前询问的影响;
  • k>midk > mid,则 solve(mid+1,r)solve(mid + 1, r) 已经计算了第 (mid+1)(k1)(mid + 1) \sim (k - 1) 项操作中所有修改对当前询问操作的影响。只要这一影响满足可加性且满足交换律,并且不同修改操作造成的影响互相独立,那么直接加上最后一项计算就可以得到第 l(k1)l \sim (k - 1) 项操作中所有修改对当前询问的影响。

这样做的好处是什么呢?我们发现,当我们在进行第 44 部分的计算时,我们其实是在解决一个静态问题。因此这一递归实质上可以把一个带有 nn 次操作的动态问题转换为解决 O(n)\mathcal{O}(n) 个静态问题,而原始问题中每个询问的结果是由 O(logn)\mathcal{O}(\log{n}) 个静态问题的结果共同组成的。一般来说,解决静态问题会比解决动态问题方便很多。与前面整体二分所类似地,只要我们能在只与 rlr - l (当前递归区间长度)有关,而与 nn 或者整个序列的长度无关的时间复杂度内解决 solve(l,r)solve(l, r),那么我们就可以用 O(f(n)logn)\mathcal{O}(f(n)\log{n}) 级别的复杂度内解决整个动态问题,其中 O(f(n))\mathcal{O}(f(n)) 是解决长度为 nn 的递归区间所需的复杂度。


偏序问题

CDQ 分治比较经典的应用就是偏序问题,因为事实上很多数据结构问题都可以在某种程度上被我们归结为偏序问题,接下来我们不妨从最简单的偏序问题看起。

二维偏序

概要

给定 nn 个二元组 pi=ai,bip_i =\langle a_i, b_i \rangle,并且满足 i,j\forall i, j,均不存在 pi=ai,bi, pj=aj,bjp_i = \langle a_i, b_i \rangle, \ p_j = \langle a_j, b_j \rangle 使得 ai=aja_i = a_jbi=bjb_i = b_j。对于每一个元素 pip_i,求满足 aj<ai, bj<bia_j < a_i, \ b_j < b_ipjp_j 的个数。

不难发现,其实统计逆序对个数就是这类问题的一个变种(下标看作第一维,值看作第二维)。

我们首先来谈谈归并排序的求解方法,因为用归并排序求解此问题的过程完整地体现了 CDQ 分治的思想。对于所有二元组我们首先以 aa 这一维度从小到大排序。其次我们进行归并排序 mergesort(l,r)mergesort(l, r),其作用定义为:k[l,r]\forall k \in [l, r],计算第 [l,k1][l, k - 1] 项元素对第 kk 项元素造成的贡献,并且对序列按照 bb 这一维度排序。下面简要描述其过程:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归计算 mergesort(l,mid)mergesort(l, mid);
  3. 递归计算 mergesort(mid+1,r)mergesort(mid + 1, r)
  4. 计算左区间中元素对右区间中每个元素造成的贡献,同时合并两个有序区间。

而我们统计答案的过程也是在第 44 步完成的。由于之前已经按照 aa 这一维排过序了,我们可以确保左区间中元素的 aa 维度一定是小于右区间中元素 aa 维度的。依据分治思想,此时我们只需要考虑左区间中的元素对右区间中每个元素造成的贡献。另外,此时左区间和右区间都已经完成递归计算,所以它们都是按 bb 这一维度按升序排好了序的,因此我们完全可以使用双指针来简便地计算贡献。不难看出,我们实际上是对原问题降了一维,所以第 44 步中我们只需要考虑 bb 这一维的偏序情况。同时我们也注意到,第 44 步处理的复杂度实际上是与分治区间长度相关而不是与 nn 相关的。基于这一特性,我们才可以得到 O(nlogn)\mathcal{O}(n\log n) 的复杂度,因此实现时一定要注意第 44 步复杂度不可与 nn 相关。


另外这里我也简要介绍一种利用树状数组的解法。

我们可以让树状数组中的第 ii 位来表示第二维为 ii 的数当前出现的次数。这样一来,我们可以对给定的数对首先按照第一维从小到大排序,并且有序地将它们的第二维插入树状数组。与此同时,询问树状数组中值比当前元素第二维小的数的个数就可以了。这样的复杂度也是 O(nlogn)\mathcal{O}(n\log{n}) 的。

那么对于三维乃至更高维的偏序问题呢?我们可以用二维树状数组!虽说如此,但是当 nn 达到 10510^5 的时候会爆内存的…… 因此,我们可以来考虑借助离线分治算法进行降维。由于分治套分治会存在顺序上的一些坑(不是不能写,就是容易挂),因此更多时候我们是采用基于时间的离线分治来降低数据结构维度(比如避免多维数据结构以及树套树) 。

三维偏序问题

概要

给定 nn 个三元组 pi=ai,bi,cip_i =\langle a_i, b_i, c_i \rangle,并且满足 i,j\forall i, j,均不存在 pi=ai,bi,ci, pj=aj,bj,cjp_i = \langle a_i, b_i, c_i \rangle, \ p_j = \langle a_j, b_j, c_j \rangle 使得 ai=aja_i = a_jbi=bjb_i = b_jci=cjc_i = c_j。对于每一个元素 pip_i,求满足 aj<ai, bj<bi, cj<cia_j < a_i, \ b_j < b_i, \ c_j < c_ipjp_j 的个数。

类似地,我们也首先对所有三元组按照 aa 这一维度从小到大排序。我们定义 solve(l,r)solve(l, r) 的作用: k[l,r]\forall k \in [l, r],计算第 [l,k1][l, k - 1] 项元素对第 kk 项元素造成的贡献,同时对原序列按照 bb 这一维度排序。下面简要描述其过程:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归计算 solve(l,mid)solve(l, mid)
  3. 递归计算 solve(mid+1,r)solve(mid + 1, r)
  4. 计算左区间中元素对右区间中每个元素造成的贡献,同时合并左右两个有序区间。

接下来我们来看看第 44 步我们面临的情景。此时,左区间中所有元素的 aa 维度一定是小于右区间中元素的 aa 维度的。而由于已经递归计算过了左右区间,因此左右区间都是按照 bb 维度升序排好序的。因此,当我们再计算左区间元素对有区间内每个元素造成的贡献时,我们不难发现,我们面临的实际上就是上面所提到的二维偏序的情境:我们只需要考虑 b,cb, c 这两维的偏序情况,并且序列还已经按照 bb 排好序了。

当然此时我们可以选择再套一层归并排序,不过更简便一点的方式便是采用上文所述的利用树状数组的解法来解决当前面对的二维偏序问题。我们首先可以利用双指针解决 bb 维度的偏序关系(正如二维偏序归并排序解法中的那样),与此同时把 cc 维度按值放进树状数组维护(正如上文提到的二维偏序树状数组解法那样),就可以解决这一问题了。总的复杂度为 O(nlog2n)\mathcal{O}(n\log^2 n)

例题

nn 个元素,第 ii 个元素有 ai,bi,cia_i, b_i, c_i 三个属性。设 f(i)f(i) 表示满足 ajai, bjbi, cjci, ija_j \le a_i, \ b_j \le b_i, \ c_j \le c_i, \ i \neq jjj 的数量。

对于 d(0,n]d \in (0, n],求 f(i)=df(i) = d 的数量。

数据范围

1n1051 \le n \le 10^5

1ai,bi,ci2×1051 \le a_i, b_i, c_i \le 2 \times 10^5

题目链接

很明显是一个裸的三维偏序问题。唯一需要注意的是,题目所要求的是小于等于而非严格小于,且不保证三元组互不相同。因此需要事先去重

为什么要去重?前面算法正确的一个前提是,在分治的第 44 步时,只需要考虑左区间对右区间的贡献。而如果题目要求的是小于等于的话,就会出现左区间也可对右区间产生贡献的情况,而我们难以对此进行计算。因此。提前去重从而把问题转化为严格小于的问题不失为一个简单的解决方案。

完整参考代码


对于更高维的偏序问题该如何解决呢?既然泥萌都会树套树,我们这里也可以 CDQ 分治套 CDQ 分治啊~ 但是这样一来,对于 kk 维偏序问题,复杂度就变成了 O(nlogk1n)\mathcal{O}(n\log^{k - 1}n) 了。所以当 kk 比较大的时候还是去学 KD 树吧(然而我不会 QAQ)。不过,如果 kk 特别大,那还不如暴力 O(kn2)\mathcal{O}(kn^2) (逃…

四维偏序问题

概要

给定 nn 个四元组 pi=ai,bi,ci,dip_i =\langle a_i, b_i, c_i, d_i \rangle,并且满足 i,j\forall i, j,均不存在 pi=ai,bi,ci,di,pj=aj,bj,cj,djp_i = \langle a_i, b_i, c_i, d_i \rangle, p_j = \langle a_j, b_j, c_j, d_j \rangle 使得 ai=aja_i = a_jbi=bjb_i = b_jci=cjc_i = c_jdi=djd_i = d_j。对于每一个元素 pip_i,求满足 aj<ai, bj<bi, cj<ci, dj<dia_j < a_i, \ b_j < b_i, \ c_j < c_i, \ d_j < d_ipjp_j 的个数。

我们大体的思路就是先用第一层 CDQ 分治把问题降维成三维偏序问题,再用第二层 CDQ 分治把问题降维成二维偏序问题,最后再借用树状数组解决之。由于 CDQ 分治套 CDQ 分治虽然看起来很显然,但是写起来还是有很多细节需要注意,所以下面还是进一步讲解一下。

我们定义第一层 CDQ 分治中 solve(l,r)solve(l, r) 的作用: k[l,r]\forall k \in [l, r],计算第 [l,k1][l, k - 1] 项元素对第 kk 项元素造成的贡献,同时对原序列按照 bb 这一维度排序。下面简要描述其过程:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归计算 solve(l,mid)solve(l, mid)
  3. 递归计算 solve(mid+1,r)solve(mid + 1, r)
  4. 标记每个元素属于左区间还是右区间,再合并两个有序区间,然后调用第二层 CDQ 分治解决降维后的问题。

在第 44 步时,我们刚开始时依然面临的是分别按照 bb 维度排好序的左右区间。然而下一层 CDQ 分治又会按照 cc 维度对序列进行排序使得 bb 这一维度的信息丢失,因此我们需要先对当前分治区间内的元素标记其属于作左区间还是右区间,这样在第二层 CDQ 分治中的处理才可以只处理两层分治都在左区间中的元素对所有两层分治中都在右区间中的元素的贡献。另外,由于第二层 CDQ 分治会改变序列的顺序,因此在调用之前我们需要备份一下合并完有序区间后的当前区间,并在调用完第二层 CDQ 分治后将其恢复回来,以保证正确性。

例题

给定一个有 nn 个元素的序列,元素编号为 1n1 \sim n,每个元素有三个属性 a,b,ca, b, c,求序列中满足 i<j,ai<aj,bi<bj,ci<cji < j, a_i < a_j, b_i < b_j, c_i < c_j 的数对 i,j\langle i, j \rangle 的个数。

数据范围

1n5×1041 \le n \le 5 \times 10^4

题目链接

四维偏序模板题…… 这里就直接上代码了~

完整参考代码


动态二维数点问题

概要

给定二维平面上 nn 个点 (xi,yi)(x_i, y_i),并且需要支持两种操作:

  1. 修改平面上的某个点的坐标;
  2. 询问一个矩形区域 (xL,yL),(xR,yR)(x_L, y_L), (x_R, y_R) 内点的数量(xLxR,yLyRx_L \le x_R, y_L \le y_R)。

这就是动态二维数点问题。但本质上,我们可以把询问给表述成:求满足 xLxixRx_L \le x_i \le x_RyLyiyRy_L \le y_i \le y_R(xL,yR)(x_L, y_R) 个数。因此我们可以把它归纳为动态二维偏序问题。对于动态问题,由于修改和询问间的先后顺序不能随便改变,也我们需要新引入了时间这一维度(记之为 timetime)。

我们首先来考虑如何处理询问操作。在 CDQ 分治的第四步,我们能保证左区间的 timetime 这一维一定是小于右区间的。之前处理偏序问题时,问题只对两个维度规定了上界限而并没有规定下界限。而在本题中,下界限的引入让问题似乎变得难以在与区间长度线性相关的复杂度内解决。不过没关系,我们可以考虑利用容斥原理来把问题转换为只有上界限的询问。

a(x,y)a(x, y) 为坐标为 (x,y)(x, y) 的点的个数,并且记 P(x,y)P(x, y) 为其二维前缀和,即:

P(x,y)=i=1xj=1ya(x,y)P(x, y) = \sum\limits_{i = 1}^{x}\sum\limits_{j = 1}^{y}a(x, y)

那么根据容斥原理,题目中的询问操作 Q(xL,yL,xR,yR)Q(x_L, y_L, x_R, y_R) 可以表示为:

Q(xL,yL,xR,yR)=P(xR,yR)+P(xL1,yL1)P(xL1,yR)P(xR,yL1)Q(x_L, y_L, x_R, y_R) = P(x_R, y_R) + P(x_L - 1, y_L - 1) - P(x_L - 1, y_R) - P(x_R, y_L - 1)

也就是说,我们可以把每个询问拆分成只包含上界限的四个询问,而询问有两种:对最终答案产生正贡献的,和对最终答案产生负贡献的。

对于修改,我们也可以考虑把它拆分成插入和删除两步。比如,若要将 (x,y)(x, y) 修改为 (x,y)(x’, y’),那么我们先删除 (x,y)(x, y),也就是在 (x,y)(x, y) 这个位置上增加 1-1 的贡献(在此之后所有包含该点的询问都受到 1-1 的影响),接着再插入 (x,y)(x’, y’),也就是在 (x,y)(x’, y’) 这个位置上增加 +1+1 的贡献。

例题

给定一个长度为 nn 的序列,共 qq 次操作。需要支持两种操作:

  1. 把位置 ii 上的数修改为 vv(从 11 开始编号);
  2. 询问区间 [L,R][L, R] 内不同的数有多少种。

数据范围

1n,q5×1041 \le n, q \le 5 \times 10^4 (还可以再加强~)

1v1061 \le v \le 10^6

题目链接

这道题的数据范围其实是允许带修改莫队做的,但是如果再加强到 10510^5 级别,可能就只能考虑树套树或者 CDQ 分治了。

我们记 pre(i)pre(i) 代表在位置 ii 左边与它最近的数值相同的数的位置,那么对于区间 [L,R][L, R] 内有多少数值不同的数就可以转变为询问有多少 i[L,R]i \in [L, R] 且满足 pre(i)<Lpre(i) < L。这样一来,我们可以把 i,pre(i)\langle i, pre(i) \rangle 看成一个二维平面上的点,而询问则是询问满足 LiR,0pre(i)L1L \le i \le R, 0 \le pre(i) \le L - 1i,pre(i)\langle i, pre(i) \rangle 个数,也就是矩形 (L,0),(R,L1)(L, 0), (R, L - 1) 内点的个数。

而对于 ii 点上的修改操作(假设值由 vv 被修改为 vv’),只会对至多三个点造成影响:

  1. 满足 pre(j)=ipre(j) = i 的位置 jj,其 prepre 会被修改为 pre(j)=pre(i)pre(j) = pre(i)
  2. 位置 iiprepre 会被修改为其左边与它最近且数值为 vv’ 的位置;
  3. 位置 ii 右边最近的数值为 vv’ 的位置 kkprepre 会被修改为 pre(k)=ipre(k) = i

我们完全可以对每一个数值开一个 set 来快速查找需要被修改的点。于是这道题就被转化成了二维动态数点问题~

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2019/01/28/offline-divide-and-conquer/