题解：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) \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)

，彻底拿下了这道题。具体实现时，由于这个题空间给的很小，还需要滚动数组优化下空间。

CPP

#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;
}

题解：P3352 [ZJOI2016] 线段树

文章操作

相关推荐

评论

题解：P3352 [ZJOI2016] 线段树