Bzoj4574 [ZJOI2016] 线段树

,

[ZJOI2016] 线段树

https://www.luogu.com.cn/problem/P3352

Solution

难得自己做出来。

关键 trick：恰好转化为至少。

观察到如果直接求恰好最大值为 $x$ 的方案数，最后乘起来，这样状态就要多一维，转移就更不用说了。

考虑求最大值恰好为 $x$ 的方案数。这样转化为对一个 $01$ 序列取 $\max$。 最后统计每个点为 $1$ 的方案数。

观察到如果一个点初始为 $0$，只会有左右两边最近的 $1$ 可能对其产生贡献。考虑对相邻的两个为 $1$ 的点，记录下标为 $L,R$ 进行计数。

令 $f_{l,r,j}$ 表示 $[L,l],[r,R]$ 在第 $j$ 轮后为 $1$，$[l+1,r-1]$ 为 $0$ 的方案数。定义 $C(n)=\dfrac{n(n+1)}{2}$。有转移：

  • $1$ 的个数没有增多，自己转移到自己：$f_{l,r,j}\gets f_{l,r,j-1}\times (C(r-l-1)+C(l)+C(n-r))$。

  • $1$ 的个数增多了，以左边为例：$f_{l,r,j}\gets \sum_{k<l} f_{k,r,j-1}\times C(k)$。右边同理

每次操作的区间大小是笛卡尔树上的子树大小。记区间大小为 $l$，每次 dp 的时间复杂度为 $O(ql^2)$。观察到随机数据下，笛卡尔树子树的期望平方和是 $O(n^2)$ 的，所以总复杂度是 $O(qn^2)$。可以通过本题。

看题解以后发现其实是有确定性的时间复杂度做法的。每次算贡献的形式一样，只需要全扔进去一起算就好了。这里还没有实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 405
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int f[maxn][maxn][2],d[maxn];
int Ans[maxn][maxn];
int rk[maxn],id[maxn],tot,n,m,a[maxn],N,c[maxn];
void add(int &x,int y) {x=(x+y)%mod;}
bool cmp(int x,int y) {return a[x]<a[y];}
int C(int n) {return n*(n+1)/2%mod;}
void calc(int L,int R,int rt) {
	int i,j,k;
	for (i=L;i<=R;i++) for (j=L;j<=R;j++) f[i][j][0]=0;
	f[L][R][0]=1;
	for (k=1;k<=m;k++) {
		int now=k&1,pre=now^1;
		for (i=L;i<=R;i++) for (j=L;j<=R;j++) f[i][j][now]=0;
		for (i=L;i<=R;i++) {
			int res=0;
			for (j=R;j>=i+1;j--) {
				if (i+1==j) add(f[i][j][now],f[i][j][pre]*C(n)+res);
				else add(f[i][j][now],f[i][j][pre]*(C(j-i-1)+C(i)+C(n-j+1))%mod+res);
				add(res,f[i][j][pre]*(n-j+1));
			}
		}
		for (j=L;j<=R;j++) {
			int res=0;
			for (i=L;i<j;i++) {
				add(f[i][j][now],res);
				add(res,f[i][j][pre]*(i));
			}
		}
	}
	for (i=L;i<=R;i++) d[i]=0;
	for (i=L;i<=R;i++) for (j=L+2;j<=R;j++) {
		add(d[i+1],f[i][j][m&1]);
		add(d[j],mod-f[i][j][m&1]);
	}
	Ans[rt][L]=N;
	for (i=L+1;i<=R;i++) add(d[i],d[i-1]),Ans[rt][i]=(N-d[i]+mod)%mod;//,gdb(rt,i,Ans[rt][i]);
}
void solve(int rt) {
	int i,j,k,las=0,L,R;
	for (i=1;i<=n;i++) Ans[rt][i]=Ans[rt+1][i];
	for (i=id[rt];i>=0;i--) if (c[i]) {L=i;break;}
	for (i=id[rt];i<=n+1;i++) if (c[i]) {R=i;break;}
	c[id[rt]]=1;
	calc(L,id[rt],rt);
	calc(id[rt],R,rt);
}
signed main(void){
	int i,j;
	read(n);read(m);
	N=power(n*(n+1)/2,m);
	gdb(N,1);
	for (i=1;i<=n;i++) read(a[i]),id[i]=i;
	sort(id+1,id+1+n,cmp);
	for (i=1;i<=n;i++) rk[id[i]]=i;
	c[0]=c[n+1]=n+1;
	for (i=n;i>=1;i--) solve(i);
	for (i=1;i<=n;i++) {
		int ans=0;
		for (j=1;j<=n;j++) add(ans,(Ans[j][i]-Ans[j+1][i]+mod)*a[id[j]]);
		printf("%lld ",ans);
	}
	return 0;
}