关于一类子区间计和问题

· · 算法·理论

前言

笔者在做题时见到了一些相似的题目,他们都有这样的特点:给定一个序列,多组询问区间,每次回答该区间的所有子区间的 w(l,r) 之和,其中 w(l,r) 是与区间最大/最小值相关的一个函数。本文旨在探究此类问题的一种套路解法。

例题

子区间最大子段和:https://vjudge.net/problem/Baekjoon-20799
子区间 \max a \times\max b(NOIP2022 比赛):https://www.luogu.com.cn/problem/P8868
子区间最大前缀:不在此处。
连续段子区间计数(一题多解):https://www.luogu.com.cn/problem/CF997E

法1

这类问题一种广为人知的做法是使用历史和线段树进行维护。这种做法在各个例题的题解区都有所介绍,在此不作赘述,读者可自行查阅。

这种方法的优点很明显,时间复杂度低,容易强制在线,代码量相对较小;但也有一些缺点,比如有些与 chkmax 相关的信息不容易上历史和(例如最大子段和),推式子更加需要数学功底等。

法2

这是本文要着重讲解的分治做法。

单组询问

以子区间最大子段和之和为例讲解具体算法流程。 ![](https://cdn.luogu.com.cn/upload/image_hosting/jvck0c27.png) 先写出区间最大子段和的式子表达: $$w(L,R)=\max(\max(ans_L,ans_R),maxsuf_L+maxpre_R)$$ 其中 $ans_L$ 表示在 $[L,mid]$ 中的最大子段和,$ans_R$ 类似,$maxsuf_L$ 表示以 $mid$ 为右端点的最大后缀,$maxpre_R$ 类似。 容易发现上述4种变量都有单调性。考虑对 $ans_L$ 和 $ans_R$ 进行归并,假设当前有 $ans_L \le ans_R$,那么我们就计算以 $L$ 为左端点,$[mid+1,R-1]$ 为右端点的所有区间(例如 $[L,mid+1]$,$[L,mid+2]\dots$)的贡献。 由于已经归并,所以可知 $ans_L\ge ans_{R-1}$,那么 $w(L,R')$ 一定不会取 $ans_{R'}$ 那一项($R'\in [mid+1,R-1]$)。式子化为: $$\max(ans_L,maxsuf_L+maxpre_{R'})$$ 考虑何时右边取答案,有: $$ans_L\le maxsuf_L+maxpre_{R'}$$ $$ans_L-maxsuf_L\le maxpre_{R'}$$ 于是设第一个满足条件的位置为 $p$,右端点在 $[mid+1,p-1]$ 的答案全是 $ans_L$,在 $[p,R-1]$ 的答案全是 $maxsuf_L+maxpre_{R'}$。求和简易。 事实上,$p$ 随着 $L$ 的移动亦有单调性。此处略证。(由这个性质可以得到 $O(n\log n)$ 的解法) 归并在右边可以对称地写出式子维护,不再赘述。 如果 $p$ 的求取使用 lower_bound 进行,时间复杂度是 $O(n\log^2 n)$ 的。 区间贡献不会算重的简证:一个区间 $[L,R]$ 只会被更晚归并弹出的那个端点计算一次。 ### 多组询问 我们依旧进行归并,但实时地使用线段树(普通的,不需要历史和)维护——截止到目前归并的这个左端点,以某个右端点为下标的贡献总和。 也即给线段树的 $[mid+1,p-1]$ 区间加 $ans_L$,给 $[p,R-1]$ 加上 $maxsuf_L+maxpre_{R'}$。右侧对左侧贡献同理。所以要维护两棵这样的线段树,左右各一棵。 所以线段树要支持区间 $a_i$ 加 $v$,区间 $a_i$ 加上 $b_i$($maxpre_{R'}$),以及区间求 $a_i$ 的和。 如何回答询问?我们将询问也分治,如果询问在一边直接递归不计算;如果包含了整个区间就不递归等底下分治回来了再回答。 跨过了中点且不包含整个区间的将贡献分四部分:左递归,右递归,左归并,右归并。其中左右递归直接扔下去就可以,左归并指的是当 $L$ 归并到 $query_l$ 后,去线段树上查询 $[mid+1,query_r]$ 的区间和。$query_l$ 指的就是询问的左端点。右同理。(此处是 $L$ 与 $query_l$ 的双指针) 正确性简证:假设一个区间 $[L,R]$ 是由 $L$ 晚归并,那么它的贡献就会算进左归并线段树的下标 $R$ 处。这本质上确实是满足了子区间二维偏序。 询问带来的复杂度可以用类似线段树的复杂度分析得到。总共是 $O((n+q)\log^2 n)

其他例题的做法

子区间 \max a \times\max b(NOIP2022 比赛)

这题以 a 的前后缀最大值进行归并,然后用 b 的前后缀最大值 lower_bound,再用线段树维护即可。

连续子区间计数 (Good Subsegments)

这题单组询问有一种较为奇妙的转化:考虑将 (i,i+1) 这个数对选不选抽象成一个点。如果原序列上的 ii+1 之间的最值为 mxmn,那么你选了 (i,i+1) 就要选 (mn,mn+1)\dots(mx-1,mx)。于是转化后问题为:每个点对应一条线段,你要计数有多少区间 [L,R] 满足封闭,也即在该区间里的点所对应的所有线段都被这个区间包含。最后还要给答案加 n,因为 i 本身也合法。读者有兴趣可以尝试这个推一推这个做法,但很可惜它难以支持多组询问。

这题套路的做法也要用到结论:区间合法当且仅当 max-min=r-l。我们考虑对前缀最大值归并,然后再 lower_bound 前缀最小值。

设当前归并到 [L,R]sufmax_L\le premax_R,第一个满足 sufmin_L\ge premin_p 的位置是 p

对于右端点在 [mid+1,p-1] 的区间,maxminl 都已知,可以推算出 r 进行单点加。

对于右端点在 [p,R-1] 的区间,maxl 已知,我们要给那些在 [p,R-1]max+l=min+r 的位置进行加一。再次利用结论,我们可以知道这样的位置只可能是 min+r 的最大值所在位(不取等也只能取大于)。所以需要线段树维护 a_i 最大值,a_i 最大值个数,区间 a_i 最大值位置的 b_i 加一(如果为给定的 max+l),区间求 b_i 的和。

反向同理。

提交记录:https://mirror.codeforces.com/problemset/submission/997/301081018

结语

历史和线段树对信息的压缩程度更高,在条件允许的情况下应当优先使用;时间上分治会略慢一倍,但分治也不失为这类题目的另一种解法(并且子区间最大子段和只能分治)。

如有疑问或勘误烦请评论区指出,谢谢阅读。