ZigZagK的博客
[线段树动态开点+启发式合并]LOJ2537(PKUWC 2018)【Minimax】题解
2018年5月15日 18:09
LOJ
查看标签

题目概述

一个节点 $i$ 的权值有 $p_i$ 的可能是儿子节点权值最大值,$1-p_i$ 的可能是儿子节点权值最小值(至多两个儿子),假设根节点(1)权值有 $m$ 种可能,第 $i$ 小的为 $v_i$ ,概率为 $d_i$ ,求 $\sum_{i=1}^{m}i\times v_i\times d_i^2\ mod\ 998244353$ 。

解题报告

看起来是一道正常的概率题目,但是答案式子很奇怪啊?所以我们干脆想办法求出所有可能的权值。

然后你就会发现这tm变成了数据结构题,对每个节点开一棵权值线段树(或者平衡树)储存每个权值的概率,然后启发式合并。但这样肯定爆空间啊,有两个选择:主席树、动态开点。能用动态开点还是动态开点好。

怎么合并?设目前的节点为 $x$ ,我们把小的树记为 $L$ ,大的记为 $R$ ,那么:

  1. 先遍历一遍把 $L$ 存在的权值抠出来。
  2. 对于权值 $V$ ,被选的概率为 $p_x\times V\times Sum(R,1,V)+(1-p_x)\times V\times Sum(R,V,MAX)$ 。
  3. 然后用 $L$ 存在的权值更新 $R$ (不能一边查询一边更新)。
  4. $R$ 中的元素也改变了,由于保证权值两两不同,所以 $R$ 被分成了很多片段,对于每个片段是区间乘。
  5. 把 $R$ 作为 $x$ 的树。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,maxt=2e7,MOD=998244353;

int n,p[maxn+5],son[maxn+5][2],tem[maxn+5],ro[maxn+5],si[maxn+5],ans;
int len,sum[maxt+5],ls[maxt+5],rs[maxt+5],tag[maxt+5];
int INV,K[maxn+5],val[maxn+5],now[maxn+5],pre[maxn+5],suf[maxn+5];

#define Add(x,y) (son[x][0]?son[x][1]=y:son[x][0]=y)
inline int Find(int x){
    for (int L=1,R=tem[0],mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (x==tem[mid=L+(R-L>>1)]) return mid; else x<tem[mid]?R=mid-1:L=mid+1;
}
#define newnode (tag[++len]=1,len)
#define Addtag(p,k) sum[p]=(LL)sum[p]*(k)%MOD,tag[p]=(LL)tag[p]*(k)%MOD
inline void Pushdown(int p){
    if (tag[p]==1) return;if (!ls[p]) ls[p]=newnode;if (!rs[p]) rs[p]=newnode;
    Addtag(ls[p],tag[p]);Addtag(rs[p],tag[p]);tag[p]=1;
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void Update(int &p,int pos,int k,int l=1,int r=tem[0]){
    if (!p) p=newnode;if (l==r) {sum[p]=k;return;}Pushdown(p);int mid=l+(r-l>>1);
    if (pos<=mid) Update(ls[p],pos,k,l,mid); else Update(rs[p],pos,k,mid+1,r);
    AMOD(sum[p]=sum[ls[p]],sum[rs[p]]);
}
void Multi(int &p,int L,int R,int k,int l=1,int r=tem[0]){
    if (R<l||r<L) return;if (!p) p=newnode;if (L<=l&&r<=R) {Addtag(p,k);return;}
    Pushdown(p);int mid=l+(r-l>>1);Multi(ls[p],L,R,k,l,mid);Multi(rs[p],L,R,k,mid+1,r);
    AMOD(sum[p]=sum[ls[p]],sum[rs[p]]);
}
#define emp(p) (!(p)||!sum[p]&&!ls[p]&&!rs[p])
int Ask(int p,int L,int R,int l=1,int r=tem[0]){
    if (R<l||r<L||emp(p)) return 0;    if (L<=l&&r<=R) return sum[p];Pushdown(p);
    int mid=l+(r-l>>1);return (Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r))%MOD;
}
void gettree(int p,int l=1,int r=tem[0]){
    if (emp(p)) return;if (l==r) {K[++K[0]]=l;val[K[0]]=sum[p];return;}
    Pushdown(p);int mid=l+(r-l>>1);gettree(ls[p],l,mid);gettree(rs[p],mid+1,r);
}
#define Sum(i,j) ((((LL)p[x]*pre[i]%MOD+(LL)(MOD+1-p[x])*suf[j])%MOD)%MOD)
void getleaf(int x){
    int L=son[x][0],R=son[x][1];if (!L) {tem[++tem[0]]=p[x];return;}
    getleaf(L);if (R) getleaf(R);
}
void Dfs(int x){
    int L=son[x][0],R=son[x][1];if (!L) return si[x]=1,Update(ro[x],Find(p[x]),1);
    if (L&&!R) {Dfs(L);ro[x]=ro[L];si[x]=si[L];return;}
    Dfs(L);Dfs(R);si[x]=si[L]+si[R];p[x]=(LL)p[x]*INV%MOD;
    if (si[L]>si[R]) swap(L,R);ro[x]=ro[R];K[0]=0;gettree(ro[L]);
    for (int i=1;i<=K[0];i++){
        now[i]=(LL)p[x]*val[i]%MOD*Ask(ro[x],1,K[i]-1)%MOD;
        AMOD(now[i],(LL)(MOD+1-p[x])*val[i]%MOD*Ask(ro[x],K[i]+1,tem[0])%MOD);
    }
    for (int i=1;i<=K[0];i++) Update(ro[x],K[i],now[i]);
    pre[0]=0;for (int i=1;i<=K[0];i++) AMOD(pre[i]=pre[i-1],val[i]);
    suf[K[0]+1]=0;for (int i=K[0];i;i--) AMOD(suf[i]=suf[i+1],val[i]);
    Multi(ro[x],1,K[1]-1,Sum(0,1));
    for (int i=2;i<=K[0];i++) Multi(ro[x],K[i-1]+1,K[i]-1,Sum(i-1,i));
    Multi(ro[x],K[K[0]]+1,tem[0],Sum(K[0],K[0]+1));
}
inline int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;}return s;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%*d",&n);for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);
    for (int i=1;i<=n;i++) scanf("%d",&p[i]);getleaf(1);
    sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
    INV=Pow(10000,MOD-2);Dfs(1);K[0]=0;gettree(ro[1]);
    for (int i=1;i<=K[0];i++) AMOD(ans,(LL)i*tem[K[i]]%MOD*val[i]%MOD*val[i]%MOD);
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
请不要发毫无意义或内容不文明的评论。与本文无关评论请发留言板!
2018-05-31 10:24:01panda_2134
2018-05-31 10:24:01

alert("手动滑稽")
以及2个log跑3e5好像确实有点卡啊qwq

访客
2018-05-31 10:36:08ZigZagK
2018-05-31 10:36:08
@panda_2134 

好像有一个log的解法……但是我太菜了不会……倍感压力

博主
2018-05-31 15:04:34panda_2134
2018-05-31 15:04:34
@ZigZagK 

我写了个和您一样的2个log的,3s TLE我的滑稽会冒汗

访客