题解：P10637 BZOJ4262 Sum

THUPOST_REMAKE · 2024-08-26 12:33:04 · 题解

本题解介绍的是不依赖序列随机特性的“序列扫描线+维护线段树历史和”的做法。时间复杂度为 O((n+q)\log n)。相较于 seg-beats，个人更推荐使用线段树历史和的做法进行练习。同时本题也可以作为 [NOIP2022] 比赛 的绝佳前置练习。

本文将具体介绍本题的具体思路，从矩阵乘法视角理解线段树历史和，线段树半群结构优化，以及其他类似习题的简单介绍。面向初学者会写的相对详尽一些。

本题题意

给定一个长度为 n 的非负整数序列 a 以及 q 组询问。每组询问为四个整数 l_1,r_1,l_2,r_2，求 \sum\limits _{l\in [l_1,r_1]}\sum\limits_{r\in [l_2,r_2]}(\max\limits_{i\in[l,r]}a_i-\min\limits_{i\in[l,r]}a_i) 。数据保证 1\le l_1\le r_1\le n,~1\le l_2\le r_2\le n。

题目思路

首先题目中的 \max 和 \min 这两项可以分开处理。另有 \min\limits_{i\in[l,r]} a_i=\max\limits_{i\in[l,r]}-a_i，所以我们可以统一按照 \max 处理，以原始的序列 a 以及全部取相反数之后的序列分别跑一遍得到的答案进行加和即为所求。此时问题变成了如何求解 \sum\limits _{l\in [l_1,r_1]}\sum\limits_{r\in [l_2,r_2]}\max\limits_{i\in[l,r]}a_i。

这个东西在线好像还是不太好求，我们可以考虑采用离线扫描线的思路来完成。将扫描线的过程分为两个维度，以按照 a_1,a_2,...,a_n 为顺序进行加点作为时间维，以通常的 [1,n] 区间作为序列维。我们称已经加入了 a_1,...,a_r 的时间称为时间版本 r 。此时维护序列上的第 i 个元素 x_i=\max\limits_{j\in[i,r]}(a_j) ，那么序列上 [l_1,r_1] 的区间和就有 \sum\limits_{i=l_1}^{r_1} x_i= \sum\limits_{l\in[l_1,r_1]}\max\limits_{i\in[l,r]} a_i。

显然，原始要求的 \sum\limits _{l\in [l_1,r_1]}\sum\limits_{r\in [l_2,r_2]}\max\limits_{i\in[l,r]}a_i 就变成了序列上 [l_1,r_1] 在时间版本 l_2,l_2+1,...,r_2 的区间和之和。又由于我们维护的答案具有可差分性，所以可以变成在 r_2 版本的历史和（即截止至 r_2 的所有时间版本 1,2,...,r_2 的区间和总和）减 l_1 版本的历史和。所以我们需要一个维护历史版本和的线段树即可。

接下来考虑扫描线的过程中，序列维度如何变化。考虑时间版本 r 当中，a_r 加入的过程。设 r 左侧第一个 l 满足 a_l>a_r ，则该序列上的 [l+1,r] 则会将 x_i 统一赋值为 r 。

但是维护区间赋值这个操作并不适合用线段树历史和来维护。那么我们可以考虑结合单调栈来维护 x_i 相同的连续段，将区间赋值操作转换为对若干个连续段的区间以及 [r,r] 的区间加操作（例：在 r 之前需要赋值为 a_r 的一段满足 x_i=k，则转成对该区间加 a_r-k）。不难证明区间加法的过程满足颜色段均摊，完整扫描过程的区间加法次数一定是 O(n) 的。

然后将所有查询挂在时间维的 l_2-1 和 r_2 上，边扫描边进行区间查询即可。

从矩阵视角理解线段树历史和

本题当中的线段树历史和需要完成以下操作：

维护序列 x 作为当前时间版本序列元素总和，\text{his} 作为截止至当前时间版本的历史总和。区间加法操作即对一个区间上的 x 统一加一个数 v，历史版本和刷新操作即对所有的 \text{his} 统一加上其对应位置的 x。

按照通常方式去思考需要一定的思维量，但是如果我们使用矩阵乘法的方式去理解就会轻松很多。

设对于线段树上的每个节点，我们要维护的是列向量 \left[\begin{matrix}\sum x_i\\l\\\sum \text{his}_i\end{matrix}\right]，其中 l 是当前节点代表序列区间的长度。则区间当前版本和以及区间历史和都可以直接通过维护列向量的加法求解。而上述两种操作我们也可以通过矩阵操作来完成。

对于区间加法操作，有：

对于刷新历史和操作，有：

此时的单位矩阵为 \left[\begin{matrix}1 & 0 & 0 \\0 & 1 & 0\\ 0& 0 & 1 \end{matrix}\right]，可以作为线段树的默认懒标记。于是我们已经可以在线段树上维护矩阵乘法，完成对历史和的维护了。

半群结构的优化

虽然对于本题来说，维护 3\times 3 的矩阵足以通过时间限制。但是不难发现，该过程的诸多运算过程都是冗余的。矩阵运算本身是一种有结合律无交换律的半群结构，那么我们在进行优化的时候，设计出来的半群结构只需要和原始运算完全一致即可。

那么我们就需要观察上述矩阵乘法当中，有哪些位置的元素是会发生变化的，那么我们的半群只需要包含这些元素即可。不难发现对于本题的矩阵 M，设左上角为第 0 行第 0 列时，只有 M_{01},M_{20},M_{21} 是有效的。所以我们的半群结构可以按照上述顺序，分别设置为 \{a,b,c\}。

接下来为该半群设计一个等价于矩阵乘法的运算，其实就是把这三个元素放回原本的矩阵当中，观察他们的变化是什么样的。

所以设两个半群 L=\{a,b,c\},R=\{a',b',c'\}，则有 L\times R=\{a+a',b+b',a'b+c+c'\}。该半群的单位元是 \{0,0,0\}。再次强调，由于该半群有结合律无交换律，所以一定要注意正确的运算顺序。

向量本身不需要优化，基于矩阵的优化半群和向量的运算类似上述处理即可，留给读者自己推导。本文给出的代码也是优化半群之后的版本。为了版面，完整代码放在最后。

此外，维护区间历史最值（见历史最值模板题）也可以先利用 \max,+ 广义乘法矩阵进行理解，再做优化。而由于 动态 DP 模板题 使用的也是 \max,+ 广义矩阵乘法，故类似的动态 DP 题目都可以使用类似方式进行半群的优化。

综上，我们以时间复杂度 O((n+q)\log n)，空间复杂度 O(n+q) 通过了本题。

拓展练习 1 : [NOIP2022] 比赛

开头就说了，本题是该拓展练习的绝佳前置练习。

给定长度 n 的序列 a,b，对于每次询问 [l,r] 求 \sum\limits_{l'\in[l,r]}\sum\limits_{r'\in[l,r]}(\max\limits_{i\in[l',r']}a_i\times \max\limits_{i\in[l',r']}b_i)。

基本就是把这题的一个序列扩展成两个序列。对于每个时间版本 r 设 x_i=\max\limits_{j\in[i,r]}a_i 和 y_i=\max\limits_{j\in[i,r]}b_i，维护当前版本的 \sum x_iy_i 以及其对应的区间和即可。而加入 a_r,b_r 时，类似本题转单调栈维护颜色段均摊，然后转区间对 x 加以及区间对 y 加。这两个操作对 \sum xy 的影响不难做。本题中需要维护 \begin{bmatrix} \text{his} \\ \sum xy \\ \sum x \\ \sum y \\ l \end{bmatrix} 这样的列向量，然后区间对 x 加，区间对 y 加，区间版本刷新也可以转成三个 5\times 5 的变换矩阵。

而由于单次矩阵乘法运算量 5^3 过大，类似上方做半群优化，可以发现矩阵上本质会变化的元素只有 9 个。完成半群优化之后即可通过本题。具体可参考其他人的题解。

拓展练习 2 : SPOJ GSS2

区间最大子段和，但是子段内相同的数只会贡献一次（比如选取子段是 1,1,4,5，那子段和就是 1+4+5=10）。

可以类似HH 的项链一题，记录每个位置 i 的前一个相同元素位置 \text{pre}_i。然后同样以序列加点顺序作为时间维，正常维护序列维。对于时间版本 r，序列维元素 x_i 代表 [i,r] 区间按照本题规则计算的子段和。则 \max\limits_{i\in[l,r]}x_i 则代表 [l,r] 在当前版本下的最大子段和。显然对该区间求历史最值即为本题所求。而加入 a_r 时的维护则考虑 x_i 的意义，直接对 [\text{pre}_r+1,r] 区间加 a_r 即可。具体可以参考其他人的题解，建议先完成历史最值模板题。

本题代码

const int N = 100010;
int n, q;
int a[N];
i64 ans[N];
namespace gen
{
    const int mod = 1000000000;
    i64 fst = 1023, sec = 1025;
    void init()
    {
        for (int i = 1; i <= n; ++i)
            a[i] = fst ^ sec, fst = fst * 1023 % mod, sec = sec * 1025 % mod;
    }
}
struct query
{
    int l1, r1, r, id, flag; // flag = 1 : add -1 : sub
    bool operator<(const query &o) const { return r < o.r; }
} qu[N];
// monotone stack
struct interval
{
    int l, r, mx;
} stk[N];
int stksz;
// history sum seg-tree
inline int lc(int u) { return u << 1; }
inline int rc(int u) { return (u << 1) | 1; }
struct vec
{
    i64 a, len, his;
    vec(i64 _a = 0, i64 l = 0, i64 h = 0) : a(_a), len(l), his(h) {}
    vec operator+(const vec &o) const { return vec(a + o.a, len + o.len, his + o.his); }
};
struct mat
{
    i64 a, b, c;
    mat() { a = b = c = 0; }
    mat(i64 _a, i64 _b, i64 _c) : a(_a), b(_b), c(_c) {}
    mat(i64 v, bool flag) { (flag ? (b = 1, a = 0) : (a = v, b = 0)), c = 0; } // flag 1 : his = his + a 0 : a += v
    mat operator*(const mat &o) const { return mat(a + o.a, b + o.b, o.a * b + c + o.c); }
    vec operator*(const vec &o) const { return vec(o.a + a * o.len, o.len, b * o.a + c * o.len + o.his); }
};
struct node
{
    mat tag;
    vec info;
    void init(int val) { info = vec(val, 1, val); }
    void modify(const mat &v) { tag = v * tag, info = v * info; }
} tr[N << 2];
void pushup(int u) { tr[u].info = tr[lc(u)].info + tr[rc(u)].info; }
void pushdown(int u) { tr[lc(u)].modify(tr[u].tag), tr[rc(u)].modify(tr[u].tag), tr[u].tag = mat(); }
void build(int u, int l, int r)
{
    tr[u].tag = mat();
    if (l == r)
        return tr[u].init(0);
    int m = (l + r) >> 1;
    build(lc(u), l, m), build(rc(u), m + 1, r), pushup(u);
}
void modify(int u, int L, int R, int l, int r, const mat &v)
{
    if (L > r || R < l)
        return;
    if (l <= L && R <= r)
        return tr[u].modify(v);
    pushdown(u);
    int M = (L + R) >> 1;
    modify(lc(u), L, M, l, r, v), modify(rc(u), M + 1, R, l, r, v);
    pushup(u);
}
vec query_vec(int u, int L, int R, int l, int r)
{
    if (L > r || R < l)
        return vec();
    if (l <= L && R <= r)
        return tr[u].info;
    pushdown(u);
    int M = (L + R) >> 1;
    return query_vec(lc(u), L, M, l, r) + query_vec(rc(u), M + 1, R, l, r);
}
void clr() { build(1, 1, n), stksz = 0; }
void solve()
{
    int j = 1;
    while (!qu[j].r)
        ++j;
    for (int i = 1; i <= n; ++i)
    {
        // modify version r
        modify(1, 1, n, i, i, mat(a[i], 0));
        while (stksz && stk[stksz].mx < a[i])
            modify(1, 1, n, stk[stksz].l, stk[stksz].r, mat(a[i] - stk[stksz].mx, 0)), --stksz;
        ++stksz, stk[stksz] = {stk[stksz - 1].r + 1, i, a[i]};
        modify(1, 1, n, 1, n, mat(0, 1)); // add version r's sum to history.
        for (; j <= q && qu[j].r == i; ++j)
            ans[qu[j].id] += qu[j].flag * query_vec(1, 1, n, qu[j].l1, qu[j].r1).his;
    }
}
int main()
{
    n = 100000, gen::init();
    q = rd();
    for (int i = 1; i <= q; ++i)
    {
        int l1 = rd(), r1 = rd(), l2 = rd(), r2 = rd();
        qu[(i << 1) - 1] = {l1, r1, l2 - 1, i, -1}, qu[i << 1] = {l1, r1, r2, i, 1};
    }
    q <<= 1, std::sort(qu + 1, qu + q + 1);
    clr(), solve();
    for (int i = 1; i <= n; ++i)
        a[i] = -a[i];
    clr(), solve();
    q >>= 1;
    for (int i = 1; i <= q; ++i)
        wr(ans[i]), putchar('\n');
}