P5298 [PKUWC2018] Minimax 题解

第一次自己做出黑

题意

给定一颗 $n$ 个节点，以 $1$ 为根节点的树，叶子节点有权值 $a_i$，其他节点有概率 $p_i$，表示有 $p_i$ 的概率此节点的权值为子节点中的最大权值，有 $1-p_i$ 的概率为子节点中的最小权值。

思路

首先将权值离散化成 $1\sim ln$，设 $f_{x,i}$ 表示节点 $x$ 的权值为 $i$ 的概率，转移十分简单，由于没有相同的权值，枚举子节点权值为 $1\sim i-1$ 和 $i+1\sim ln$ 即可。

具体来说，设子节点为 $y$，当 $i$ 作为最大值时的概率：

$$f_{x,i}\times\sum_{j=1}^{i-1}f_{y,j}\times a_x$$

$i$ 作为最小值的概率：

$$f_{x,i}\times\sum_{j=i+1}^{ln}f_{y,j}\times (1-a_x)$$

设 $tot_{x,i}=\sum_{j=1}^{i}f_{x,j}$，转移式即为：

$$f_{x,i}\leftarrow f_{x,i}\times(tot_{y,i-1}\times a_x+(1-tot_{y,i-1})\times (1-a_x))$$

这样直接进行dp是 $O(n^2)$ 的，代码如下：

$O(n^2)$ dp部分代码

void dfs(int &x){
	if(!ls[x]){
		v[x].push_back(a[x]);
		dp[x].push_back(1);
		sz[x]=1;
		return ;
	}
	if(!rs[x]){
		dfs(ls[x]); 
		x=ls[x];
		return ;
	}
	dfs(ls[x]);dfs(rs[x]);
	if(sz[ls[x]]<sz[rs[x]])swap(ls[x],rs[x]);
	for(int i=0;i<sz[ls[x]];i++)totl[i]=((i?totl[i-1]:0)+dp[ls[x]][i])%mod;
	for(int i=0;i<sz[rs[x]];i++)totr[i]=((i?totr[i-1]:0)+dp[rs[x]][i])%mod;
	int j=-1;
	for(int i=0;i<sz[ls[x]];i++){
		while(j<sz[rs[x]]-1&&v[rs[x]][j+1]<=v[ls[x]][i])j++;
		dp[ls[x]][i]=dp[ls[x]][i]*((j>=0?totr[j]*a[x]%mod:0)+(mod+1-(j>=0?totr[j]%mod:0))%mod*((mod+1-a[x])%mod)%mod)%mod;
	}
	j=-1;
	for(int i=0;i<sz[rs[x]];i++){
		while(j>=0&&v[ls[x]][j]>v[rs[x]][i])j--;
		while(j<sz[ls[x]]-1&&v[ls[x]][j+1]<=v[rs[x]][i])j++;
		dp[rs[x]][i]=dp[rs[x]][i]*((j>=0?totl[j]*a[x]%mod:0)+(mod+1-(j>=0?totl[j]%mod:0))%mod*((mod+1-a[x])%mod)%mod)%mod;
	}
	j=0;
	for(int i=0;i<sz[ls[x]];i++){
		while(j<sz[rs[x]]&&v[rs[x]][j]<v[ls[x]][i]){
			dp[x].push_back(dp[rs[x]][j]);
			v[x].push_back(v[rs[x]][j]); 
			j++;
		}
		dp[x].push_back(dp[ls[x]][i]);
		v[x].push_back(v[ls[x]][i]);
	}
		while(j<sz[rs[x]]){
			dp[x].push_back(dp[rs[x]][j]);
			v[x].push_back(v[rs[x]][j]); 
			j++;
		}
	sz[x]=sz[ls[x]]+sz[rs[x]];
}

注意到dp总状态数是稀疏的，并且转移过程需要维护前后缀，考虑线段树合并。

设 $px,sx$ 表示当前节点的 $x$ 的线段树的前缀和和后缀和，则在叶子节点的 $y$ 的转移即为 $tr_y=tr_y*(px*a_x+sx*(1-a_x))$，$x$ 的转移也同理。

剩下主要的细节都在代码里，结合代码仔细理解。

代码

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,ls[300010],rs[300010],ln; 
ll lsh[300010],a[300010];
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
struct N{
	int ls,rs;
	ll c,la;//区间和以及乘法懒标记 
}tr[10000010];
int rt[300010],id;
void pushup(int p){
	tr[p].c=0;
	if(lc(p))tr[p].c=tr[lc(p)].c;
	if(rc(p))tr[p].c=(tr[p].c+tr[rc(p)].c)%mod;
}
void pushdown(int p){
	if(tr[p].la!=1){
		if(lc(p)){
			tr[lc(p)].c=tr[lc(p)].c*tr[p].la%mod;
			tr[lc(p)].la=tr[lc(p)].la*tr[p].la%mod;
		}
		if(rc(p)){
			tr[rc(p)].c=tr[rc(p)].c*tr[p].la%mod;
			tr[rc(p)].la=tr[rc(p)].la*tr[p].la%mod;
		}
		tr[p].la=1;
	}
}
void change(int &p,int l,int r,int x){//插入一个权值为x的节点，初始概率为1 
	if(!p)tr[p=++id]={0,0,1,1};
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x);
	else change(rc(p),mid+1,r,x);
}
int merge(int x,int y,int l,int r,ll px,ll sx,ll py,ll sy,ll P){//线段树合并，px,sx,py,sy意思如题解所说，P即为a_x，选最大值的概率 
	if(!x&&!y)return 0;//两个节点都不存在返回0 
	if(!x){//只有y的节点 
		tr[y].c=tr[y].c*(px*P%mod+sx*(mod+1-P)%mod)%mod;
		tr[y].la=tr[y].la*(px*P%mod+sx*(mod+1-P)%mod)%mod;
		return y;
	}
	if(!y){//只有x的节点 
		tr[x].c=tr[x].c*(py*P%mod+sy*(mod+1-P)%mod)%mod;
		tr[x].la=tr[x].la*(py*P%mod+sy*(mod+1-P)%mod)%mod;
		return x;
	}
	if(l==r){//叶子节点 
		tr[x].c=(tr[x].c*(py*P%mod+sy*(mod+1-P)%mod)%mod+tr[y].c*(px*P%mod+sx*(mod+1-P)%mod)%mod)%mod;
		return x;
	}
	int mid=(l+r)>>1;
	pushdown(x);pushdown(y);
	ll prex=tr[lc(x)].c,prey=tr[lc(y)].c,sufx=tr[rc(x)].c,sufy=tr[rc(y)].c;//累加前后缀和 
	lc(x)=merge(lc(x),lc(y),l,mid,px,(sx+sufx)%mod,py,(sy+sufy)%mod,P);
	rc(x)=merge(rc(x),rc(y),mid+1,r,(px+prex)%mod,sx,(py+prey)%mod,sy,P);
	pushup(x);
	return x;
}
ll find(int p,int l,int r){//统计答案 
	if(!p)return 0;
	if(l==r)return l*lsh[l]%mod*tr[p].c%mod*tr[p].c%mod;
	pushdown(p);
	int mid=(l+r)>>1;
	return (find(lc(p),l,mid)+find(rc(p),mid+1,r))%mod;
}
void dfs(int x){//树形dp 
	if(!ls[x]){
		change(rt[x],1,ln,a[x]);
		return ;
	}
	if(!rs[x]){
		dfs(ls[x]);
		rt[x]=rt[ls[x]];
		return ;
	}
	dfs(ls[x]);dfs(rs[x]);
	rt[x]=merge(rt[ls[x]],rt[rs[x]],1,ln,0,0,0,0,a[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		if(x){
			if(ls[x])rs[x]=i;
			else ls[x]=i;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(!ls[i])lsh[++ln]=a[i];
		else a[i]=a[i]*qpow(10000,mod-2)%mod;
	}
	sort(lsh+1,lsh+1+ln);
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=n;i++)if(!ls[i])a[i]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
	dfs(1);
	cout<<find(rt[1],1,ln);
	return 0;
}

好妙的一个题…

我们设 $f_{i,j}$ 为 $i$ 节点出现 $j$ 的概率

设 $l = ch[i][0] , r = ch[i][1]$ 即左儿子右儿子

设 $m$ 为叶子结点的个数

显然，$i$ 出现 $j$ 的概率为

$$f_{i,j} = f_{l,j} * (p_i \sum_{k=1}^{j-1}f_{r,k} + (1-p_i)\sum_{k=j+1}^{m}f_{r,k}) + f_{r,j} * (p_i \sum_{k=1}^{j-1}f_{l,k} + (1-p_i)\sum_{k=j+1}^{m}f_{l,k})$$

不难发现，这个柿子有关前缀和和后缀和，可以用线段树合并的操作来进行转移，从下到上转移，求出根节点的概率就好了…

#include <cstdio>
#include <algorithm>

int read() {
  int x = 0;
  char c = 0;
  while (c < 48) c = getchar();
  while (c > 47) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
  return x;
}

const int mod = 998244353;
int qpow(int x, int y) {
  int ans = 1;
  for (; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1) ans = 1ll * ans * x % mod;
  return ans;
}

int n;
const int maxn = 3e5 + 10;
int ch[maxn][2], fa[maxn], cnt[maxn], val[maxn], tmp[maxn], qwq = 0, s[maxn];
int rt[maxn], ls[maxn << 5], rs[maxn << 5], sum[maxn << 5], mul[maxn << 5];
int ans = 0, tot = 0;

void pushup(int rt) { sum[rt] = (sum[ls[rt]] +sum[rs[rt]]) % mod; }
void pushmul(int rt, int v) {
  if (!rt) return;
  sum[rt] = 1ll * sum[rt] * v % mod;
  mul[rt] = 1ll * mul[rt] * v % mod;
}

void pushd(int rt) {
  if (mul[rt] == 1) return;
  if (ls[rt]) pushmul(ls[rt], mul[rt]);
  if (rs[rt]) pushmul(rs[rt], mul[rt]);
  mul[rt] = 1;
}

int newnode() {
	int x = ++ tot; 
	ls[x] = rs[x] = sum[x] = 0, mul[x] = 1 ;
	return x ;
}
void upd(int& p, int l, int r, int x, int v) {
  if (!p) p = newnode() ;
  if (l == r) {
    sum[p] = v;
    return;
  }
  pushd(p);
  int mid = l + r >> 1;
  (x <= mid) ? upd(ls[p], l, mid, x, v) : upd(rs[p], mid + 1, r, x, v);
  pushup(p);
}

int merge(int x, int y, int l, int r, int xmul, int ymul, int v) {
  if (!x && !y) return 0;
  if (!x) {
    pushmul(y, ymul);
    return y;
  }
  if (!y) {
    pushmul(x, xmul);
    return x;
  }
  pushd(x), pushd(y);
  int mid = l + r >> 1;
  int lsx = sum[ls[x]], lsy = sum[ls[y]], rsx = sum[rs[x]], rsy = sum[rs[y]];
  ls[x] = merge(ls[x], ls[y], l, mid, (xmul + 1ll * rsy % mod * (1 - v + mod)) % mod,
                (ymul + 1ll * rsx % mod * (1 - v + mod)) % mod, v);
  rs[x] = merge(rs[x], rs[y], mid + 1, r, (xmul + 1ll * lsy % mod * v) % mod,
                (ymul + 1ll * lsx % mod * v) % mod, v);
  pushup(x);
  return x;
}

void out(int x, int l, int r) {
  if (!x) return;
  if (l == r) {
    s[l] = sum[x];
    return;
  }
  int mid = l + r >> 1;
  pushd(x);
  out(ls[x], l, mid);
  out(rs[x], mid + 1, r);
}

void dfs(int u) {
  if (!cnt[u]) upd(rt[u], 1, qwq, val[u], 1);
  if (cnt[u] == 1) dfs(ch[u][0]), rt[u] = rt[ch[u][0]] ;
  if (cnt[u] == 2) dfs(ch[u][0]), dfs(ch[u][1]), rt[u] = merge(rt[ch[u][0]], rt[ch[u][1]] ,1 , qwq , 0 , 0 , val[u]);
}

int main() {
  n = read();
  for (int i = 1; i <= n; i++) fa[i] = read();
  for (int i = 1; i <= n; i++)
    if (fa[i]) ch[fa[i]][cnt[fa[i]]++] = i;
  for (int i = 1; i <= n; i++) val[i] = read();
  for (int i = 1; i <= n; i++) {
    if (cnt[i]) {
      val[i] = 1ll * val[i] * qpow(10000, mod - 2) % mod;
    } else {
      tmp[++qwq] = val[i];
    }
  }
  std ::sort(tmp + 1, tmp + qwq + 1);
  for (int i = 1; i <= n; i++)
    if (!cnt[i]) val[i] = std ::lower_bound(tmp + 1, tmp + qwq + 1, val[i]) - tmp;
  dfs(1);
  out(rt[1], 1, qwq);
  for (int i = 1; i <= qwq; i++) ans = (ans + 1ll * i * tmp[i] % mod * s[i] % mod * s[i]) % mod;
  printf("%d\n", ans);
  return 0;
}

C70 线段树合并+概率论 P5298 [PKUWC2018] Minimax

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void read(int &x){ //快读
  x=0; char c=getchar();
  while(!isdigit(c))c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar();
}
typedef long long LL;
const int N=300005, M=998244353;
#define mid (l+r)/2
int n,m,ans,tot;
int fa[N],ch[N][2],cnt[N],p[N],v[N],d[N];
int root[N],ls[N*22],rs[N*22];
LL f[N*22],tag[N*22];
//p:叶子离散权值和非叶子概率, v:叶子权值, d:根取值的概率
//f:节点权值的概率和, tag:乘法懒标记

int qpow(int x,int n){ //快速幂
  int s=1;
  for(;n;n>>=1,x=1ll*x*x%M)
    if(n&1) s=1ll*s*x%M;
  return s;
}
void update(int x,int v){ //更新x点信息
  f[x]=f[x]*v%M; tag[x]=tag[x]*v%M;
}
void pushdown(int x){ //下传
  if(tag[x]>1)
    update(ls[x],tag[x]), update(rs[x],tag[x]), tag[x]=1;
}
void change(int &x,int l,int r,int p){ //点修
  if(!x){x=++tot; tag[x]=1;}
  f[x]++;
  if(l==r) return;
  if(p<=mid) change(ls[x],l,mid,p);
  else change(rs[x],mid+1,r,p);
}
int merge(int x,int y,int px,int py,int sx,int sy,LL p){ //合并
  //px,py:x,y的前缀和，sx,sy:x,y的后缀和，p:x与y的父节点的概率
  if(!x&&!y) return 0;
  //若x不空，则f[x]*(p*y的前缀和+(1-p)*y的后缀和)
  if(!y){update(x,(p*py%M+(1-p+M)*sy%M)%M);return x;}
  if(!x){update(y,(p*px%M+(1-p+M)*sx%M)%M);return y;}
  pushdown(x),pushdown(y);
  LL lx=f[ls[x]],ly=f[ls[y]],rx=f[rs[x]],ry=f[rs[y]];
  //x,y同步走左分支时，向下累计各自的后缀和
  ls[x]=merge(ls[x],ls[y],px,py,(sx+rx)%M,(sy+ry)%M,p);
  rs[x]=merge(rs[x],rs[y],(px+lx)%M,(py+ly)%M,sx,sy,p);
  f[x]=(f[ls[x]]+f[rs[x]])%M; return x;
}
void dfs(int x){ //递归原树
  if(!ch[x][0])  //x是叶子,创建线段树
    {change(root[x],1,m,p[x]);return;}
  if(!ch[x][1])  //x只有左儿子,继承线段树
    {dfs(ch[x][0]);root[x]=root[ch[x][0]];return;}
  dfs(ch[x][0]); dfs(ch[x][1]); //递归左右,合并线段树
  root[x]=merge(root[ch[x][0]],root[ch[x][1]],0,0,0,0,p[x]);
}
void dfs2(int x,int l,int r){  //递归线段树
  if(l==r){d[l]=f[x]; return;} //保存叶子权值的概率
  pushdown(x);
  dfs2(ls[x],l,mid);
  dfs2(rs[x],mid+1,r);
}
int main(){
  read(n);
  for(int i=1; i<=n; i++) read(fa[i]);
  for(int i=1; i<=n; i++) read(p[i]);
  for(int i=1; i<=n; i++) ch[fa[i]][cnt[fa[i]]++]=i;
  for(int i=1; i<=n; i++)
    if(!cnt[i]) v[++m]=p[i]; //叶子权值
    else p[i]=1ll*p[i]*qpow(10000,M-2)%M; //非叶子概率
  sort(v+1,v+m+1);
  for(int i=1; i<=n; i++) //叶子的离散权值
    if(!cnt[i]) p[i]=lower_bound(v+1,v+m+1,p[i])-v;
  dfs(1);
  dfs2(root[1],1,m);
  for(int i=1; i<=m; i++)
    ans=(ans+1ll*i*v[i]%M*d[i]%M*d[i]%M)%M;
  printf("%d\n",ans);
}