NOIP T4 题解

· · 题解

题意

给定 A_{1, \dots, n}, B_{1 \dots n}, 以及 m 个提问, 每次提问给出 l, r, 求

\sum_{p = l}^r \sum_{q = p}^r \bigl(\max\nolimits_{i=p}^q A_i\bigr)\bigl(\max\nolimits_{i=p}^q B_i\bigr).

题解

我们离线所有询问, 对右端点 r 进行扫描线.

在扫描过程中, 我们设 X_lY_l 分别表示

事实上应该是 $X_{l, r}$ 和 $Y_{l, r}$. 我们只是简记. 在扫描右端点的同时, 我们维护 $A, B$ 的单调栈. 这样如果扫描到 $i$, 轮到 $i$ 入栈时, 设两个栈顶分别是 $u, v$, 那么 $u+1, \dots, i$ 区间的 $X$ 会区间修改为 $A_i$, $v+1, \dots, i$ 区间的 $Y$ 会区间修改为 $B_i$. 如果我们要查询的 $l, r$ 的答案, 那么相当于在扫描到 $r$ 的时候, 查询 $l, \dots, r$ 区间的 _历史 $X \times Y$ 和_. 这么说可能有点奇怪, 不太好谈. 我们可以在扫描的时候, 对每个 $l$, 维护 $$S_{l, r} = \sum_{r' = l}^r X_{l, r'} \times Y_{l, r'}.$$ 这样的话, 我们要查询的就是 $l, \dots, r$ 的区间 $S$ 和. 而我们的操作则是区间 $X$ 修改 (覆盖), 区间 $Y$ 修改 (覆盖), 以及**区间 $S \mathrel{+}= X \times Y$**. 因此我们可以用线段树维护. 复杂度 $O(n \log n)$. ### 细节 我们发现 tag 是若干区间 $X$ 修改 (覆盖), 区间 $Y$ 修改 (覆盖), 以及区间 $S \mathrel{+}= X \times Y$ 的复合, 可以维护为 $\mathrm{Tag}(s_X, s_Y, a_X, a_Y, a_{XY}, a)$, 表示 $$\begin{aligned} S' &= S + a_XX + a_YY+a_{XY}X \times Y+a \\ X' &= \begin{cases} X & s_X = 0 \\ s_X & s_X \neq 0\end{cases} \\ Y' &= \begin{cases} Y & s_Y = 0 \\ s_Y & s_Y \neq 0\end{cases} \end{aligned}$$ 也就是说 $s_X, s_Y$ 表示 $X, Y$ 的区间覆盖, 而 $a_X, a_Y, a_{XY}, a$ 分别表示 $S$ 加上对应倍的 $X, Y, X \times Y, 1$. 我们要维护区间 $S$ 和, 结合上面的 $\mathrm{Tag}$ 就知道我们还要同时维护区间 $X$ 和, 区间 $Y$ 和以及区间 $X \times Y$ 和. 剩下的具体看代码. ## 代码 ```cpp #include <algorithm> #include <cctype> #include <cstdio> #include <cstring> int read() { int ans = 0, c; while (!isdigit(c = getchar())); do ans = ans * 10 + c - '0'; while (isdigit(c = getchar())); return ans; } typedef unsigned long long ULL; struct Msg { ULL sumX, sumY, sumXY, sumS; Msg() : sumX(0), sumY(0), sumXY(0), sumS(0) {} Msg(ULL sx, ULL sy, ULL sxy, ULL sb) : sumX(sx), sumY(sy), sumXY(sxy), sumS(sb) {} inline Msg operator+(const Msg &t) const { return Msg(sumX + t.sumX, sumY + t.sumY, sumXY + t.sumXY, sumS + t.sumS); } }; struct Tag { // first add, then set ULL addX, addY, addXY, addC; // S += addX * X + addY * Y + addXY * XY + addC ULL setX, setY; // = 0: not set Tag() : addX(0), addY(0), addXY(0), addC(0), setX(0), setY(0) {} Tag(ULL ax, ULL ay, ULL axy, ULL ac, ULL sx, ULL sy) : addX(ax), addY(ay), addXY(axy), addC(ac), setX(sx), setY(sy) {} operator bool() const { return addX || addY || addXY || addC || setX || setY; } // check if tag is non trivial // tag1 * tag2: first apply tag2, then apply tag1 inline Tag operator*(const Tag &t) const { ULL ax = t.addX, ay = t.addY, axy = t.addXY, ac = t.addC; ULL sx = t.setX, sy = t.setY; if (sx) { ac += addX * sx; if (sy) { ac += addXY * sx * sy; } else { ay += addXY * sx; } } else { ax += addX; if (sy) { ax += addXY * sy; } else { axy += addXY; } } if (sy) { ac += addY * sy; } else { ay += addY; } ac += addC; if (setX) sx = setX; if (setY) sy = setY; return Tag(ax, ay, axy, ac, sx, sy); } inline Msg apply(const Msg &m, ULL len) const { // len: length of range return Msg(/* sumX */ setX ? setX * len : m.sumX, /* sumY */ setY ? setY * len : m.sumY, /* sumXY */ setX ? (setY ? setX * setY * len : setX * m.sumY) : (setY ? m.sumX * setY : m.sumXY), /* sumS */ m.sumS + addX * m.sumX + addY * m.sumY + addXY * m.sumXY + addC * len); } }; const int N = 250050; const int NN = 550000; Tag tag[NN]; Msg msg[NN]; inline void upd(int o, int l, int r) { msg[o] = tag[o].apply(msg[o << 1] + msg[o << 1 | 1], r - l + 1); } inline void app(int o, int l, int r, const Tag &t) { tag[o] = t * tag[o]; msg[o] = t.apply(msg[o], r - l + 1); } inline void pushd(int o, int l, int r) { if (tag[o]) { int m = (l + r) / 2; app(o << 1, l, m, tag[o]); app(o << 1 | 1, m + 1, r, tag[o]); tag[o] = Tag(); } } void Modify(int o, int l, int r, int L, int R, const Tag &t) { if (L <= l && r <= R) { app(o, l, r, t); return; } pushd(o, l, r); int m = (l + r) / 2; if (L <= m) Modify(o << 1, l, m, L, R, t); if (R > m) Modify(o << 1 | 1, m + 1, r, L, R, t); upd(o, l, r); } ULL QueryS(int o, int l, int r, int L, int R) { if (L <= l && r <= R) return msg[o].sumS; pushd(o, l, r); int m = (l + r) / 2; ULL ans = 0; if (L <= m) ans += QueryS(o << 1, l, m, L, R); if (R > m) ans += QueryS(o << 1 | 1, m + 1, r, L, R); return ans; } struct Qry { int l, r, id; bool operator <(const Qry &t) const { return r < t.r; } } Q[N]; int n, m, A[N], B[N]; int sA[N], sB[N]; ULL ans[N]; int main() { read(); n = read(); for (int i = 1; i <= n; ++i) A[i] = read(); for (int i = 1; i <= n; ++i) B[i] = read(); // Init(1, 1, n); m = read(); for (int i = 0; i < m; ++i) { Q[i].l = read(); Q[i].r = read(); Q[i].id = i; } std::sort(Q, Q + m); int lA = 0, lB = 0; for (int i = 1, j = 0; i <= n; ++i) { while (lA && A[sA[lA]] < A[i]) --lA; while (lB && B[sB[lB]] < B[i]) --lB; Modify(1, 1, n, sA[lA] + 1, i, Tag(0, 0, 0, 0, A[i], 0)); // set X Modify(1, 1, n, sB[lB] + 1, i, Tag(0, 0, 0, 0, 0, B[i])); // set Y Modify(1, 1, n, 1, i, Tag(0, 0, 1, 0, 0, 0)); // S += X * Y sA[++lA] = sB[++lB] = i; for (; j < m && Q[j].r == i; ++j) ans[Q[j].id] = QueryS(1, 1, n, Q[j].l, i); } for (int i = 0; i < m; ++i) printf("%llu\n", ans[i]); } ```