区间操作问题

Published: by Creative Commons Licence

  • Tags:

sparse-table算法

区间最值

st算法可以用于计算区间最值,不同于其它区间最值查询算法,st算法单次查询的时间复杂度仅为$O(1)$。下面讲解st算法。

假设区间的范围为$[0,n]$。我们首先定义函数$f(i,j)$表示区间$[i,i+2^j)$的最小值。很显然我们可以给出递推公式:

对于$i$,共有$0$到$n$总选择,而对于$j$,共有$0$到$\lfloor \log_2n \rfloor$种选择。总计对$f$的调用有$O(n\log2_n)$种可能,我们可以提前通过上面的递推公式以$O(n\log2_n)$的时空复杂度预处理得到。之后的所有$f$调用的时间复杂度都为$O(1)$,这也是st算法能够在$O(1)$时间复杂度内回答区间最小值的关键。

现在,假设我们要查询区间$[l,r]$的最小值。我们知道区间$[l,r]$的最小值,也就是$[l,r+1)$的最小值。记$k=\lfloor \log_2(r+1-l) \rfloor$,则$[l,r+1)$的最小值必定是$[l, l+2^k)$的最小值和$[r+1-2^k,r+1)$的最小值中的较小者,即$min(f(l,k), f(r+1-k,k))$。

上面的操作几乎可以认为是$O(1)$了,美中不足的是我们需要计算$\lfloor \log_2(r+1-l) \rfloor$。一般对于这种操作,各种语言都提供了接近$O(1)$的奇技淫巧,但是如果追求严格,可以以预先处理的方式以$O(n)$的时空复杂度计算$\lfloor \log_2x \rfloor$,其中$x=1,2,\ldots,n+1$。这样对数向下取整也能保证以$O(1)$的时间复杂度得到。

上面预处理的总的时间复杂度和空间复杂度均为$O(n\log_2n)$,而每次查询区间最值仅需要$O(1)$的时间复杂度。

LCA

LCA问题可以转换为区间最值问题,之后利用st算法就可以高效求解了。

首先我们对树进行深度优先搜索,当第一次访问结点$u$时,将$u.enter$记录为当前时间戳。之后比较特殊的是,在访问$u$时,我们首先将$u$加入某个列表尾部,之后每次访问$u$的子结点返回后,都要将$u$再次加入列表尾部,访问$u$完毕后将$u.leave$设置为当前时间戳。

第一次将$u$加入该列表尾部的费用由$u$支付,之后每次访问某个结点$v$后再次加入$u$的费用由边$(u,v)$支付,每次支付的费用为1,而一株大小为$n$的树中,结点数目为$n$,边的数目为$n-1$,因此最终搜索完毕后列表的大小为$2n-1$。

void dfs(root){
    root.enter = list.size();
    list.add(root);
    for(Node child : root.children)
    {
        dfs(child);
        list.add(root);
    }
    root.leave = list.size() - 1;
}

接下来,每次查询结点$x=lca(u,v)$,等价于查询list区间$I=[min(u.enter,v.enter), max(u.leave, v.leave)]$中$enter$值最小的哪个结点。这就是我们上面聊到的区间最值问题。

下面证明一下下面几点:

  1. 区间$I$中一定包含$u$与$v$的$x$。
  2. $x$是区间$I$中拥有最小$enter$值的结点。

如果$u=v$,落在区间$I$中的结点都是$u$的子结点,因此两条命题都是满足的。下面都认为$u.enter < v.enter$,由于$x=lca(u,v)$,那么可知$u$和$v$分别处在$x$下不同的两个子树中,因此在从含$u$的子树中递归返回后,$x$会被加入到列表尾部,之后会访问$v$,很显然命题1是满足的。并且在$x$返回之前,中间不会加入其它$x$的祖先结点,即$x$是拥有最小$enter$值节点,命题2是满足的。上面的推理对于$u=x$的情况也是一样的。

莫队算法

莫队可以用于解决一类区间离线统计问题。如果我们以经统计了$[l,r]$的信息,现在要统计$[l+1,r]$、$[l-1,r]$、$[l,r-1]$、$[l,r+1]$(这四种转移是基础转移),如果你能很快滴给出答案,那么就可以用莫队来优化离线区间查询。

假设我们现在有一段长度为n的序列,之后有m个查询,每个查询需要统计一段区间的信息。

下面我们首先按固定大小k进行分块,若请求的左边界为l,那么它会落在块$\lfloor \frac{l}{k} \rfloor$中。首先对查询预先进行排序,排序的第一关键字为查询所属的块,第二关键字为查询的右边界r。

之后我们按顺序处理每个请求,只不过在切换请求时我们复用上一个请求留下来的区间统计信息。比如现在区间为$[a,b]$,而查询的区间为$[l,r]$,我们可以通过四种基础转移将区间进行转换,需要执行$|a-l|+|b-r|$次转移。

下面我们来分析时间复杂度:

对于块号相同的查询,由于查询的右边界递增,因此右边界最多移动n次。总共有n/k个块,故最多移动$n^2/k$次。

对于块号相同的查询,由于每次切换查询时,左边界最多移动k次,共有m个查询,因此最多移动$km$次。

对于不同块的交界,切换时,我们左边界和右边界可能需要重置,这部分最多需要$2n$次基础操作,块最多切换$n/k$次,因此总共移动$2n^2/k$。

加总所需的时间费用,总共为$O(m\log_2m+km+n^2/k)$,当我们取$k=n/\sqrt{m}$时,此时时间复杂度为$O(m\log_2m+n\sqrt{m})$。

带修改莫队

我们可以将莫队修改成支持单点修改的形式。

设区间长度为n,区间查询与单点修改共m次。如何用莫队优化。

我们为查询引入版本的概念,一个查询的版本为在该次查询发生之前发生的修改次数。之后我们选取一个数k,并进行分块。对于查询,其左边界为l,右边界为r,版本为v,其属于分块$(\lfloor \frac{l}{k} \rfloor, \lfloor \frac{v}{k} \rfloor)$。定义块号的顺序为块号的字典序。首先我们需要对查询进行预先排序,排序的第一关键字为查询所处块号,第二关键字为查询的右边界。

之后按顺序处理查询。对于一个查询,如果版本号为上一个处理的查询不同,我们还需要应用或回退一些修改。

下面证明时间复杂度:

对于同一个块的查询,右边界最多移动n次,块数不超过$nm/k^2$,因此右边界总计移动$n^2m/k^2$。

对于同一个块中的查询,左边界和版本号最多分别变动k次,因此总共最多发生$2mk$次变动。

对于块之间的切换,每次左边界最多修改n,右边界最多修改n,版本最多修改m,因此总共发生$(2n+m)nm/k^2$次修改。

总的时间复杂度为$O(m\log_2m+3n^2m/k^2+2mk+nm^2/k^2)$。当我们取k为$n^{2/3}$时,得到时间复杂度$O(m\log_2m+n^{2/3}m+m^2/n^{1/3})$。

高维莫队

考虑$[0,N]^k$向量空间,我们初始时位于$(0,\ldots,0)$处。现在有$Q$个目的地$p_1,\ldots,p_n$。我们需要经过所有目的地。每次我们可以移动到曼哈顿距离为$1$的另外一个整数点上。问最少需要的步骤数。

这个问题是旅行商问题,是NP问题。因此我们将问题改成,设计一条足够短的路径。

很显然我们直接从起点到$p_1$,从$p_1$到$p_2$,如此重复下去,就能得到一条路径,但是这条路径的长度可能达到$QkN$。

这里我们可以使用一个简单的优化,就是将$k$个维度的前$k-1$个维度进行分块,块大小为$B$。接下来我们对所有请求进行排序,首先按照所在块进行排序(同一块的请求放在一起),如果块相同则按照第$k$个维度进行排序。

对于每个请求块内的转移费用最多为$(k-1)B$,而对于每个块其第$k$个维度的转移所需步骤为最多为$N$。同时切换块的时候转移为$kN$。块的数目为$(\frac{N}{B})^{k-1}$。因此总的步骤上限为$Q(k-1)B+(\frac{N}{B})^{k-1}(N+kN)$。

上面如果我们取$B=N^\frac{k-1}{k}$,这样需要的步骤数为$O(QkN^{1-\frac{1}{k} }+(k+1)N^{2-\frac{1}{k} })=O(kN^{1-\frac{1}{k}}(Q+N))$。

这里一般认为$Q=O(N)$,这样需要的步骤数为$O(kN^{2-\frac{1}{k}})$。

下面我们用高维莫队来解释已有的莫队:

  • 普通的序列上的莫队,请求由$l,r$两个属性决定,我们可以将其映射到二维空间上。现在我们从$0$出发,要处理所有请求(经过所有请求),莫队算法提供的步骤数为$O(2N^{1.5})$。这里每一步的费用为1,因此时间复杂度也是$O(2N^{1.5})$。
  • 考虑在二维数组上,我们需要查询某个子矩阵中的各种信息。每个请求可以由$l,r,b,t$决定,可以映射到四维空间。因此用莫队解决所需步骤数为$O(4N^{1.75})$。当然你说这时间复杂度怎么可能,当然我们这里并没有提及时间复杂度,实际上二维数组上每移动一步的费用为$O(N)$(比如$l$增大,对应要删除最左边的列,共$O(N)$个元素),因此时间复杂度为$O(4N^{2.75})$,依旧比暴力的$O(N^3)$好。
  • 考虑带修改莫队,每个请求都由$l,r,time$所决定,因此可以映射到三维空间。所以用莫队解决所需步骤数为$O(3N^{1.667})$。但是和二维数组上的莫队不同,这里每步的费用也是$O(1)$,因此时间复杂度为$O(3N^{1.667})$。

树上莫队

莫队可以扩展到树上。

对于子树查询,我们可以先计算树的dfs序,之后子树的dfs序一定是连续的,形成一个区间。那么实际上如果我们将结点按照dfs序铺平,那么子树查询就对应了普通的区间查询,直接可以上莫队。同样在这种情形下要支持单点修改,将普通莫队替换为带修改莫队即可。

还有一类比较神奇的应用是树上路径统计。我们知道一株树可以用括号序列来表示,比如(()())是一个根结点带两个叶结点。一个结点在其括号序列中对应两个括号,一个开括号一个闭括号。那么要查询从u到v的路径,我们这边假设u的左括号在v的左括号之前出现,那么可以发现在括号序列中,u的右括号到v的左括号之间仅u到v的路径上顶点的括号正好出现一次,其余顶点的括号要么成对出现要么不出现。因此我们可以认为一个顶点出现奇数次则包含入结果,否则从结果剔除。这里需要特别注意的是u和v的lca可能需要手动处理。

一类阈值查询问题

所谓的阈值问题是指要让你维护一个数组,支持区间更新,以及查询某个区间中有多少数大于等于$k$。

问题1:给定一个序列$a_1,a_2,\ldots, a_n$和一个数$k$,给定m次操作,操作分成两种,第一种是将区间中所有元素加上某个数$x$,第二种操作是询问区间中所有大于等于$k$的元素值的和,这个问题中$x\geq 0$,$n,m\leq 10^5$

由于$x\geq 0$,我们可以直接暴力维护两颗线段树,第一颗线段树维护数组中所有小于$k$的元素的信息,第二颗线段树维护所有大于等于$k$的元素信息。每次更新操作都需要同时修改两颗线段树,并且修改完后需要不断检查第一颗线段树中最大的元素是否大于等于$k$,如果是,将其从第一颗线段树中删除,并迁移到第二颗线段树中。查询只需要查询第二颗线段树。由于每个区间中的元素最多会被迁移一次,因此时间复杂度为$O((n+m)\log_2n)$。

问题2:给定一个序列$a_1,a_2,\ldots, a_n$和一个数$k$,给定m次操作,操作分成两种,第一种是将区间中所有元素加上$x$,第二种操作是询问区间中所有大于等于$k$的元素值的和,这个问题中$|x|=1$,$n,m\leq 10^5$。

这个问题的难点在于存在负数的情况,假如使用问题1中提到的算法那么就无法保证迁移只发生$n$次。

下面来聊聊做法,我们将区间分块维护,每一块的大小为$b=\sqrt{n}$。这样每次区间更新操作可以看成$b$个块的完全更新和$2$个块的局部更新。前者我们用惰性标记,同时计算一下有哪些数大于等于$k$。后者我们可以直接暴力更新即可。这里值域比较大,我们可以用哈希表来存储每个块中元素值为$t$的所有元素的总和。查询操作就加总一下所有块即可,总的时间复杂度为$O(n\sqrt{n})$,这里由于使用了哈希表所以可能常数比较大。

问题3:给定一个序列$a_1,a_2,\ldots,a_n$。之后$m$次操作,操作分为三类:

  1. 给定区间$l_i,r_i,x_i$,对于$l_i<j<r_i$,将$a_j$修改为$\max(a_j,x_i)$
  2. 查询区间$l_i,r_i,x_i$,输出$\sum_{j=l}^r\max(a_j-x_i,0)$

这里保证第二类请求中$x_i$非严格递增,$1\leq n,m\leq 10^6$

我们可以用Segment tree beats来解决这个问题,对于第一类更新操作,Segment tree beats本来就支持。考虑第二类操作,我们可以这样做,将所有数都增大到至少$x_i$,这样区间和就是原本的区间和减去$(r-l+1)\cdot x_i$,注意到由于第二类请求的$x_i$递增,因此增大操作不会影响后面请求的结果。

问题4:给定一个序列$a_1,a_2,\ldots,a_n$。之后$m$次操作,操作分为三类:

  1. 给定区间$l_i,r_i,x_i$,对于$l_i<j<r_i$,将$a_j$修改为$\max(a_j,x_i)$
  2. 查询区间$l_i,r_i,x_i$,输出$\sum_{j=l}^r\max(a_j-x_i,0)$

这里保证第二类请求中$x_i$非严格递减,$1\leq n,m\leq 10^6$

这道题可以这样做。我们可以建立两个线段树,第一个线段树维护序列中$a_j<x_i$的部分,而第二个线段树维护其余部分。可以发现我们在整个过程中不断将元素从第一个线段树中移动到第二颗线段树中。可以证明移动的元素总数不会超过$O(n)$。第二类线段树由于需要支持总和和区间取最大操作,因此需要用Segment tree beats来实现。

而总和的话只需要去第二颗线段树中查询即可。时间复杂度为$O((n+m)\log_2n)$。

提供一道题目

多维平面操作问题

一般的区间操作都是发生在一维平面上的,但是当这些区间操作发生在多维平面上时,问题将变得非常困难,甚至不能给出多项式时间内的解法。

问题1:给定一个$n\cdot m$的矩阵$1\leq n,m\leq 10^9$,每个矩阵单元的初始值都是0。之后给出$q$次请求,每次请求要么要求你将落在某个子矩形中的所有单元都加上一个数(可能是负数),要么要求查询某个子矩形中所有单元的值的和

这个问题可以直接用稀疏二维线段树解决(动态开点)。但是这样的空间复杂度为$O(q\log_2n\log_2m)$。

问题2:给定一个$n\cdot m$的矩阵$1\leq n,m\leq 10^9$,每个矩阵单元的初始值都是0。之后给出$q$次请求,每次请求要么要求你修改某个单元的数(可能是负数),要么要求查询某个子矩形中所有单元的值的和

这个问题可用问题1的方案直接解决。如果我们将每次更新看成点的增加和删除,将请求发生的时间作为第三个维度,那么我们可以将查询操作视作在三维平面上的某个立方体中的顶点权值总和的查询,这允许我们用CDQ分治疗解决,时间复杂度为$O(q(\log_2q)^2)$,空间复杂度为$O(q)$。

问题3:给定一个$n\cdot m$的矩阵,$1\leq n,m\leq 10^9$,之后给出$q$个请求,每次请求要么要求你修改某个单元的数(可能是负数),要么要求查询某个子矩形中所有单元的值的最大值

这个问题可以直接用稀疏二维线段树解决。时间复杂度和空间复杂度均为$O(q\log_2n\log_2m)$。

问题4:给定一个$n\cdot m$的矩阵,$1\leq n,m\leq 10^3$,之后给出$q$个请求,每次请求要么要求你将落在某个子矩形中的所有单元都加上一个数(可能是负数),要么要求查询某个子矩形中所有单元的值的最大值

这个问题可以用这种方式解决,我们可以建立Quad tree,之后你就可以以$O(n+m)$时间复杂度处理每个请求,总的时间复杂度为$O((n+m)q)$。

问题5:给定一个$n\cdot m$的矩阵,$1\leq n,m\leq 10^9$,,每个单元的初始值都是0。之后给出$q$个请求,每次请求要么要求你将落在某个子矩形中的所有单元都加上一个数(可能是负数),要么要求查询某个子矩形中所有单元的值的最大值,这里$q\leq 10^4$。

我们没法开quad tree,因为矩阵太大了。这里我们可以对请求进行离散化操作,将一个矩形拆分成$12$个点。如下图。

https://raw.githubusercontent.com/taodaling/taodaling.github.io/master/assets/images/2020-02-29-interval/clip.png

之后可以用KD树求解,由于$k$维KD树区间查询修改的时间复杂度是$O(n^{1-\frac{1}{k}})$,而这里维度是2,因此时间复杂度为$O(q\sqrt{12q})$

区间选择问题

问题1:给定一个序列$a_1,a_2,\ldots, a_n$,以及$m$个区间$I_1=[l_1,r_1],I_2=[l_2,r_2],\ldots, I_m=[l_m,r_m]$。现在我们允许选择任意个区间,将所有被至少一个选中区间覆盖的元素$a_i$加总,问总和最大可以为多少。其中$-10^9\leq a_i \leq 10^9,1\leq n\leq 10^5,1\leq m\leq 10^5$。

可以发现,如果我们选择了两个区间$[l_i, r_i]$和$[l_j,r_j]$,且$l_j\leq l_i \leq r_i\leq r_j$,那么区间$i$是否选择并不会影响结果。因此我们可以认为不允许同时选择嵌套的区间。

对于区间$I_i$,我们为其建立一个DP状态$dp(I_i)$,其意义为已选的右边界最大的区间为$[l_i,r_i]$的前提下最大总和是多少。

第一类转移:对于区间$j$,如果$r_j<l_i$,那么转移公式为:$dp(I_i)=dp(I_j)+s(r_i)-s(l_i-1)$,其中$s(k)=a_1+\ldots+a_k$。

第二类转移:对于区间$j$,如果$l_j\leq l_i \leq r_j\leq r_i$,这时候两个区间有交,此时转移公式为:$dp(I_i)=dp(I_j)+s(r_i)-s(r_j)$。

有了转移公式,那么如果找到这些满足条件的$j$呢。我们可以将区间的左边界作为横坐标,将区间的右边界作为纵坐标,这时候会发现所有两类转移都落在由$(0,0)$和$(l_i,r_i)$组成的矩形内。且矩形中坐标大于等于$l_i$的为第二类转移,小于$l_i$的为第一类转移。

上面的几何化意味着我们可以用二维线段树来维护平面信息,但是实际上我们可以通过提前对一个维度进行排序处理的技术,使用普通线段树就可以维护了。

对于第一类转移和第二类转移需要分别建立一颗线段树进行维护。总的时间复杂度为$O(n+m(\log_2n+\log_2m))$。

提供一道Atcoder的题目

问题2:给定一个序列$a_1,a_2,\ldots, a_n$,以及$m$个区间$I_1=[l_1,r_1],I_2=[l_2,r_2],\ldots, I_m=[l_m,r_m]$。现在我们恰好选择$k$个区间,将所有被至少一个选中区间覆盖的元素$a_i$加总,问总和最大可以为多少。其中$-10^9\leq a_i \leq 10^9,1\leq n\leq 10^5,1\leq m\leq 10^5$。

首先在不考虑$k$的约束情况下,这个问题与问题1无异。可以发现随着$k$增大,增幅会越小,这意味着由$k$和最优解组成的曲线是一个上凸包。考虑到这些,我们就可以利用WQS技术结合问题1求DP的方式解决这个问题,时间复杂度为$O((n+m(\log_2n+\log_2m))\log_2M)$,其中$M$与数值大小以及精度有关,一般不会超过$60$。

问题3:给定一个序列$a_1,a_2,\ldots, a_n$,以及$m$个区间$I_1=[l_1,r_1],I_2=[l_2,r_2],\ldots, I_m=[l_m,r_m]$。现在我们任意选择区间,将所有被至少一个选中区间覆盖的元素$a_i$加总,问总和最大可以为多少。其中$0\leq a_i \leq 10^9,1\leq n\leq 10^6,1\leq m\leq 10^6$。

这道题连题都不算,我们直接将所有被至少一个区间覆盖的数值加总起来即可,时间复杂度$O((n+m)\log_2n)$,如果区间已经被按照左边界排序过,那么时间复杂度为$O(m+n)$

问题4:给定一个序列$a_1,a_2,\ldots, a_n$,以及$m$个区间$I_1=[l_1,r_1],I_2=[l_2,r_2],\ldots, I_m=[l_m,r_m]$。现在我们要正好选择$k$个区间,将所有被至少一个选中区间覆盖的元素$a_i$加总,问总和最大可以为多少。其中$0\leq a_i \leq 10^9,1\leq n\leq 10^6,1\leq m\leq 10^6$。

这道题实际上是问题2的简化版,于是我们直接可以得出一个$O((n+m(\log_2n+\log_2m))\log_2M)$的做法。但是这道题的数据范围加大了,因此这种做法会超时。

可以想到用WQS二分来解决这个问题,但是现在问题来了,如何计算每次决策惩罚$C(C\geq 0)$的情况下最优能得到的总权。

首先我们还是假设不能选择两个相互包含的区间,因为这是没有意义的。

对于区间$I_i$,我们为其建立一个DP状态$dp(I_i)$,其意义为已选的右边界最大的区间为$[l_i,r_i]$的前提下最大总和是多少。

第一类转移:对于区间$j$,如果$r_j<l_i$,那么转移公式为:$dp(I_i)=dp(I_j)+s(r_i)-s(l_i-1)$,其中$s(k)=a_1+\ldots+a_k$。

第二类转移:对于区间$j$,如果$l_j\leq l_i \leq r_j\leq r_i$,这时候两个区间有交,此时转移公式为:$dp(I_i)=dp(I_j)+s(r_i)-s(r_j)$。

对于第一类转移,由于$s(r_i)-s(l_i-1)$是常数,因此我们只需要取最大的$dp(I_j)$即可。而对于第二类转移,比较复杂,但是注意到$s(i)$是非严格递增函数,因此我们可以使用斜率优化计算。

因此在已知惩罚的前提下,一次DP的时间复杂度为$O(n+m)$,结合WQS二分总的时间复杂度为$O((n+m)\log_2M)$,是可以通过的。

提供一道CF题目

问题5:给定一颗树,树根为1,树上有$n$个顶点,第$i$个顶点有一笔价值$w_i$的财富。其中$m$个顶点是特殊的,我们现在可以派出$k$个人,从$k$个特殊的顶点出发,向根出发,搜集路上所有的财富(同一个顶点的财富只会被搜集一次)。问我们最多可以得到多少总财富?其中$0\leq w_i \leq 10^9,1\leq k\leq n\leq 1000$

这个题目首先可以想到费用流,我们将每个顶点拆分成两个,两个顶点连一条费用为$-w_i$容量为1的边。每个顶点同时连源点和汇点。看最优值即可。总的时间复杂度为$O(kV\log_2V)$,这里使用Dijkstra优化的费用流。

问题6:给定一颗树,树根为1,树上有$n$个顶点,第$i$个顶点有一笔价值$w_i$的财富。我们现在可以派出$k$个人,从$k$个顶点出发,向根出发,搜集路上所有的财富(同一个顶点的财富只会被搜集一次)。问我们最多可以得到多少总财富?其中$-10^9\leq w_i \leq 10^9,1\leq k\leq n\leq 10^6$

我们可以直接用贪心法证明,每次选择出发收益最大的顶点出发,$k$次后得到的就是最大收益。假设$v$是初始时出发收益最大的顶点,那么如果最后的方案中不选择$v$,记方案中被搜集的顶点形成的树为$T$,我们可以找到$T$中$v$的深度最小的祖先,回退之前$T$下的任意一个特殊顶点带来的影响,并加入$v$,可以证明这时候我们的收益是不会减少的。

首先我们可以利用所有顶点的dfs序构建线段树,之后利用线段树实现区间修改和弹出全局收益最大顶点的能力(即大根堆)。

第一次增广非常容易,找到收益最大的顶点$v$即可。将其弹出后,我们暴力枚举其所有祖先,之后修改祖先下其余顶点的收益,比如枚举到祖先$a$,祖先到当前顶点的路径中除了祖先外,深度最小的顶点记作$b$,那么我们将$a$代表的子树中的所有顶点的权重减去$a$的收益,但是$b$中的子树需要另外加上$a$的收益(即抵消该次变化)。而对于$v$,我们将$v$下所有顶点减去$v$的收益。这样我们遍历$v$的所有未被处理过的祖先就可以修正剩余所有特殊顶点的收益了。

可以发现每个每个顶点最多被访问一次,因此总的时间复杂度为$(n+k)\log_2n$。

给一道BZOJ题目,是这道题的弱化版。

区间颜色统计问题

题目1:给定一个序列$a_1,\ldots,a_n$,之后给出$q$个查询,第$i$个查询为$l_i,r_i$,询问$a_{l_i},\ldots,a_{r_i}$中有多少不同的数。

典型问题,最简单的方式就是直接用莫队,时间复杂度为$O(n\sqrt{n})$。但是实际上这个问题存在$O(n\log_2n)$的解法。

首先定义一个新序列$b_1,\ldots,b_n$,$b_i$表示第$i$个数之前与$a_i$相同的数中最大的下标(如果不存在则设为$-1$)。那么现在查询询问的实际上是区间$b_{l_i},\ldots,b_{r_i}$中有多少数小于$l_i$。

实际上我们可以把第$i$个数转换成二维平面点:$(i,b_i)$。这样查询其实询问的是某个二维平面中子矩形中的顶点数目。由于是离线查询,因此可以用线段树$O(n\log_2n)$求解。

题目2:给定一个序列$a_1,\ldots,a_n$,之后给出$q$个查询,第$i$个查询为$l_i,r_i$,询问$a_{l_i},\ldots,a_{r_i}$中有多少不同的数。查询强制在线。

由于是在线查询,因此莫队方法是行不通的。

我们可以用题目1的技巧将问题转换为二维点,之后用持久化线段树替换普通线段树,这样就可以支持在线查询了,时间复杂度和空间复杂度均为$O(n\log_2n)$。

题目3:给定一个序列$a_1,\ldots,a_n$,之后给出$q$个操作,操作分为两类:第一类,查询$l_i,r_i$,询问$a_{l_i},\ldots,a_{r_i}$中有多少不同的数;第二类,修改某个$a_{x_i}$,将其修改为某个指定数。

由于可以离线,所以用带修莫队可以过,时间复杂度为$O(n^{\frac{5}{3}})$。

同样我们将每个值转换为二维点,而修改操作就变成了增加点和删除点(对应点权为$1$和$-1$)。因此第$i$个值转换为$(i,b_i,t_i)$,其中$t_i$表示这个顶点出现的时间。之后问题就变成了三维空间的子矩形问题,可以利用CDQ分治以$O(n(\log_2n)^2)$的时间复杂度求解。

题目4:给定一个序列$a_1,\ldots,a_n$,之后给出$q$个操作,操作分为两类:第一类,查询$l_i,r_i$,询问$a_{l_i},\ldots,a_{r_i}$中有多少不同的数;第二类,修改某个$a_{x_i}$,将其修改为某个指定数。要求查询和修改在线。

莫队继续躺好。

将每个值转换为二维点之后,问题就变成了在线删点、加点以及统计区间,稀疏二维线段树足矣。时间复杂度和空间复杂度均为$O(n(\log_2n)^2)$。

题目5:给定一株拥有$n$个顶点的树,第$i$个顶点上写着$a_i$。要求统计每个顶点作为根的子树下有多少不同的数。

树上DSU可以轻松解决,时间复杂度为$O(n\log_2n)$。

题目6:给定一株拥有$n$个顶点的树,第$i$个顶点上写着$a_i$。之后$q$个查询,每个查询指定两个顶点$u,v$,要求回答$u$到$v$的唯一路径上的顶点上总共写着多少不同的数字。

树上路径统计是莫队的强项,直接用树上莫队即可。时间复杂度为$O(n\sqrt{n})$。

题目7:给定一株拥有$n$个顶点的树,第$i$个顶点上写着$a_i$。之后$q$个操作:操作1,指定两个顶点$u,v$,要求回答$u$到$v$的唯一路径上的顶点上总共写着多少不同的数字;操作2,修改某个顶点上的数字。

树上带修莫队,时间复杂度为$O(n^{\frac{5}{3}})$。

区间众数问题

题目1:给定一个序列$a_1,\ldots,a_n$,要求回答$q$个请求,第$i$个请求给定三个参数$l_i,r_i,k_i$,要求找出区间$a_l,\ldots,a_r$中出现次数超过$\frac{r_i-l_i+1}{k_i}$的最小的数,如果不存在则输出$-1$。其中$n,q\leq 10^5$,$1\leq k\leq 5$

这个问题有很多做法。

第一种就是用莫队。莫队内部维护一个统计表,统计每个数在区间中出现的次数。且由于每次每个数出现次数变化最多为$1$,因此对于每个分块,分配一个链表数组,第$i$个元素记录该分块中所有出现次数为$i$的元素组成的链表。很显然这样我们不管某个数出现次数是加$1$还是减$1$,都可以$O(1)$完成,且最重要的是我们可以实时统计每个分块中的最大值。在回答请求的时候,我们可以利用分块中的最大值先找满足条件的编号最小的分块,之后在分块中暴力查找。因此总的时间复杂度为$O((n+q)\sqrt{n})$。

莫队的做法优点是与$k$无关,缺点是常数比较大,且必须离线请求。

第二种做法就是发现,对于某个回答,我们可以不断从区间中选择$k$个不同的数,之后删除。最后留下来的数不超过$k-1$个,我们可以证明结果一定在这留下来的数中。这种区间消除的方式,我们可以用线段树实现,这样每次线段树的查询和修改的时间复杂度都是$O(k^2\log_2n)$。之后如果验证结果呢,这个我们可以通过持久化技术加差分或者直接上倍增完成,校验一个数的时间复杂度为$O(\log_2n)$,总的时间复杂度为$O((q+n)k^2\log_2n)$。

第二种做法的优点是支持在线(我们可以为每个数都开一个稀疏线段树),缺点就是$k$不能过大。

还有一种非常简单的做法就是直接上持久化线段树+差分的技术。线段树的每个结点记录区间中每个数出现的次数。之后对于每个请求,我们暴力扫描线段树,加上一旦发现区间中总数少于阈值就直接退出的剪枝。可以证明一次请求,线段树每一层最多有$k$个顶点被访问(因为阈值决定了每一层最多有$k$个条件满足条件)。总的时间复杂度为$O((n+kq)\log_2n)$。

第三种做法可以充分利用$k$很小的特性。但是$k$比较大的时候还是用莫队比较好。

一道题目

问题2:给定一个序列$a_1,\ldots,a_n$,以及$q$个请求,每个请求指定一个区间$l,r$,要求找到序列$a_l,\ldots,a_r$中的众数(出现次数最多的数),如果有多个,就输出其中最小的。这里$n,q\leq 10^5$,要求在线处理请求

一道题目

先离散化数据。

这道题目的核心是发现,要计算$A\cup B$的区间众数,其仅可能为$A$的区间众数,或者是$B$中的某个元素。

上面这个观察允许我们用分块解决这个问题。按照大小$\sqrt{n}$进行分块。

之后考虑一次请求,可以知道答案要么出现在区间两端的块中,要么就是区间中间部分的众数。

我们可以维护两个数组$c$和$p$。其中$c(i,j)$表示前$i$块中$j$的出现次数。这样我们可以利用差分的技巧来快速计算某个数字在连续块中总的出现次数。而$p(i,j)$表示第$i$块到第$j$块中的众数。数组$c$可以直接暴力计算每一块的信息最后统计前缀和,而$p$可以暴力枚举两端块,之后通过$p(i,j-1)$快速转移。预处理的时间复杂度和空间复杂度均为$O(n^{1.5})$。

每次请求我们也能以$O(\sqrt{n})$求解,枚举每个可能的众数即可(总共只有$O(\sqrt{n})$种可能)。

总的时间复杂度为$((n+q)\sqrt{n})$。

分块技巧

假设给我们一个长度为n的数组,要求支持区间更新,区间统计。

最简单的方式是将数组分块,每一块大小为$m=\sqrt{n}$。之后我们为每一块都额外维护一份辅助信息,第i块的辅助信息记作$f(i)$。

现在考虑区间更新问题,只要利用惰性标记就可以实现$\sqrt{n}$的时间复杂度。对于完全处于区间中的块,我们直接标记在辅助信息上(如果已经有标记了,就合并标记),这样的块最多有$\sqrt{n}$个。而对于与区间有交集的却不被完全覆盖的块,我们先下推标记,之后直接暴力修改,可以得知这样的块不会超过两个,总的修改的元素不超过$2\sqrt{n}$个。

查询操作也是相同的,对于被完全覆盖的块,直接从辅助信息中提取,否则直接暴力查询,时间复杂度为$O(\sqrt{n})$。

题目1:给定$n$个数$a_1,\ldots,a_n$,要求处理$m$个请求,请求分两类:第一类某个区间加上一个数$x$(允许为负数)。第二类查询区间中小于$x$的数的数目。(其中$x$不同请求可能不一样),$n,m\leq 10^5$。

这个问题可以对数组进行分块,设$B$为每块的大小。之后对于修改操作,中间的区间打标记,两端的区间暴力更新(合并两个有序区间可以线性完成),因此修改请求的时间复杂度为$O(\frac{n}{B}+B)$。而对于查询请求,中间的用二分查找法,两端的暴力查找,时间复杂度为$O(2B+\frac{n}{B}\log_2B)$。

因此时间复杂度的上限为$m(B+\frac{n\log_2B}{B})$,我们可以选择$B=\sqrt{n\log_2B}$,则每个请求的时间复杂度为$\sqrt{n\log_2B}$,总的时间复杂度为$O(m\sqrt{n\log_2B})$。

实际上这个问题还可以用Fractional Cascading的技术,优化到$O(m\sqrt{n})$,但是由于实现复杂,很可能常数会大于$\sqrt{\log_2n}$。

提供一道题目

题目2:给定$n$个数$a_1,\ldots,a_n$,要求处理$m$个请求。请求分为两类:第一类请求要求将区间$[l,r]$中所有大于等于$x$的数全部减去$x$,第二类请求查询区间$[l,r]$中有多少数正好等于$x$(不同请求的$x$可以不同)。满足$1\leq n,m,a_i,x\leq 10^5$。

我们可以按$B$对数组进行分块,并记录一个数组$L$,其中$L(i,j)$代表第$i$块中值恰好为$j$的所有数组成的链表。

先考虑查询操作,两端的区间暴力处理即可,时间复杂度为$O(B)$。而中间的每个区间,我们可以直接查表$O(1)$得出结果,因此总的时间复杂度为$O(B+\frac{n}{B})$。

在考虑修改操作,两端的区间暴力处理,时间复杂度为$O(B)$。而中间的区间,我们记区间中的最大值为$k$。

  • $2x\leq k$,我们可以暴力查表找出所有小于$x$的数,并将其增加$x$。之后我们给整个块打上一个减$x$的标记。(这时候最大值为$k-x$)
  • $2x > k$,我们可以暴力查表找出所有大于等于$x$的数,并将其减去$x$。

对于第一个操作,我们每查找一个数,最大值都要减少1。而对于第二个操作,最大值减少的量不少于我们查找数的数目。因此对于每个块,我们可以断定扫描次数一定不超过这个块中的最大值。记所有数的最大值为$M$,那么扫描的总次数不超过$M\frac{n}{B}$。

综合上面所说的,时间复杂度为$O(mB+\frac{nm}{B}+\frac{nM}{B})$。这里我们可以记$N=\max(n,m,M)$即可得到$O(N\sqrt{N})$时间复杂度。

一道题目

树上分块

题目1:给定$n$个顶点组成的树,第$i$个顶点上写着一个数字$a_i$。令顶点$1$作为根。现在给出$q$个请求,每个请求指定两个顶点$u,v$,其中保证$u$是$v$的祖先。这时候给$u$到$v$路径上任意顶点分配权重,顶点$x$的权重为$a_x\oplus dist(v,x)$,对于每个请求,找出$u$与$v$决定的唯一路径上,最大的顶点权重。其中$1\leq n\leq 6\times 10^4$,$0\leq a_i\leq n$,$1\leq q\leq 2\times 10^5$。

发现所有涉及的数最多只有16位(二进制),我们可以将每个数拆解为高8位和低8位。预处理出数组$dp(v,i)$,记$A$表示所有顶点$v$的祖先中距离顶点$v$小于$2^8$的顶点组成的集合,则$dp(v,i)=\max_{u\in A} a_u\oplus dist(u,v)\oplus (i\cdot 2^8)$。

我们一旦计算出$dp(v,i)$,对于每个请求,我们可以从路径底部每次向上跳$2^8$距离,如果距离顶部小于$2^8$,则暴力计算。因此一次请求的处理时间复杂度最多为$\frac{6\cdot 10^4}{2^8}+2^8\leq 2^9$。请求处理的总时间为$O(2^9q)$。

那么该如何计算$dp(v,i)$呢,最简单的暴力计算方法就是枚举所有满足条件的祖先,这样处理每个顶点的时间复杂度为$O(2^{16})$,有点大。但是可以发现$dp(v,i)$与$dp(v,j)$的区别仅在于前者拿$a_u\oplus dist(u,v)$亦或上$i\cdot 2^8$,后者亦或上$j\cdot 2^8$。因此我们可以对一个顶点同时计算其相关的所有dp状态,用二叉树进行维护,这样时间复杂度就为$O(8\cdot 2^{8})$。

总的时间复杂度为$O(8\cdot 2^8n+2^9q)$。

区间最值算法

给定一个静态序列$a_1,\ldots,a_n$,现在要求我们回答$q$个请求,每个请求给定$l,r$,要求计算$\max_{l\leq i\leq r}a_i$。

这个我们可以用线段树或BIT,但是这样很浪费,因为它们支持修改导致查询时间为$O(\log_2n)$。我们可以上Sparse Table将查询时间复杂度优化到$O(1)$,缺点在于花费了$O(n\log_2n)$的空间复杂度和预处理时间复杂度。

下面我们来讨论一下如何$O(n)$预处理并且$O(1)$回答询问的算法。

首先我们知道笛卡尔树,将最大值作为根,最大值左边的数放在左子树,右边的数放在右子树,并且递归处理。我们可以$O(n)$时间复杂度内构建原序列的笛卡尔树。

我们可以直接断言$a_l,\ldots,a_r$中的最大值,为$a_l$和$a_r$在笛卡尔树上的LCA。考虑笛卡尔树的构建过程,在第一次从$a_l,\ldots,a_r$范围中取最大值作为根之前,$a_l$和$a_r$还属于同一子树,之后$a_l$和$a_r$就属于$\max_{l\leq i\leq r}a_i$的左子树和右子树中(当然有可能变成祖先和后代的关系)。

由于存在$O(n)$预处理时间$O(1)$查询的树上LCA的算法,比如Schieber-Vishkin算法,因此我们有能力实现我们高校的RMQ算法。

参考资料