关于一类子区间计和问题
murder_drones
·
·
算法·理论
前言
笔者在做题时见到了一些相似的题目，他们都有这样的特点：给定一个序列，多组询问区间，每次回答该区间的所有子区间的 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
这是本文要着重讲解的分治做法。
单组询问
以子区间最大子段和之和为例讲解具体算法流程。
先写出区间最大子段和的式子表达：
$$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) 这个数对选不选抽象成一个点。如果原序列上的 i 和 i+1 之间的最值为 mx 和 mn，那么你选了 (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] 的区间，max，min，l 都已知，可以推算出 r 进行单点加。
对于右端点在 [p,R-1] 的区间，max，l 已知，我们要给那些在 [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
结语
历史和线段树对信息的压缩程度更高，在条件允许的情况下应当优先使用；时间上分治会略慢一倍，但分治也不失为这类题目的另一种解法（并且子区间最大子段和只能分治）。
如有疑问或勘误烦请评论区指出，谢谢阅读。