P8868 比赛 题解

· · 个人记录

传送门

题意简述：给定序列 a,b 和 m 次查询，每次询问 \displaystyle\sum_{i=l_i}^{r_i}\sum_{j=i}^{r_i}(\max_{k=i}^j a_k\times \max_{k=i}^jb_k)。

## 【8pts：暴力】 暴力枚举。 ## 【20pts：关注贡献集合的变化，O(1)更新】 离线，右端点排序，假设此时循环到右端点为 $r$。 定义：$x_i=\max\limits_{j=i}^r\{a_j\}$，$y_i$ 类似定义。$f_i=x_i\times y_i$。 在右端点为 $r$ 时，我们发现，$f_i$ 就是当 $p=i,q=r$ 时的答案。 于是在右端点为 $r$ 时，$\displaystyle\sum_{i=l}^rf_i$ 就是当 $p=l,l+1,\dots,r,q=r$ 时的答案。 再进一步，在右端点为 $l,l+1,\dots,r$ 的时候，所有 $\displaystyle\sum_{i=l}^r f_i$ **的和**就是询问 $(l,r)$ 的答案。 但是如果我们在当前求 $f_i$ 时，要找出所有包含 $f_i$ 的询问累加，实在是太麻烦，太慢了。 因此可以**转而在 $f_i$ 上累加贡献**：当右端点为 $r$ 时，令 $F_i$ 代表 $p=i,q=i\sim r$ 时的答案和。（**注意，这里变的是右端点，左端点不变**） 因为**左端点不变**，所以 $r\leftarrow r+1$ 时， $F_i$ 中 $\sum [i,i\sim r]$ 的部分**不会变**，我们只需加入 $[i,r+1]$ 的贡献，也就是 $\displaystyle\max_{j=i}^{r+1}a_j\times \max_{j=i}^{r+1}b_j=x_i\times y_i$，可以 $O(1)$ 求得。 在 $r$ 右移时，更新是： ``` x[i] = max(x[i], x[r]); y[i] = max(y[i], y[r]); F[i] += x[i] * y[i]; //注意这里的 += ``` 答案就是： ``` for (int i = l; i <= r; i++) ans[id] += F[i]; ``` 因为 $x,y,F$ 都要随着 $i$ 的右移更新多次，所以 $x,y,F$ 的更新是 $O(n^2)$ 的；每次询问要循环，所以询问复杂度 $O(n)$。总复杂度 $O(n^2+nq)$。 ### 【小 Question】 为什么上面 $F_i$ 定义为 $p=i,q=i\sim r$ 的答案的和，而非 $p=i\sim r,q=r$ 的答案的和？ 因为这样在 $r$ 右移的过程中，$F_i$ 的定义中 $p,q$ 都与 $r$ 有关系，我们就需要补充 $[i\sim r+1,r+1]$ 的贡献。前一种定义只需要补充 $[i,r+1]$ 的贡献，因为 $p$ 与 $r$ 无关。 ## 【100pts】 一个很显眼的优化就是可以用线段树维护 $x,y$：先用单调栈预处理每个数左边大于它的数，然后区间赋值。 接下来尝试用线段树维护 $F_i$，这样对于询问 $[l,r]$，我们能 $O(\log n)$ 的求出 $\sum F_i$。 我们只有三种操作：区间赋值 $x$，区间赋值 $y$，区间加上这个区间内所有单个位置的 $x\times y$（简记为区间 $+x\times y$）。 考虑我们要对一个节点保存什么信息： 1. 答案 $ans$，也就是这个区间的 $F_i$ 和。 2. 区间内每个位置 $X\times Y$ 的和 $sumxy$，这样方便执行区间 $+x\times y$。 3. 区间内 $x$ 的和 $sumx$，区间内 $y$ 的和 $sumy$。这样在区间赋值 $x,y$ 的时候，能快速更新 $sumxy$。 然后考虑一个标记保存什么信息： 1. $setx,sety$ 显然需要，即区间赋值 $x,y$ 的标记。 2. $addxy$，即这个区间应当加上 $addxy$ 个 $x\times y$。 虽然上面两个标记已经包含了题目的信息，但是当两个标记碰在一起的时候，我们发现无法规定一个合适的优先级，使得两个标记能等价地合并成一个标记。 比如：当我们有一个 $+1\;x\times y$ 的标记，但是遇到了 $setx$ 标记。此时的 $addxy$ 如果还是 $1$，加出来的 $x\times y$ 就是 $set$ 之后的 $x\times y$ 了，肯定不对；但是这一个 $+1\;x\times y$ 的增加也不能丢掉，不然答案又少了。 这样就卡住了。 那怎么办呢？**当你发现线段树的标记无法完美合并的时候，可以考虑一下多记录一些信息。** 考虑我们上面遇到的问题：当 $addxy$ 遇到 $set$ 的时候，没有地方可以存原先的 $addxy$ 了！ 因此我们考虑设置一个暂存点：$addC$，表示这个区间**每一个位置的答案**都要加上 $addC$ 这么多**数值**，总答案也就是加上 $addC\times len$ 的数值。 > 错误示范：如果 $addxy$ 遇到 $set$，我们可以调用这个标签所在的节点的 $x\times y$ 值，加入 $addC$ 中，同时 $addxy\leftarrow 0$。 这是不对的！ # 线段树的 Tag*Tag，一定不能涉及到 Val 的属性！！！ 因为当我们 pushdown 的时候，Val 的属性就会变化，Tag 也要跟着变，太麻烦了！ 发现增加了一个 $addC$ 还是不能合并，原因在于：**如果 pushdown 了，$addC$ 不能同时加到两个子区间上，因为这个 $addC$ 是大区间的 $addC$，小区间需要根据小区间自己的 $sumx,sumy$ 增加。** 既然小区间需要根据小区间的 $sumx,sumy$ 打标记，我们自然想到在 Tag 上再额外记录两个信息：$addx,addy$，表示这个区间需要 $+addx\times sumx,+addy\times sumy$。 这样就对了，当 $addxy$ 遇到 $set$ 的时候，可以通过 $set$ 的值，把增加的倍数加入 $sumx,sumy$ 里面。 ## 同时，我们规定：一个 Tag，加法操作的优先级高于赋值操作。比如 Tag:adx=3,covx=2，加的是原来的sumx，不是covx*len # 【总结】 Val 包含的信息： 1. ans，答案； 2. sumX，区间内 X 的和； 3. sumY，区间内 Y 的和； 4. sumXY，区间内 X*Y 的和。 Tag 包含的信息（**加法的优先级高于赋值**）： 1. setx, sety：X，Y 的赋值信息； 2. addXY：这个区间加了多少次 X*Y； 3. addX：这个区间加了多少次 sumX； 4. addY：这个区间加了多少次 sumY； 5. addC：这个区间的答案要加上 addC*len。 所以一个区间的答案就是 $ans+addXY\times sumXY+addX\times sumX+addY\times sumY+addC\times len.

Tag * Tag 怎么写？用标记队列的思想。