NOIP T4 题解
_rqy
·
·
题解
题意
给定 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_l 和 Y_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]);
}
```