题解-PKUWC2018 Minimax

Problem

loj2537

Solution

pkuwc2018最水的一题，要死要活调了一个多小时（1h59min）

我写这题不是因为它有多好，而是为了保持pkuwc2018的队形，与这题类似的有一个好玩得多的题

由于答案的形式和期望相去甚远，所以可以肯定这题和期望无关，而且这么复杂的式子我们最好还是把所有可能计算出来啦

可以肯定地说这题是从叶子向根合并，合并时分类讨论下取最大\((p)\)还是最小\((1-p)\)，然后维护前后缀概率和即可

再瞟一眼数据，发现线段树合并可以解决，完结

Code

注意由于线段树合并时若一个节点为空则直接返回，但这棵子树需要乘上整体概率，所以还要在裸的线段树合并中加上标记维护

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void read(int&x){
    char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
    while(isdigit(c11))x=x*10+c11-‘0‘,c11=getchar();
}

const int N=301050,M=N*10,p=998244353;
struct Edge{int v,nxt;}a[N];
int ls[M],rs[M],f[M],lz[M];
int head[N],c[N],b[N],rt[N];
int n,_,tot;

template <typename _tp> inline _tp qm(_tp x){return x<0?x+p:x<p?x:x-p;}

void update(int l,int r,int&x,int vl){
    if(!x)lz[x=++tot]=1;
    if(l==r){f[x]=1;return ;}
    int mid(l+r>>1);
    if(vl<=mid)update(l,mid,ls[x],vl);
    else update(mid+1,r,rs[x],vl);
    f[x]=qm(f[ls[x]]+f[rs[x]]);
}

inline void mul(int x,int vl){
    f[x]=1ll*f[x]*vl%p;
    lz[x]=1ll*lz[x]*vl%p;
}

inline void down(int x){
    if(ls[x])mul(ls[x],lz[x]);
    if(rs[x])mul(rs[x],lz[x]);
    lz[x]=1;
}

int merge(int x,int y,ll p0,ll p1,ll p2){
    if(x&&lz[x]!=1)down(x);
    if(y&&lz[y]!=1)down(y);
    if(!x){mul(y,p0*p1%p+qm(1-p0)*qm(1-p1)%p);return y;}
    if(!y){mul(x,p0*p2%p+qm(1-p0)*qm(1-p2)%p);return x;}
    rs[x]=merge(rs[x],rs[y],p0,qm(p1+f[ls[x]]),qm(p2+f[ls[y]]));
    ls[x]=merge(ls[x],ls[y],p0,p1,p2);
    f[x]=qm(f[ls[x]]+f[rs[x]]);
    return x;
}

void dfs(int x){
    for(int i=head[x];i;i=a[i].nxt){
        dfs(a[i].v);
        if(!rt[x])rt[x]=rt[a[i].v];
        else rt[x]=merge(rt[x],rt[a[i].v],c[x],0ll,0ll);
    }
    if(!head[x])update(1,n,rt[x],c[x]);
}

int calc(int l,int r,int x){
    if(lz[x]!=1)down(x);
    if(l==r)return 1ll*l *b[l]%p *f[x]%p *f[x]%p;
    int mid(l+r>>1);
    return qm(calc(l,mid,ls[x])+calc(mid+1,r,rs[x]));
}

int main(){
    read(n);
    for(int i=1,x;i<=n;++i){
        read(x),a[++_].v=i;
        a[_].nxt=head[x],head[x]=_;
    }
    int tt=0;const ll inv5=796898467;
    for(int i=1;i<=n;++i){
        read(c[i]);
        if(head[i])c[i]=inv5*c[i]%p;
        else b[++tt]=c[i];
    }
    sort(b+1,b+tt+1);
    int end=unique(b+1,b+tt+1)-b;
    for(int i=1;i<=n;++i)
        if(!head[i])c[i]=lower_bound(b+1,b+end,c[i])-b;
    n=end-1;dfs(1);
    printf("%d\n",calc(1,n,1));
    return 0;
}

题解-PKUWC2018 Minimax

原文：https://www.cnblogs.com/penth/p/10181881.html