[NOIP 2022] T4 比赛 题解
CuiZhenhang
·
·
题解
本题解为线段树维护区间历史版本和做法，讲解自认为较详细。
题意
给定 a_{1,\dots,n}, b_{1,\dots,n}，以及 m 个询问, 每次询问给出 l, r 求：
\sum_{p=l}^{r}\sum_{q=p}^{r}(\max_{i=p}^{q}a_i) \times (\max_{i=p}^{q}b_i)
数据范围：n,m \leq 2.5 \times 10^5。
题解
52 pts 做法
发现 n \times m 为 10^6 级别，考虑接近 O(nm) 的做法。
对于区间最大值求和问题，一种常见的方法是考虑每个数的贡献。
所以，令 apre_i 表示 1 \sim i 中最大的 j 满足 a_j \gt a_i，bpre_i 同理。
依次考虑子区间右边界从 $l$ 到 $r$ 递增。
右边界 $q$ 确定时，为表示方便，令 $A_p = \max_{i=p}^{q}a_i, B_p = \max_{i=p}^{q}b_i$。
可以发现，当右边界 $q$ 扩展到 $k$ 时，$A_p$ 在 $1 \sim apre_k$ 处的值不变，在 $apre_k + 1 \sim k$ 处的值变为 $a_k$。$B_p$ 同理。
因此，我们用线段树维护序列 $A_p, B_p$ 和 $\sum_{p=l}^{q}A_p \times B_p$，支持区间赋值 $A_p, B_p$。
答案为 $\sum_{q=l}^{r}(\sum_{p=l}^{q}A_p \times B_p)$。
总时间复杂度为 $O(m n \log n)$，预期 52 pts。
### 100 pts 做法
可以发现，当右边界 $q$ 扩展到 $k$ 时，序列的修改与询问的 $l$ 无关，且不会修改 $A_{k+1,\dots,n}, B_{k+1,\dots,n}$。
所以，右边界 $q$ 从 $1$ 开始还是从 $l$ 开始不会影响询问的答案。
由此可知，以下做法也是正确的：
$A_p, B_p$ 初始值为 $0$。
令 $q$ 依次扩展到 $1 \sim n$，维护 $A_p, B_p, \sum A_p \times B_p$。
然后将所有 $r \ge q$ 的询问的答案增加 $\sum_{p=l}^{r}A_p \times B_p$。
因此，每一个询问的答案是 $r = q$ 时 $\sum_{p=l}^{r}A_p \times B_p$ 的历史版本和。
---
以下讲解如何维护区间历史版本和。
对于普通的区间历史版本和，2016 年集训队论文中有介绍。
类比着做，令 $S_i = A_i \times B_i$，设 $Ans_i$ 为历史版本和，同时我们让 $gt$ 为当前结束的时间（二者均不包含当前操作）。同样，定义 $C_i$，每一时刻结束都让 $C_i = Ans_i - gt \cdot S_i$。
令 $x'$ 表示修改前的 $x$ 信息，$\Delta x$ 表示修改前后 $x$ 的变化量。
$$\begin{aligned}\Delta C_i
&= \Delta Ans_i - \Delta(gt \cdot S_i) \\
&= \Delta gt \cdot S_i' - (gt' + \Delta gt)\cdot(S_i' + \Delta S_i) + gt' \cdot S_i' \\
&= -\Delta gt \cdot \Delta S_i -gt' \cdot \Delta S_i \\
&= -(gt' + \Delta gt) \cdot \Delta S_i \\
&= -gt \cdot \Delta S_i
\end{aligned}$$
维护线段树标记逻辑很麻烦，我们考虑借助矩阵理解。
先确定状态矩阵（行向量）如下：
$$\begin{bmatrix} \sum S_i & \sum A_i & \sum B_i & len & \sum C_i\end{bmatrix}$$
其中 $len$ 为当前区间的长度。
可得转移矩阵：
$$\begin{bmatrix}
[a=b=0] & 0 & 0 & 0 & c \\
[a=0]b & [a=0] & 0 & 0 & ca \\
[b=0]a & 0 & [b=0] & 0 & cb \\
a \cdot b & a & b & 1 & cl \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}$$
其中 $a$ 非零时表示将区间中所有 $A_i$ 赋值为 $a$，$b$ 同理，$c, ca, cb, cl$ 仅供计算。
该矩阵中左上 $4 \times 4$ 的部分和 $52$ pts 的标记是等价的，结合实际意义维护即可，而 $\sum C_i$ 我们选择用矩阵维护。
这里是我对该标记的实现：
```cpp
struct Tag {
ull a, b;
ull c, ca, cb, cl;
inline bool empty() const {
return !(a || b || c || ca || cb || cl);
}
inline void clear() {
a = b = 0;
c = ca = cb = cl = 0;
}
inline void add(const Tag &t) {
if (this->empty()) return (void) (*this = t);
// matrix 1
const ull a1s = a ? 0 : b, b1s = b ? 0 : a;
const ull a1a = a ? 0 : 1, b1b = b ? 0 : 1;
const ull l1s = a*b, l1a = a, l1b = b;
const ull s1c = c, a1c = ca, b1c = cb, l1c = cl;
// matrix 2
const ull s2c = t.c, a2c = t.ca, b2c = t.cb, l2c = t.cl;
// matrix result
const ull sc = s1c*1;
const ull ac = a1s*s2c + a1a*a2c + a1c*1;
const ull bc = b1s*s2c + b1b*b2c + b1c*1;
const ull lc = l1s*s2c + l1a*a2c + l1b*b2c + 1*l2c + l1c*1;
// assign
c = sc, ca = ac, cb = bc, cl = lc;
if (t.a) a = t.a;
if (t.b) b = t.b;
}
};
```
其中 `add` 方法为合并两个标记（转移矩阵）。
P.S. `add` 方法的代码复杂程度较高，建议以可读性为重点，相信现代编译器是完全能够优化这简单的逻辑的。
将标记应用于线段树上的节点：
```cpp
struct Node {
ull s, sa, sb, c;
Tag tag;
} tree[N*4+10];
inline void set_val(int p, int l, int r, const Tag &tag) {
Node &self = tree[p];
const ull len = r - l + 1;
const ull s = self.s, sa = self.sa, sb = self.sb;
if (tag.a && tag.b) {
self.s = tag.a * tag.b * len;
self.sa = tag.a * len;
self.sb = tag.b * len;
} else if (tag.a) {
self.s = tag.a * sb;
self.sa = tag.a * len;
} else if (tag.b) {
self.s = tag.b * sa;
self.sb = tag.b * len;
}
self.c += tag.c * s + tag.ca * sa + tag.cb * sb + tag.cl * len;
self.tag.add(tag);
// if (l < r) push_down(p, l, r);
// tree[p].tag = tag;
}
```
P.S. 这里有个调试的小技巧，因为合并两个标记很难调试，所以调试时通过再次下传标记避免合并，从而方便其它部分的调试。不过这会导致线段树时间复杂度 $O(n^2)$，但调试时可以接受。
当我们把一段区间的 $A_i$ 赋值为 $v$ 时，以上矩阵 $a = v, b = 0$。
$\sum C_i$ 可由 $\Delta C_i = -gt \cdot \Delta S_i$ 推导，得到 $c = gt, ca = 0, cb = -v \cdot gt, cl = 0$。
同理得把 $B_i$ 赋值为 $v$ 时，$a = 0, b = v, c = gt, ca = -v \cdot gt, cb = 0, cl = 0$。
所以扩展右边界时的代码如下：
```cpp
++cntR; // 扩展右边界
ull a = arr[cntR].val, b = brr[cntR].val, gt = cntR;
update(1, 1, n, arr[cntR].pre + 1, cntR, Tag { a, 0, gt, 0, -gt*a, 0 });
update(1, 1, n, brr[cntR].pre + 1, cntR, Tag { 0, b, gt, -gt*b, 0, 0 });
```
对于查询，注意 $Ans_i$ 是不包含当前操作的，所以查询的答案为 $\sum_{i=l}^{r} C_i + (gt + 1) \cdot S_i$。
总时间复杂度 $O(n \log n)$，预期 100 pts。
[完整代码](https://www.luogu.com.cn/paste/fm6c7wd4)。