题解：P13120 [GCJ 2019 #3] Pancake Pyramid

WorldMachine · 2026-03-27 09:58:29 · 题解

薄煎饼好吃。

类似接雨水，容易发现每个位置 i 的最终高度为前缀 \max 和后缀 \max 的较小值，因此代价为：

这个 \min 摆在这很不舒服，由于 \min(a,b)=a+b-\max(a,b)，上式化为：

求所有区间 [l,r] 的 W(l,r) 之和，考虑拆贡献。设 L_i 表示 i 左侧第一个 \color{red}\ge\color{#333333}a_i 的位置（没有则为 0），R_i 表示 i 右侧第一个 \color{red}>\color{#333333}a_i 的位置（没有则为 n+1），可以用单调栈 \mathcal O(n) 求出。

考虑 a_i 的贡献，为了方便，设 A=i-L_i，B=R_i-i：

1. 第四部分，包含 i 的区间共有 i(n-i+1) 个，贡献 -i(n-i+1)a_i；
2. 第三部分，要求 i 是 [l,r] 的区间最大值，条件是 l\in(L_i,i]\land r\in[i,R_i)，同时 a_i 会被计算 r-l+1 次，因此总次数为 \displaystyle\sum_{l=L_i+1}^i\sum_{r=i}^{R_i-1}(r-l+1)，用等差数列求和，贡献为 -\dfrac{AB(A+B)}2a_i；
3. 第一部分，要求 i 是 [l,j] 的区间最大值，r 任取，条件是 l\in(L_i,i]\land j\in[i,R_i)，同时 r 有 n-j+1 种选择，因此总次数为 \displaystyle\sum_{l=L_i+1}^i\sum_{j=i}^{R_i-1}(n-j+1)，第二个求和式只和 j 有关，易知贡献为 A\left(B(n-i+1)-\dfrac12B(B-1)\right)a_i；
4. 第二部分，同理可知贡献为 B\left(Ai-\dfrac12A(A-1)\right)a_i。

把一二三部分加起来化简：

因此答案为：

时间复杂度为 \mathcal O(n)，30s 何意味。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, p = 1e9 + 7; char buf[N], *p1, *p2;
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF : *p1++)
int rdtp; inline int rd(int &x = rdtp) { x = 0; char c = 0; while (c < '0' || c > '9') c = gc; while (c >= '0' && c <= '9') x = x * 10 - '0' + c, c = gc; return x; }
int n, a[N], s[N], L[N], R[N];
void solve(int _) {
    rd(n); for (int i = 1; i <= n; i++) rd(a[i]); int ans = 0;
    s[0] = 0;     for (int i = 1, t = 0; i <= n; i++) { while (t && a[s[t]] <  a[i]) t--; L[i] = s[t], s[++t] = i; }
    s[0] = n + 1; for (int i = n, t = 0; i >= 1; i--) { while (t && a[s[t]] <= a[i]) t--; R[i] = s[t], s[++t] = i; }
    for (int i = 1; i <= n; i++) ans = (ans + (ll(i - L[i]) * (R[i] - i) * (n - R[i] + L[i] + 2) - (ll)i * (n - i + 1) % p + p) % p * a[i]) % p;
    cout << "Case #" << _ << ": " << ans << '\n';
}
int main() { int T = rd(); for (int i = 1; i <= T; i++) solve(i); }