[NOIP2022] 比赛 - 洛谷 P8868
给定长度为 \(n\) 的序列 \(a, b\) ，令 \(F(p, q) = \max\limits_{i = l}^r \{ a_i\} \cdot \max\limits_{i = l}^r \{b_i\}\)。
现在有 \(T\) 组询问，每次给定 \(l, r\)，求 \(\sum\limits_{l \le p \le q \le r} F(p, q)\)。
\(n, T \le 2.5 \times 10^5\)
首先将问题离线下来，让 \(r\) 从 \(1\) 移动到 \(n\)，维护 \(ans_l\)。
考虑 \(r - 1\) 到 \(r\) 的过程 \(ans_l\) 的变化：只需要考虑 \(q = r\) 的情况即可。我们令 \(f_p\) 表示 \(\sum F(p, q)\)，那么其实 \(ans_l = \sum\limits_{p = l}^r f_p\)。
所以只需要求 \(f_p\) 的变化量 \(F(p, r)\) 即可。于是你就获得了一个 \(O(n(n + q))\) 的做法，获得了 \(20pts\) 的高分。
考虑优化，首先我们要处理一下 \(F(p, r)\) 这个复杂的东西。看到这种关于区间 max/min 的，不难想到单调栈。令 \(x_p = \max\limits_{i = p}^r \{a_i\}, y_p = \max\limits_{i = p}^r \{b_i\}\)，那么相当于区间赋值 \(x_p, y_p\)，区间加 \(x_p \cdot y_p\)，以及区间求和。
那我们来看看要维护什么？
首先是 \(\sum f, \sum x_p \cdot y_p\)，那么要维护支持区间赋值，还需要维护 \(\sum x_p, \sum y_p\) 似乎就够了，于是你可能就得到了一个 \(O(n \sqrt n)\)
的分块做法（口胡的。）对于每个块打一个修改 \(x, y\) 的标记以及修改的时间，修改散块时好计算差值。
但这个做法太垃圾了，所以我们直接上线段树。
知道我们维护的信息，那么接下来就是要维护的懒标记了。首先肯定有区间覆盖的标记 \(cx, cy\)（\(= 0\) 代表没有覆盖的操作），以及区间加 \(x \cdot y\) 的次数 \(add\)。
然后发现无法下传标记，因为这个 \(add\) 对应加的 \(xy\) 每次都可能不一样，也就是交替出先覆盖、区间加操作，一个变量是无法记下来的。
回想一下 CPU 监控 那个题，我们是将懒标记序列分成了加和赋值两个部分，其实这个题也有相似的地方。
对于一个懒标记而言，如果被区间覆盖了 \(x\)，那么以后的 \(x\) 都会是一样的，所以如果 \(x\) 被覆盖过了，后面的区间加法中的 \(x\) 部分是可以直接加起来的，\(y\) 同理。而如果没有区间覆盖 \(x\) 的标记，那么就是原来的 \(x\)，也是比较处理的。
所以，我们就有了一个大致思路。对于 \(x, y\) 都分成未被覆盖过和被覆盖过，前一个部分就是下传前的值，后有一个部分又可以累加，就比较舒服了。
所以我们的 \(tag\) 总共就有 \(6\) 个了，cx, cy, addx, addy, addxy, add1，表示 f[i] += addx * x[i] + addy * y[i] + addxy * x[i] * y[i] + add1，也就是 \(4\) 个部分的系数。懒标记合并时根据原本的 cx, cy 是否等于 \(0\)（是否有标记） 分类讨论一下即可。
注意要先下传 add 标记，再进行赋值。因为 add 标记的含义是原先 x[i], y[i] 的系数。
时间复杂度：\(O((n + T) \log n)\)。
还是挺困难的一个题，可能是因为这种版本历史和的题做的不多的缘故。发现一个规律：覆盖操作可以一般都可以分成第一次覆盖前/后分别计算。
struct Tag {// 先加，再覆盖ll cx, cy, addx, addy, addxy, add1; // 覆盖标记，加标记：f[i] += x[i] * addx + y[i] * addy + x[i] * y[i] * addxy + add1
} lzy[MAXN * 4];struct SegTree {ll sum, sxy, sx, sy; // sum(f), sum(x * y), sum(x), sum(y)
} tr[MAXN * 4];void update(int x, int len, Tag &t) {// 先下传 add 标记tr[x].sum += t.addx * tr[x].sx + t.addy * tr[x].sy + t.addxy * tr[x].sxy + t.add1 * len;if (lzy[x].cx && lzy[x].cy) { // 如果本身两个标记都有，那么原本的 x, y 就没有了，只有 add1 有值。lzy[x].add1 += t.add1 + t.addx * lzy[x].cx + t.addy * lzy[x].cy + t.addxy * lzy[x].cx * lzy[x].cy;} else if (lzy[x].cx) {lzy[x].addy += t.addy + t.addxy * lzy[x].cx;lzy[x].add1 += t.add1 + t.addx * lzy[x].cx;} else if (lzy[x].cy) {lzy[x].addx += t.addx + t.addxy * lzy[x].cy;lzy[x].add1 += t.add1 + t.addy * lzy[x].cy;} else {lzy[x].addx += t.addx;lzy[x].addy += t.addy;lzy[x].add1 += t.add1;lzy[x].addxy += t.addxy;}// 再下传覆盖的标记if (t.cx) {lzy[x].cx = t.cx;tr[x].sx = t.cx * len, tr[x].sxy = tr[x].sy * t.cx;}if (t.cy) {lzy[x].cy = t.cy;tr[x].sy = t.cy * len, tr[x].sxy = tr[x].sx * t.cy;}
}