题解：P3352 [ZJOI2016] 线段树

biyi_mouse · 2025-04-03 15:00:49 · 题解

或许更好的阅读体验

首先观察题面，期望乘上 (\frac{n(n + 1)}{2})^q ，即乘上所有可能的操作数。其实就是求所有可能的值乘上方案数。可以根据期望的定义感性理解一下。

所有我们不妨先把答案的式子写出来，即 ans_i = \sum v_j \times h(i, v_j)，其中 h(i, v) 为第 i 个数为 v 的方案数。

然后考虑如何计算 h(i, v)，一个很经典的技巧就是用第 i 个数小于等于 v 的方案数减去小于等于 v - 1 的方案数。

所以我们不妨继续尝试下 DP。容易发现 DP 的阶段应该是操作的次数，记为 i；同时为了满足上述计算，还要记录一个值 v。然后你会发现不能单独记录某一个数的值为 v，因为题目是区间操作，所以记录某个区间 [l, r] 内的数全部小于等于 v。同时我们给出必要的限制，即 a_{l - 1} 和 a_{r + 1} 都必须大于 v。

到此，我们便顺利地得出状态表示 f(i, v, l, r)，其含义就是上文的叙述。

然后思考转移，这一步比较简单，我们直接给出转移式。

其中 g(l, r) 记录的是所有没有影响的操作。这些操作可以是对于 [l, r] 内部区间修改成最大值，也可以是对于 [1, l - 1] 和 [r + 1, n] 的。

所以 g(l, r) = \frac{(r - l + 1)(r - l + 2)}{2} + \frac{l(l + 1)}{2} + \frac{(n - r)(n - r + 1)}{2}。

到此我们便得到了 O(n^3q) 的做法，但是由于数据随机所以近似于 O(n^2q) 就可以过了。

然而我们可以继续优化，注意到在 f 的式子中上述式子中全程 v 没有变化，所以我们不妨思考一下如何去掉这一维。

此时我们再把 f 代入 h，可以得到 h(i, v) = \sum_{i \in [l, r]} [f(q, v, l, r) - f(q, v - 1, l, r)]，所以就有 ans_i = \sum v_j \times \sum_{i \in [l, r]} [f(q, v_j, l, r) - f(q, v_j - 1, l, r)]。

此时我们可以发现，对于某个 f(q, v, l, r)，它的贡献为 f(q, v, l, r) \times (v_j - v_{j + 1})，因此我们可以直接带着 (v_j - v_{j + 1}) 的贡献做 DP，这样就只要记录 f'(q, l, r) 就行了。

但这样子初值就不同了，考虑对于 f'(0, l, r) 它要带有 v_1 - v_2 + v_2 - v_3 + \dots 的贡献，我们会发现 f'(0, l, r) 其实就是区间最大值减最小值，直接做就完了。

于是我们就优化到了 O(n^2q)，彻底拿下了这道题。具体实现时，由于这个题空间给的很小，还需要滚动数组优化下空间。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 1010, Mod = 1e9 + 7;

int n, q;
int a[N], f[2][N][N], g[N][N], s1[2][N][N], s2[2][N][N];

int add(int a, int b, int c) {
    return ((a + b) % Mod + c) % Mod;
}
int mul(int a, int b) {
    return 1ll * a * b % Mod;
}
int calc(int x) {
    return 1ll * x * (x + 1) / 2;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    a[0] = a[n + 1] = 1e9 + 1;
    for (int l = 1; l <= n; l ++) {
        int maxx = 0;
        for (int r = l; r <= n; r ++) {
            maxx = max(maxx, a[r]);
            if (l == 1 && r == n) f[0][l][r] = maxx;
            else if (a[l - 1] > maxx && a[r + 1] > maxx)
                f[0][l][r] = (maxx - min(a[l - 1], a[r + 1]) + Mod) % Mod;
            g[l][r] = add(calc(r - l + 1), calc(l - 1), calc(n - r));
        }
    }
    for (int i = 1; i <= q; i ++) {
        int now = i & 1, pre = i & 1 ^ 1;
        for (int l = 1; l <= n; l ++) {
            for (int r = l; r <= n; r ++) 
                s1[pre][l][r] = (s1[pre][l - 1][r] + mul(f[pre][l][r], l - 1)) % Mod;
            for (int r = n; r >= l; r --)  
                s2[pre][l][r] = (s2[pre][l][r + 1] + mul(f[pre][l][r], n - r)) % Mod;
        }
        for (int l = 1; l <= n; l ++)
            for (int r = l; r <= n; r ++)           
                f[now][l][r] = add(mul(f[pre][l][r], g[l][r]), s1[pre][l - 1][r], s2[pre][l][r + 1]);
    }
    for (int i = 1; i <= n; i ++) {
        int ans = 0;
        for (int l = 1; l <= i; l ++)
            for (int r = i; r <= n; r ++)
                ans = (ans + f[q & 1][l][r]) % Mod;
        cout << ans << " ";
    }
    return 0;
}