BZOJ5461 PKUWC2018Minimax（概率期望+线段树合并+动态规划）

时间：2024-12-13 10:06:56

　　离散化后，容易想到设f[i][j]为i节点权值为j的概率，不妨设j权值在左子树，则有f[i][j]=f[lson][j](pi·f[rson][1~j]+(1-pi)·f[rson][j~m])。

　　考虑用线段树合并优化这个dp。记录前缀和，合并某节点时，若某棵线段树在该节点处为空，给另一棵线段树打上乘法标记即可。注意前缀和不要算成合并后的了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 300010

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,p[N],a[N],b[N],fa[N],root[N],t,ans,cnt;

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

struct data2{int l,r,x,lazy;

}tree[N<<];

void ins(int &k,int l,int r,int x)

{

    if (!k) k=++cnt;tree[k].x=;

    if (l==r) return;

    int mid=l+r>>;

    if (x<=mid) ins(tree[k].l,l,mid,x);

    else ins(tree[k].r,mid+,r,x);

}

void update(int k,int x)

{

    if (!k) return;

    tree[k].x=1ll*tree[k].x*x%P;

    if (tree[k].lazy) tree[k].lazy=1ll*tree[k].lazy*x%P;

    else tree[k].lazy=x;

}

void down(int k){update(tree[k].l,tree[k].lazy),update(tree[k].r,tree[k].lazy),tree[k].lazy=;}

int query(int k,int l,int r,int x)

{

    if (!k) return ;

    if (l==r) return tree[k].x;

    if (tree[k].lazy) down(k);

    int mid=l+r>>;

    if (x<=mid) return query(tree[k].l,l,mid,x);

    else return query(tree[k].r,mid+,r,x);

}

int merge(int x,int y,int l,int r,int s0,int s1,int p)

{

    if (tree[x].lazy) down(x);

    if (tree[y].lazy) down(y);

    if (!x||!y)

    {

        if (!x) x=y,swap(s0,s1);

        update(x,(1ll*p*s1+1ll*(P+-p)*(P+-s1))%P);

        return x;

    }

    if (l<r)

    {

        int mid=l+r>>;

        tree[x].r=merge(tree[x].r,tree[y].r,mid+,r,(s0+tree[tree[x].l].x)%P,(s1+tree[tree[y].l].x)%P,p);

        tree[x].l=merge(tree[x].l,tree[y].l,l,mid,s0,s1,p),

        tree[x].x=(tree[tree[x].l].x+tree[tree[x].r].x)%P;

    }

    return x;

}

void dfs(int k)

{

    int s=;

    for (int i=p[k];i;i=edge[i].nxt)

    dfs(edge[i].to),s++;

    if (s==) ins(root[k],,m,a[k]);

    else if (s==) root[k]=root[edge[p[k]].to];

    else root[k]=merge(root[edge[p[k]].to],root[edge[edge[p[k]].nxt].to],,m,,,a[k]);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5461.in","r",stdin);

    freopen("bzoj5461.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++)

    {

        int x=read();

        fa[i]=x,addedge(x,i);

    }

    for (int i=;i<=n;i++)

    {

        a[i]=read();

        if (p[i]) a[i]=1ll*a[i]*%P;

        else b[++m]=a[i];

    }

    sort(b+,b+m+);

    for (int i=;i<=n;i++) if (!p[i]) a[i]=lower_bound(b+,b+m+,a[i])-b;

    dfs();

    for (int i=;i<=m;i++)

    {

        int x=query(root[],,m,i);

        ans=(ans+1ll*i*b[i]%P*x%P*x)%P;

    }

    cout<<ans;

    return ;

}

相关文章