P3352 ZJOI2016 线段树

首先观察题面，期望乘上 \((\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)\)，其含义就是上文的叙述。

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

\[f(i, v, l, r) = f(i - 1, v, l, r) \times g(l, r) + \sum_{j > r} f(i - 1, v, l, j) + \sum_{j < l}f(i - 1, v, j, 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) * (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 + ...)\) 的贡献，我们会发现 \(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;
}