题解：ARC169F Large DP Table

题意

给定长度为 \(n\) 的序列 \(a,b,x,y\)，保证 \(a_1=1,b_1=2\)，且 \(a_1,\cdots,a_n,b_1,\cdots,b_n\) 恰好构成长度为 \(2n\) 的排列。定义

\[d_{i,j}=\begin{cases} 0&(i,j)=(1,1)\\ d_{i,j-1}+x_i&(i,j)\neq (1,1)\land a_i<b_j\\ d_{i-1,j}+y_j&(i,j)\neq (1,1)\land a_i>b_j \end{cases} \]

求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^nd_{i,j}\)。

题解

对于每个点 \((i,j)\)，从 \((i-1,j)\) 或者 \((i,j-1)\) 向 \((i,j)\) 连一条有向边，得到一张网格图。考虑对于每个 \(x_i,y_i\) 计算贡献，下面以 \(x_i\) 为例。

只有满足 \(a_i<b_j\) 的位置 \((i,j)\) 会在后面的递推过程中产生对 \(x_i\) 的贡献，而贡献系数实际上就是 \((i,j)\) 能到达多少点 \((p,q)\)，于是问题转化为求上述贡献系数。

正难则反，尝试刻画 \((i,j)\) 无法到达 \((p,q)\) 的条件。注意到点的入度为 \(1\)，考虑沿着点的唯一入边反向回溯，则从 \((p,q)\) 出发的反向路径必然不会经过 \((i,j)\)。不妨设这条反向路径会从 \((i,k)(k>j)\) 处向上穿出边界，且穿出边界前最后一个向上走的极长段是从 \((u,k)\) 向上走到 \((i,k)\)，其中 \(u\geq i\)。这说明 \(\forall i\leq r\leq u,a_r>b_k\)。同时，我们发现一个形如 \((i,j-1)\to (i,j)\to (i+1,j)\) 的拐点可以导出 \(a_i<b_j<a_{i+1}\)，因此 \(\forall u<r\leq p,a_r>a_{r-1}>b_k\)。综上，我们可以得出 \(\min\{a_{i\sim p}\}>b_k\)。类似讨论可以得出，若这条反向路径会从 \((k,j)(k>i)\) 处向左穿出边界，则 \(\min\{b_{j\sim q}\}>a_k\)。

现在我们得到了一个充分条件：\(\min\{a_{i\sim p}\}>b_k\lor \min\{b_{j\sim q}\}>a_k\)。注意到，这两个条件在网格图上相当于第 \(k-1\) 列和第 \(k\) 列之间没有连边，或者第 \(k-1\) 行和第 \(k\) 行之间没有连边，因此若这两个式子之中有一个成立，\((i,j)\) 也必然无法到达 \((p,q)\)，因此这个条件事实上是充要的！

由此可以得到，\((i,j)\) 可以到达 \((p,q)\) 的充要条件为：

\[(\forall j<k\leq q,b_k> \min\{a_{i\sim p}\})\land (\forall i<k\leq p,a_k> \min\{b_{j\sim q}\}) \]

结合 \(a_i<b_j\)，上述条件等价于：

\[a_i<\min\{b_{j\sim q}\}<\min\{a_{i+1\sim p}\} \]

设 \(f_i\) 表示有多少区间 \([l,r]\) 满足 \(\min\{b_{l\sim r}\}\geq i\)，则我们相当于要求：

\[x_i\left(f_{a_i}+\sum_{p=i+1}^n[a_i<\min\{a_{i+1\sim p}\}](f_{a_i}-f_{\min\{a_{i+1\sim p}\}})\right) \]

注意这里加上 \(f_{a_i}\) 是为了补上 \(p=i\) 时的贡献。

\(f\) 容易单调栈后预处理后缀和求出。注意到 \(a_i<\min\{a_{i+1\sim p}\}\) 对应的 \(\min\{a_{i+1\sim p}\}\) 的值，恰好是在由 \(a_{i+1\sim n}\) 构建的单调栈中插入 \(a_i\) 时弹出的那些值，于是套路地在弹栈时累计答案即可。

\(a_i>b_j\) 的情况是类似的。注意由于 \(d_{1,1}=0\)，最后答案需要减去 \(n^2x_1\)。

主要代码

int n, a[N], b[N], x[N], y[N];
int top, stk[N], prv[N], nxt[N];
mint ans, f[N], g[N];int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 1; i <= n; ++i) cin >> x[i];for (int i = 1; i <= n; ++i) cin >> y[i];fill(nxt + 1, nxt + n + 1, n + 1);for (int i = 1; i <= n; ++i) {while (top && b[stk[top]] > b[i]) nxt[stk[top--]] = i;prv[i] = stk[top], stk[++top] = i;}for (int i = 1; i <= n; ++i) f[b[i]] = (ll)(i - prv[i]) * (nxt[i] - i);for (int i = n << 1; i; --i) f[i] += f[i + 1];fill(nxt + 1, nxt + n + 1, n + 1);top = 0;for (int i = 1; i <= n; ++i) {while (top && a[stk[top]] > a[i]) nxt[stk[top--]] = i;prv[i] = stk[top], stk[++top] = i;}for (int i = 1; i <= n; ++i) g[a[i]] = (ll)(i - prv[i]) * (nxt[i] - i);for (int i = n << 1; i; --i) g[i] += g[i + 1];stk[top = 0] = n + 1;for (int i = n; i; --i) {ans += x[i] * f[a[i]];while (top && a[i] < a[stk[top]]) {ans += x[i] * (f[a[i]] - f[a[stk[top]]]) * (stk[top - 1] - stk[top]);--top;}stk[++top] = i;}stk[top = 0] = n + 1;for (int i = n; i; --i) {ans += y[i] * g[b[i]];while (top && b[i] < b[stk[top]]) {ans += y[i] * (g[b[i]] - g[b[stk[top]]]) * (stk[top - 1] - stk[top]);--top;}stk[++top] = i;}cout << ans - mint(x[1]) * n * n;return 0;
}