2023.11.26 模拟赛
T1
给定数列 \(a_{1, \cdots, n}, b_{1, \cdots, m}\)，一个 \(n \times m\) 的矩阵 \(W\) 满足 \(W_{i, j} = a_i + b_j\)。
给定常数 \(x\)，问满足 \(W_{i, j} \le x\) 的所有格子 \((i, j)\) 形成的四连通块数量。
\(1 \le n, m, x, a_i, b_j \le 2 \times 10 ^ 5\)。
对于每一个连通块，必然有至少一行、至少一列贯穿了整个块，因为行与行、列与列之间 \(W_{i, j} \le x\) 的格子呈包含关系。
用一个连通块中数字最小的格子代表这个连通块。如果有多个选择最左边那个，仍有多个选择最上面那个。反证法容易证明先向上找再向左找会到达同一个格子。
考虑预处理出如下信息：
-
\(up_i\) 为最大的 \(1 \le i' < i\)，使 \(W_{i', j} \le W_{i, j}\)，若不存在则 \(up_i = i\)。
-
\(lf_j\) 为最大的 \(1 \le j' < j\)，使 \(W_{i, j'} \le W_{i, j}\)，若不存在则 \(lf_j = j\)。
-
\(dn_i\) 为最小的 \(i < i' \le n\)，使 \(W_{i', j} < W_{i, j}\)，若不存在则 \(dn_i = i\)。
-
\(rg_j\) 为最小的 \(j < j' \le m\)，使 \(W_{i, j'} < W_{i, j}\)，若不存在则 \(rg_j = j\)。
容易发现如果一个格子 \((i, j)\) 能够代表一个连通块，仅当 \(up_i, dn_i\) 要么等于 \(i\)，要么和 \((i, j)\) 不在同一个连通块，\(lf_j, rg_j\) 同理。
定义 \(l > r\) 时 \(\max\limits_{l \le p \le r} a_p = +\infty\)。那么 \((i, j)\) 能代表连通块时：
\[\begin{cases} a_i + b_j \le x \\ a_i + \max\limits_{lf_j < p \le j} b_p > x \\ a_i + \max\limits_{j \le p \le rg_j} b_p > x \\ \max\limits_{up_i < p \le i} a_p + b_j > x \\ \max\limits_{i \le p < dn_i} a_p + b_j > x \end{cases} \]记 \(f_i = \min (\max\limits_{up_i < p \le i} a_p, \max\limits_{i \le p < dn_i} a_p), g_j = \min (\max\limits_{lf_j < p \le j} b_p, \max\limits_{j \le p \le rg_j} b_p)\)。条件简化为：
\[\begin{cases} x - f_i < b_j \le x - a_i \\ g_j > x - a_i \end{cases} \]将 \((b_j, g_j)\) 看作平面上的点，于是就是经典的二维数点问题，离线树状数组即可。
Code of T1
#include <bits/stdc++.h>
const int M = 2e5 + 10;
const int LIM = 200001;
int n, m, x, a[M], b[M], f[M], g[M];
int lf[M], rg[M], up[M], dn[M], stk[M], top;
void getdirqwq() {
stk[top = 0] = 0;
for (int i = 1; i <= n; i++) {
while (top && a[i] < a[stk[top]]) top--;
up[i] = top ? stk[top] : i, stk[++top] = i;
}
stk[top = 0] = 0;
for (int i = 1; i <= m; i++) {
while (top && b[i] < b[stk[top]]) top--;
lf[i] = top ? stk[top] : i, stk[++top] = i;
}
stk[top = 0] = n + 1;
for (int i = n; i >= 1; i--) {
while (top && a[i] <= a[stk[top]]) top--;
dn[i] = top ? stk[top] : i, stk[++top] = i;
}
stk[top = 0] = m + 1;
for (int i = m; i >= 1; i--) {
while (top && b[i] <= b[stk[top]]) top--;
rg[i] = top ? stk[top] : i, stk[++top] = i;
}
}
int _lg2[M];
struct STalbe {
int st[20][M];
void Build(int* a, int n) {
for (int i = 1; i <= n; i++) st[0][i] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[j][i] = std::max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int Qmax(int l, int r) {
if (l > r) return LIM;
int k = _lg2[r - l + 1];
return std::max(st[k][l], st[k][r - (1 << k) + 1]);
}
} sA, sB;
struct BIT {
int c[M];
void Add(int x, int v) {
for (; x <= LIM; x += (x & -x)) c[x] += v;
}
int Ask(int p) {
int ans = 0;
for (; p; p -= (p & -p)) ans += c[p];
return ans;
}
} T;
long long ans;
struct Query {
int pos, bot, v;
bool operator < (const Query& o) const {
return pos < o.pos;
}
} q[M << 1];
std::vector<int> pt[M];
int cntq;
int main() {
freopen("cloud.in", "r", stdin);
freopen("cloud.out", "w", stdout);
_lg2[0] = -1;
for (int i = 1; i < M; i++) _lg2[i] = _lg2[i >> 1] + 1;
scanf("%d%d%d", &n, &m, &x);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
getdirqwq();
sA.Build(a, n), sB.Build(b, m);
for (int i = 1; i <= n; i++)
f[i] = std::min(sA.Qmax(up[i] + 1, i), sA.Qmax(i, dn[i] - 1));
for (int j = 1; j <= m; j++)
g[j] = std::min(sB.Qmax(lf[j] + 1, j), sB.Qmax(j, rg[j] - 1));
for (int j = 1; j <= m; j++) pt[b[j]].push_back(g[j]);
for (int i = 1; i <= n; i++) {
if (x - a[i] < 1) continue;
q[++cntq] = { x - a[i], x - a[i], 1 };
if (x - f[i] >= 0) q[++cntq] = { x - f[i], x - a[i], -1 };
}
std::sort(q + 1, q + 1 + cntq);
for (int i = 1; i <= cntq; i++) {
for (int j = q[i - 1].pos + 1; j <= q[i].pos; j++)
for (int x : pt[j]) T.Add(x, 1);
ans += q[i].v * (T.Ask(LIM) - T.Ask(q[i].bot));
}
printf("%lld\n", ans);
return 0;
}