引入
支配对通常用来解决一类点对贡献问题。具体来说,任意两个对象构成一个点对,我们做一定范围内的信息查询时,就相当于查询范围内的点对的信息并。但是这样点对的数量是 \(\mathcal{O}(n^2)\) 量级的,无法接受。
支配对优化这类问题的思想,就是只保留有效点对,通常题目中有性质使得有贡献的点对量级会得到减小。
不应把支配对视作一个套路式的 trick,而应该把它视作一种思想。支配对的做法是及其灵活而富有技巧性的,需要仔细感受。
第一类支配对
\(\mathcal{O}(n^2)\) 个点对产生的本质不同的贡献只有 \(\mathcal{O}(n)\) 种。
常见的题目类型,就是在树上做编号区间内的信息查询,并且这个信息与 LCA 强相关。本质不同的点对只有 \(\mathcal{O}(n)\) 种,通常就是因为本质不同的 LCA 只有 \(\mathcal{O}(n)\) 个。
求出这类支配对的常见套路是做 DSU On Tree,在 LCA 处统计贡献,每次遍历轻子树内的点为其中一个点 \(u\),而其他子树内与 \(u\) 构成点对的若干个 \(v\) 只需要保留离 \(u\) 最近的那些。这样每次遍历轻子树时,一个点只会贡献 \(\mathcal{O}(1)\) 个点对,根据 DSU On Tree 的时间复杂度可以证明最终点对数量是 \(\mathcal{O}(n\log{n})\) 量级的。
P7880 [Ynoi2006] rldcot
给定 \(n\) 个点的树,边有边权,\(m\) 次询问 \(l,r\),求 \(\left\lvert\{dep_{\operatorname{lca}(i,j)}\mid l\leq i,j\leq r\}\right\rvert\)。\(1\leq n\leq 10^5\),\(1\leq m\leq 5\times 10^5\)。
把点对视作无序的,也就是钦定 \(i\leq j\),显然不影响答案。将 \(dep_{\operatorname{lca}(i,j)}\) 视作点对 \((i,j)\) 的颜色,那么询问 \(l,r\) 就是在 \(\text{4-side}\) 矩形数颜色。注意到我们实际上只需保证 \(i\geq l,j\leq r\),多出的部分必然不合法,所以实际上是 \(\text{2-side}\) 矩形数颜色。这是简单的,对 \(r\) 从小到大扫描线,对 \(\mathcal{O}(n)\) 种颜色离散化,每个颜色 \(c\) 维护其最大的出现下标 \(pos_c\),那么查询就转化成有多少颜色 \(c\) 满足 \(pos_c\geq l\),BIT 随便做。
于是我们可以轻松得到 \(\mathcal{O}(n^2\log{n})\) 的暴力,把 \(\mathcal{O}(n^2)\) 个点对全部扔进去扫描线即可。
考虑优化。思考对于同色点对 \((a,b),(c,d)\),若 \(a\leq c\leq d\leq b\),我们称 \((c,d)\) 支配了 \((a,b)\),也就是说 \((a,b)\) 必然是无用的点对。因为如果一个询问区间包含了 \((a,b)\) 就必然包含 \((c,d)\),我们只是在数颜色,所以保留 \((c,d)\) 就够了。
使用 DSU On Tree 找出所有支配点对。具体来说,考虑当前的根节点 \(x\),把它当作 LCA,每次进入轻子树遍历到一个点 \(u\) 时,设前面已经遍历过的子树构成的点的编号集合为 \(S\),对于形如 \((u,x)(x\in S)\) 的点对,我们只需保留 \(x\) 最小的那个,同理对于形如 \((x,u)(x\in S)\) 的点对,我们只需保留 \(x\) 最大的那个。用 set
维护集合 \(S\),那么就相当于查询 \(x\) 的前驱后继。显然每次进入轻子树遍历时每个点至多贡献 \(2\) 个点对,因此点对总数是 \(\mathcal{O}(n\log{n})\) 的。这部分时间复杂度为 \(\mathcal{O}(n\log^2{n})\)。
然后我们按照前文中的做法直接扫描线就行了。总体时间复杂度 \(\mathcal{O}(n\log^2{n}+m\log{m}+m\log{n})\)。
P8528 [Ynoi2003] 铃原露露
给定 \(n\) 个点的树,点有点权 \(a_i\),保证 \(a\) 是一个排列。\(m\) 次询问 \(l,r\),求有多少二元组 \((L,R)\) 满足 \(l\leq L\leq R\leq r\) 且 \(\forall L\leq a_x\leq a_y\leq R,L\leq a_{\operatorname{lca}(x,y)}\leq R\)。
对于每个点对 \((x,y)(a_x<a_y)\),令 \(z=\operatorname{lca}(x,y)\),分类讨论其会令哪些二元组 \((L,R)\) 不合法:
- \(a_z<a_x<a_y\):此时 \(a_z+1\leq L\leq a_x,a_y\leq R\leq n\) 的二元组 \((L,R)\) 变得不合法。
- \(a_x<a_z<a_y\):此时没有二元组会因为该点对变得不合法。
- \(a_x<a_y<a_z\):此时 \(1\leq L\leq a_x,a_y\leq R\leq a_z-1\) 的二元组 \((L,R)\) 变得不合法。
注意我们无需考虑 \(a_x=a_y\) 的情况,因为显然此时不会有二元组变得不合法。
把不合法的 \((L,R)\) 的范围放到平面上视作矩形,考虑降低矩形的数量。还是 DSU On Tree,在每次进入轻子树遍历到一个点 \(u\) 时,对于形如 \((x,u)\) 的点对,只需保留 \(a_x\) 最大的那个,因为右端点的限制是相同的,我们当然取左端点限制最松的那个,这样可以覆盖限制更紧地矩形。对于形如 \((u,x)\) 的点对同理。所以我们还是用 set
维护点集,遍历到一个点 \(u\) 的时候查询 \(a_u\) 的前驱后继即可。这样矩形个数就被降到了 \(\mathcal{O}(n\log{n})\) 级别。
接下来考虑如何统计答案。我们放到平面上考虑,每个不合法的矩形视作矩形 \(+1\),询问就相当于查询矩形内 \(0\) 个数。我们套路地把 \(\text{4-side}\) 矩形加查分成两次 \(\text{3-side}\) 矩形 \(\pm 1\),用线段树维护其中一维,支持区间加、区间查询历史 \(0\) 个数和。这是简单的,我们在节点上维护最小值、最小值个数,标记维护加法标记、历史和更新次数标记,每次 pushdown 或者在一个节点上给历史和标记 \(+1\),只在最小值为 \(0\) 上的节点操作即可。
\(n,m\) 同阶,时间复杂度 \(\mathcal{O}(n\log^2{n})\)。
P11364 [NOIP2024] 树上查询
给定 \(n\) 个点的树,\(q\) 次询问 \(l,r,k\),求
\[\max_{\substack{[l',r']\subseteq [l,r]\\r'-l'+1\geq k}}dep_{\operatorname{lca}[l',r']} \]其中 \(\operatorname{lca}[l,r]=\operatorname{lca}(l,\cdots,r)\)。\(1\leq n,q\leq 5\times 10^5\),\(1\leq k\leq r-l+1\)。
关于区间 LCA 有经典结论:
还是考虑有 \(\mathcal{O}(n^2)\) 个区间,如何降低区间个数。令 \(a_i=dep_{\operatorname{lca}(i,i+1)}\)。首先特判掉 \(n\) 个长度为 \(1\) 的 \([u,u]\) 区间。接下来考虑对 \(a\) 建出小根笛卡尔树,可以发现对于区间 \([l,r]\),其区间 LCA 就是 \(l,r\) 在笛卡尔树上的 LCA 对应的节点。在本题中,被包含的区间必然会被支配,所以对于笛卡尔树上的每个点,我们取其子树对应的下标范围作为支配区间是最优的。这样又会增加最多 \(n-1\) 个支配区间。于是我们就可以找出最多 \(2n-1\) 个支配区间了。
接下来问题转化成:有 \(\mathcal{O}(n)\) 个区间,区间有权值,每次询问区间 \([l,r]\) 和 \(k\),求所有和 \([l,r]\) 的交集长度 \(\geq k\) 的区间的权值最大值。
分类讨论产生贡献的区间 \([l',r']\) 和 \([l,r]\) 的关系。
首先 \(l'\leq l\leq r\leq r'\) 的区间一定产生贡献,这是很显然的二维偏序的形式,\(\text{2-side}\) 矩形最大值,容易用树状数组/线段树维护。
再来考虑 \(l\leq l'\) 的情况。首先,此时无论是 \(r'\leq r\) 还是 \(r\leq r'\),都需要满足 \(r'-l'+1\geq k\)。而若 \(l\leq l'\leq r\leq r'\),则还需要满足 \(r-l'+1\geq k\Leftrightarrow l'\leq r-k+1\),若 \(l\leq l'\leq r'\leq r\),则也有 \(r-l'+1\geq r'-l'+1\geq k\)。
因此,\(r'-l'+1\geq k\land l\leq l'\leq r-k+1\) 是这种 case 下 \([l',r']\) 有贡献的充要条件。
于是我们可以从大到小枚举 \(k\),把 \([l',r']\) 挂在 \(l'\) 上,每次询问 \([l,r]\) 时查询 \([l,r-k+1]\) 的区间 \(\max\) 即可。
还剩 \(l'\leq l\leq r'\leq r\) 的 case,也是容易维护的二维偏序的形式。
这样我们做三次扫描线即可统计答案。时间复杂度 \(\mathcal{O}((n+q)\log{n})\)。
第二类支配对
\(\mathcal{O}(n^2)\) 个点对中产生的本质不同的贡献同样有 \(\mathcal{O}(n^2)\) 种。
这类题通常是序列问题,在区间内查询对象两两产生贡献的 \(\min/\max\)。有两种常见的支配对形式:
- 对于每个右端点 \(r\),有 \(\mathcal{O}(\log)\) 个 \(l\) 可以和 \(r\) 构成支配点对,这 \(\mathcal{O}(\log)\) 个点对支配了所有的 \((1,r),(2,r),\cdots,(r-1,r)\) 点对。更具体地,我们通常考虑 \(i<j<k\),\((i,k)\) 是有效点对时应当同时支配 \((i,j),(j,k)\),把条件写出来,题目性质会使得每往左跳一个 \(l\),\(l\) 的相关范围会减半。
- 分治,设当前子问题规模为 \(n\),跨过分治中心的 \(\mathcal{O}(n)\) 个点对支配了所有跨过中点的 \(\mathcal{O}(n^2)\) 个点对。
CF765F Souvenirs
给定长度为 \(n\) 的序列 \(a\),\(m\) 次询问 \(l,r\),求 \(\min\limits_{l\leq i< j\leq r}|a_i-a_j|\)。\(2\leq n\leq 10^5\),\(1\leq m\leq 3\times 10^5\)。
看到绝对值自然想到分类讨论。接下来我们只考虑 \(j<i\land a_j\geq a_i\) 的点对 \((j,i)\) 的贡献。\(a_i>a_j\) 的部分把 \(a\) 反转再做一遍即可。
固定右端点 \(i\),考虑两个位置 \(j,k\),满足 \(i>j>k\)。若 \((k,i)\) 有贡献,则:
- \((k,i)\) 不能被 \((j,i)\) 支配,因此 \(a_k-a_i<a_j-a_i\Leftrightarrow a_k<a_j\)。
- \((k,i)\) 不能被 \((k,j)\) 支配,因此 \(a_k-a_i<a_j-a_k\Leftrightarrow a_k<\dfrac{a_i+a_j}{2}\)。
显然每次 \(a_k\) 的上界至少减半,因此对于每个右端点 \(i\),有贡献的左端点 \(j\) 只有 \(\mathcal{O}(\log{V})\) 个。需要支持找到最大的 \(j<i\) 使得 \(a_j\in[L,R]\),使用动态开点权值线段树容易 \(\mathcal{O}(\log{V})\) 跳到下一个合法的位置上,右端点从小到大扫的同时在线段树上单点修改即可。
最后就是一个唐诗 \(\text{2-side}\) 矩形内点权 \(\min\),容易用 BIT 维护。时间复杂度 \(\mathcal{O}(n\log^2V+m\log{m})\)。
CodeChef Minimum Xor On Segment
给定长度为 \(n\) 的序列 \(a\)。\(q\) 次询问 \(l,r\),求 \(\min\limits_{l\leq i<j\leq r}\{a_i\oplus a_j\}\)。\(2\leq n\leq 2\times 10^5\),\(1\leq q\leq 10^5\),\(0\leq a_i<2^{30}\)。
固定右端点 \(i\),考虑两个位置 \(j,k\),满足 \(i>j>k\),刻画 \((k,i)\) 有贡献的条件:\(a_k\oplus a_i<a_j\oplus a_i\) 且 \(a_k\oplus a_i<a_k\oplus a_j\)。
不妨考察 \(a_i,a_j,a_k\) 在二进制表示下的 LCP 的后一位。首先指出,\(a_i,a_j\) 必然在这一位上不同。
证明:考虑反证。假设 \(a_i,a_j\) 在这一位上相同,由 LCP 的极长性,必然有 \(a_k\) 在这一位上与 \(a_i,a_j\) 都不同。此时 \(a_k\oplus a_i\) 在这一位上为 \(1\),\(a_j\oplus a_i\) 在这一位上为 \(0\),说明 \((k,i)\) 被 \((j,i)\) 支配了,矛盾。\(\Box\)
其次,\(a_k\) 在这一位上必然与 \(a_i\) 相同,因为 \(a_k\oplus a_i\) 需要小于 \(a_k\oplus a_j\)。
注意到由于 \(a_i,a_j\) 在这一位上不同,所以这个 LCP 实际上也是 \(a_i,a_j\) 的 LCP。不难发现每次令 \(j\leftarrow k\) 时 LCP 至少拓展一位,因此每个右端点 \(i\) 对应的有贡献的左端点只有 \(\mathcal{O}(\log{V})\) 个。
对 \(a_k\) 的限制相当于值域上的一段连续区间,所以同样可以用动态开点值域线段树维护找支配点对的过程。找到这 \(\mathcal{O}(n\log{V})\) 个点对后和前面一题一样做个扫描线即可。时间复杂度 \(\mathcal{O}(n\log^2{V}+q\log{q})\)。
P9058 [Ynoi2004] rpmtdq / P9678 [ICPC 2022 Jinan R] Tree Distance
给定一棵 \(n\) 个点的有边权的无根树,\(q\) 次询问 \(l,r\),求 \(\min\limits_{l\leq i<j\leq r}\operatorname{dist}(i,j)\)。\(1\leq n\leq 2\times 10^5\),\(1\leq q\leq 10^6\)。
树上路径相关,考虑点分治。设当前分治中心为 \(r\),\(a_u=\operatorname{dist}(r,u)\)。考虑 \(i<j<k\),刻画 \((i,k)\) 有贡献的条件:首先 \((i,k)\) 不能被 \((i,j)\) 支配,因此 \(a_i+a_k<a_i+a_j\Leftrightarrow a_k<a_j\),同理考虑 \((j,k)\) 可以得到 \(a_i<a_j\)。由于对于每个 \(j\in[i+1,k-1]\) 都需要满足 \(a_i<a_j\land a_k<a_j\),因此容易得出 \((i,k)\) 有贡献的条件:\(\min\limits_{j=i+1}^{k-1}a_j>\max(a_i,a_k)\)。
注意一个细节,上面的推导中我们直接用 \(a_i+a_j\) 代替了 \(\operatorname{dist}(i,j)\),实际上若 \(i,j\) 位于 \(r\) 的同一个儿子的子树中,可能会有 \(a_i+a_j\geq \operatorname{dist}(i,j)\),但是这并不影响答案。我们无需担心 \((i,j)\) 因为 \(\operatorname{dist}\) 变大而被其他点对支配的问题,因为在之后的时刻,必然会存在新的分治中心 \(r'\) 使得 \(r'\) 在 \(i,j\) 的路径上,也就是使得 \(a_i+a_j\) 变得恰等于 \(\operatorname{dist}(i,j)\)。
考虑如何找出这些支配点对。不妨处理出当前层内所有节点的 \((p,a_p)\) 二元组,按照 \(p\) 排序。考虑支配点对 \((i,j)\),若 \(a_i\leq a_j\),则 \(i\) 相当于 \(j\) 前面最靠近 \(j\) 的满足 \(a_i\leq a_j\) 的位置,若 \(a_i>a_j\),则 \(j\) 相当于 \(i\) 后面最靠近 \(i\) 的满足 \(a_i>a_j\) 的位置,用单调栈扫一遍即可。设当前分治中心总节点个数为 \(n\),则每一层分治会找出 \(\mathcal{O}(n)\) 个支配点对,总共就有 \(\mathcal{O}(n\log{n})\) 个支配点对。
找出来之后还是直接扫描线即可。时间复杂度 \(\mathcal{O}(n\log^2{n}+q\log{q})\),瓶颈在于每一层对二元组进行排序。
P9062 [Ynoi2002] Adaptive Hsearch&Lsearch
给定 \(n\) 个二维平面上的点 \((x_i,y_i)\)。\(q\) 次询问 \(l,r\),求 \(\min\limits_{l\leq i<j\leq r}\operatorname{dist}(p_i,p_j)\)。\(2\leq n\leq 2.5\times 10^5\),\(1\leq q\leq 2.5\times 10^5\),\(1\leq x_i,y_i\leq 10^8\)。
回顾平面最近点对的期望线性做法:把所有点随机打乱,每次取当前答案 \(d\) 为边长,将平面划分为若干个 \(d\times d\) 的正方形块,枚举相邻的 \(3\times 3\) 的网格计算贡献,若答案更新则重构。
这启发我们考虑对平面网格化。考虑寻找合适量级的支配对来计算答案,初步想法是,取一个 \(d\),将平面划分为若干个 \(d\times d\) 的正方形块,依次加入每个点,枚举相邻的 \(3\times 3\) 的网格中的点加入支配对中。但是这样单个网格内点数可能会很多,从而使得支配对数量达到 \(\mathcal{O}(n^2)\) 级别。
因此考虑降低单个网格内的点数。我们智慧地考虑倍增,取底数 \(d\),设 \(V=\max\limits_{i=1}^n\{\max(x_i,y_i)\}\),枚举 \(0\leq k\leq\lceil\log_dV\rceil\),把平面划分为若干 \(d^k\times d^k\) 的正方形块,依次加入每个点 \(i\),枚举相邻的 \(3\times 3\) 的网格中的点加入支配对中,然后删去和点 \(i\) 距离 \(<d^{k-1}\) 的点。
为什么这样是对的呢?沿用支配对的思路,考察下标 \(i<j<k\),如果 \((i,k)\) 是有贡献的支配点对,那么对于每个 \(i<j<k\) 都会有 \(\operatorname{dist}(p_i,p_j)>\operatorname{dist}(p_i,p_k)\)。考虑最小的 \(x\) 使得 \(d^{x-1}<\operatorname{dist}(p_i,p_k)\leq d^x\),此时对于每个 \(i<j<k\) 都有 \(\operatorname{dist}(p_i,p_j)>d^{x-1}\),因此在倍增到 \(d^x\) 时,我们依次加入下标在 \([i+1,k-1]\) 中的点之后,\(p_i\) 必然不会被删除,同时因为 \(\operatorname{dist}(p_i,p_k)\leq d^x\),\(p_i,p_k\) 必然在相邻的网格中,所以在枚举 \(p_k\) 的相邻网格时,\((i,k)\) 一定会被加入支配点对中。
这里注意细节,枚举 \(k\) 时上界要取到 \(\lceil\log_dV\rceil\),因为要保证对于每个支配点对的 \(\operatorname{dist}\) 存在一个 \(d^x\) 使得这个 \(\operatorname{dist}\) 能被枚举到,如果 \(k\) 只取到 \(\lfloor \log_dV\rfloor\) 是有可能漏枚举一些支配点对的。
还有一个细节就是,\(k=0\) 时 \(d^{k-1}\) 应该定义为 \(1\),如果定义为 \(0\) 就会导致 \(n\) 个点重合时被卡成 \(\mathcal{O}(n^2)\)。
我们发现删去和当前点距离 \(<d^{k-1}\) 的点,可以保证每个网格中任意两点距离 \(\geq d^{k-1}\)。我们指出,这样每个网格中点的数量是 \(\mathcal{O}(d^2)\) 量级的。
证明:这里给出一个很粗略的上界,实际上界应当比这个上界更紧。
考虑用若干个半径为 \(\dfrac{d^{k-1}}{2}\) 的圆覆盖这个 \(d^k\times d^k\) 的正方形,满足圆之间不交,从面积的角度计算,那么显然圆的个数不超过\[\frac{d^k\times d^k}{\pi (\frac{d^{k-1}}{2})^2}=\frac{4d^2}{\pi}=\mathcal{O}(d^2)\quad\Box \]
于是每轮倍增每个点会贡献 \(\mathcal{O}(d^2)\) 个支配点对,因此总支配对个数是 \(\mathcal{O}(nd^2\log_d V)\) 级别的,可以接受。
找出点对后扫描线即可。由于点对个数较多,我们扫描线时用 \(\mathcal{O}(1)-\mathcal{O}(\sqrt{n})\) 分块平衡复杂度会更快,时间复杂度为 \(\mathcal{O}(nd^2\log_d V+q\sqrt{n})\)。我的实现下,取 \(d=2\) 跑得最快。
P8078 [WC2022] 秃子酋长 / P11367 [Ynoi2024] 魔法少女网站第二部
给定长度为 \(n\) 的排列 \(a\),\(m\) 次询问 \(l,r\),求 \(a[l,r]\) 中的元素排序后相邻的数在原序列中的位置的差的绝对值之和。弱化版 \(1\leq n,m\leq 5\times 10^5\),强化版 \(1\leq n,m\leq 2\times 10^6\)。
问题可以看作按照值从小到大的顺序走,求走的总步数。用链表支持 \(\mathcal{O}(1)\) 删除,套用回滚莫队即可轻松做到 \(\mathcal{O}(m\sqrt{n})\)。轻微卡常即可通过弱化版。
猫树分治,设当前分治区间为 \([l,r]\),分治中心为 \(mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor\),每次处理所有跨过 \(mid\) 的询问。我们尝试拆开 \([l,mid]\) 和 \([mid+1,r]\) 对询问的贡献。对于询问区间 \([x,y]\),考虑 \(a[x,mid]\) 中排序后相邻的两个元素 \(a_i,a_j\),可以发现:
- 若存在 \(k\in[mid+1,y]\) 使得 \(a_i<a_k<a_j\),则必定是从 \(a_i\) 开始走,跨过 \(mid\),在右区间走若干步后,跨过 \(mid\) 走回来到 \(a_j\),此时令 \((i,j)\) 的贡献为 \(-i-j\)。
- 否则令 \((i,j)\) 的贡献为 \(|i-j|\)。
右区间 \(a[mid+1,y]\) 的贡献是类似的,若左区间有夹在 \(a_i,a_j\) 中间的数,则贡献为 \(i+j\),否则为 \(|i-j|\)。
注意考虑边界情况,以左区间为例,考虑 \(a[x,mid]\) 中的最小值 \(a_i\),若存在 \(k\in[mid+1,y]\) 使得 \(a_k<a_i\),则 \(i\) 本身会有 \(-i\) 的贡献,否则贡献为 \(0\);同样要考虑最大值 \(a_j\),若存在 \(k\in[mid+1,y]\) 使得 \(a_j<a_k\),则 \(j\) 会有 \(-j\) 的贡献,否则贡献为 \(0\)。
我们发现这样设计贡献可以精准地刻画询问区间的答案。为什么呢?还是以左区间为例,考虑排序后相邻的两个元素 \(a_i,a_j\),设右区间中夹在 \(a_i,a_j\) 中间的数从小到大依次为 \(a_{p_1},a_{p_2},\cdots,a_{p_m}\),那么:
- 形如 \(|p_i-p_{i+1}|(1\leq i<m)\) 的贡献会在右区间中以 \(|i-j|\) 的形式被计算。
- 对于 \(p_1-i+p_m-j\),设 \(a_{p_0}\) 为 \(a_{p_1}\) 在 \(a[mid+1,y]\) 中的前驱,\(a_{p_{m+1}}\) 为 \(a_{p_m}\) 在 \(a[mid+1,y]\) 中的后继,那么在考虑 \((p_0,p_1)\) 和 \((p_m,p_{m+1})\) 的贡献是会把 \(p_1+p_m\) 算进去,而在考虑左区间中 \((i,j)\) 的贡献时也会把 \(-i-j\) 算进去。
接下来以左区间为例,考虑进一步刻画贡献条件。使用支配对思想,对于左区间中的一个相邻对 \((i,j)\),考虑右区间中最小的 \(k\) 使得 \(a_i<a_k<a_j\),不难发现贡献条件变成:若询问区间的右端点 \(y\geq k\) 则贡献为 \(-i-j\),否则贡献为 \(|i-j|\)。改写成更容易维护的形式,就是初始时就给 \((i,j)\) 赋上 \(|i-j|\) 的贡献,若 \(y\geq k\) 就会有 \(-|i-j|-i-j\) 的增量,那么我们只需要在询问时计算总的增量。
不难发现贡献条件是一维数点的形式,考虑对询问的左端点扫描线。如果对左端点从大到小扫描线,我们要支持插入数的同时动态维护前驱后继,需要使用 set
一类的数据结构维护前驱后继,会成为时间复杂度的瓶颈。
受根号做法的启发,我们倒着做,考虑对左端点从小到大扫描线,初始状态就是对 \(a[l,mid]\) 排序,然后使用双指针对每个相邻点对 \((i,j)\) 求出对应的 \(k\)。使用归并排序即可线性合并两个分治子区间对应的有序序列。删除一个数 \(a_i\) 时,考虑当前 \(a_i\) 的前驱后继 \(a_{prv},a_{nxt}\),我们要把点对 \((prv,i),(i,nxt)\) 合并成 \((prv,nxt)\)。注意到合并得到的 \((prv,nxt)\) 对应的 \(k\) 是容易计算的,其实就是 \((prv,i),(i,nxt)\) 对应的 \(k\) 取 \(\min\)。然后可以使用链表支持 \(\mathcal{O}(1)\) 删除/查询前驱后继,用 BIT 维护动态一维数点,每次删数时只会更改 \(\mathcal{O}(1)\) 个位置的增量。这样我们就可以 \(\mathcal{O}(\log{n})\) 回答一个询问,在每一层以 \(\mathcal{O}(n\log{n})\) 的代价做扫描线,整体时间复杂度是 \(\mathcal{O}(n\log^2{n}+m\log{n})\) 的。
注意到两边时间复杂度并不平衡,可以考虑多叉线段树。设分叉数为 \(t\),则修改复杂度是 \(\mathcal{O}(\log_t{n})\) 的,询问复杂度是 \(\mathcal{O}(t\log_t{n})\) 的,要做到平衡就需要 \(n\log{n}\log_t{n}=mt\log_t{n}\),\(n,m\) 同阶,因此解得 \(t=\log{n}\),得到更优的理论时间复杂度 \(\mathcal{O}\left(\dfrac{n\log^2{n}}{\log\log{n}}\right)\)。但是这个一脸常数很大的样子,感觉跑不过 BIT,我没写。
关于卡常,我 TLE 了一发之后就卡过去了。优化的地方是:不要使用同一个 BIT 维护左右的贡献,应当对于左区间开一个前缀 BIT,对于右区间开一个后缀 BIT,这样询问的时候就只会调用 query 一次,可以优化掉 \(\dfrac{1}{2}\) 的常数。