ZJOI2016 线段树

Vexoben

Mar 19, 2019

It takes 8 minutes to read this article.

题目链接：ZJOI2016 线段树

（刷新以获取数学公式）

题意

给定一个长为 $n$ 的随机序列(即每个元素在 $1e9$ 范围内随机)， $q$ 次操作，每次随机选定一个区间，将这段区间中的数都替换为这段区间的最大值。求最终每个数的期望乘 $(\frac{n(n+1)}{2})^q$

数据范围： $n,q≤400$

题解

相当于计算在所有可能的操作下，每个数最终结果之和。于是我们只需要求出最终变成每个数的方案数。

由于元素在 $1e9$ 内随机，我们可以认为所有数互不相同。对于每个数 $x$ ，我们可以处理出一个区间 $[L,R]$ ，使得它是这个区间的最大值（也就是建出笛卡尔树）。

设计一个状态：设当前枚举数是 $x$ ，令 $f_{i,l,r}$ 为进行了 $i$ 次操作 $[l,r]$ 是一个最大值不超过 $x$ 的极大区间的方案数。极大的意思是，如果 $l>1$ ，那么 $l-1$ 上的数必须大于 $x$ 。显然只有当 $L≤l≤r≤R$ 的时候状态是有意义的。

这样转移就很显然了：

$f_{i,l,r} = f_{i-1,l,r} * c_{l,r} + \sum_{k=L}^{i-1} f_{i-1,k,j}*(k-1)+\sum_{k=j+1}^{R}f_{i-1,i,k}*(R-k)$ $c_{l,r} = \frac{i(i+1)+(n-j)(n-j+1)+(j-i+1)(j-i+2)}{2}$

第一个是选择一个 $[l,r]$ 的子区间或一个和 $[l,r]$ 没有交集的区间进行操作，从 $f_{i-1,l,r}$ 转移。

第二个是原来极大区间是 $[k,j]$ ，选择一个左端点在 $[1..k-1]$ ，右端点在 $i-1$ 的区间进行操作。第三个和第二个类似。

计算答案是枚举这个数不大于多少，然后枚举极大区间即可。

这里认为 $n,q$ 同阶。在数据非随机的情况下复杂度是 $O(n^4)$ 。但是数据随机可以证明期望是 $O(n^3)$

事实上我们只要证明：对长度为 $n$ 的序列建立的笛卡尔树，所有节点控制区间的长度平方和是 $O(n^2)$

不妨设这个值是 $f_{n}$ ，枚举最大值的位置，那么：

$f_{n} = n ^ 2 + \frac{1}{n} \sum_{i=1}^{n} f_{i-1} + f_{n-i}, f_0 = 0$

令 $g_{n} = \sum_{i=0}^{n} f_n$

$g_{n} = \frac{n+2}{n} g_{n-1} + n^2 , g_0 = 0$ $\frac{g_n}{(n+2)(n+1)} = \frac{g_{n-1}}{(n+1)(n)} + \frac{n^2}{(n+2)(n+1)}$ $g_{n} = (n+1)(n+2) \sum_{i=1}^{n} \frac{i^2}{(i+1)(i+2)}$ $f_{n} = g_{n} - g_{n-1} = (n+1)(2\sum_{i=1}^{n-1}\frac{i^2}{(i+1)(i+2)} + \frac{n^2}{n+1}) = O(n^2)$

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 405;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

int n, m;
int a[N], val[N];
int f[2][N][N], sum[N][N];

LL calc(int x) {
	return 1LL * x * (x + 1) / 2 % mod;
}

void upd(int &x, int y) {
	x = (x + y >= mod) ? x + y - mod : x + y;
}

void solve(int x, int L, int R) {
	for (int i = L; i <= R; ++i) {
		for (int j = i; j <= R; ++j) {
			f[0][i][j] = f[1][i][j] = 0;
		}
	}
	f[0][L][R] = 1;
	int p = 1;
	for (int k = 1; k <= m; ++k, p ^= 1) {
		for (int i = L; i <= R; ++i) {
			for (int j = i; j <= R; ++j) {
				f[p][i][j] = 0;
			}
		}
		for (int i = L; i <= R; ++i) {
			for (int j = i; j <= R; ++j) {
				int s = 1LL * f[p ^ 1][i][j];
				s = 1LL * s * (calc(i - 1) + calc(n - j) + calc(j - i + 1)) % mod;
				upd(f[p][i][j], s);
			}
		}
		for (int j = L; j <= R; ++j) {
			int t = 0;
			for (int i = L; i <= j; ++i) {
				upd(f[p][i][j], t);
				upd(t, 1LL * (i - 1) * f[p ^ 1][i][j] % mod);
			}
		}
		for (int i = L; i <= R; ++i) {
			int t = 0;
			for (int j = R; j >= i; --j) {
				upd(f[p][i][j], t);
				upd(t, 1LL * (n - j) * f[p ^ 1][i][j] % mod);
			}
		}
	}
	for (int i = L; i <= R; ++i) {
		for (int j = i; j <= R; ++j) {
			for (int k = i; k <= j; ++k) {
				upd(sum[k][x], f[p ^ 1][i][j]);
			}
		}
	}
}

int main() {
	read(n); read(m);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		val[i] = a[i];
	}
	sort(val + 1, val + n + 1);
	int tot = unique(val + 1, val + n + 1) - val - 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(val + 1, val + tot + 1, a[i]) - val;
	}
	for (int i = 1; i <= n; ++i) {
		int L = i, R = i;
		while (L > 1 && a[L - 1] < a[i]) --L;
		while (R < n && a[R + 1] < a[i]) ++R;
		solve(a[i], L, R);
	}
	for (int i = 1; i <= n; ++i) {
		int ans = 0;
		for (int j = 1; j <= n; ++j) {
			int k = sum[i][j];
			if (!k) {
				sum[i][j] = sum[i][j - 1];
				continue;
			}
			upd(k, mod - sum[i][j - 1]);
			upd(ans, 1LL * val[j] * k % mod);
		}
		if (ans < 0) ans += mod;
		printf("%d ", ans);
	}
	puts("");
}