「PKUWC2018」Minimax

左手的ㄟ右手 2021-12-22 00:13 183阅读 0赞

## [ 传送门 ][Link 1] ##

## **Solution**  ##

> 发现叶子节点的值都不样，所以可以线段树合并。
> 
> 然后因为我们要维护一个后缀，所以我们先合并右儿子，在合并左儿子

## **Code ** ##

//2019.1.14 8:59~10:15 PaperCloud #include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } #define MN 300005 #define mod 998244353 int const INV_1e4=796898467; int N,c[MN][3],fa[MN],p[MN]; struct Node { int val,id; bool operator<(const Node&o)const {return val<o.val;} }a[MN];int tot; struct node{int ls,rs,lazy,p;}t[MN*15];int pin,root[MN]; #define mid ((l+r)>>1) inline void Modify(int &x,int l,int r,int val) { if(!x) x=++pin;t[x].lazy=t[x].p=1ll;if(l==r) return; val<=mid?Modify(t[x].ls,l,mid,val):Modify(t[x].rs,mid+1,r,val); } ll L,R,P; inline void pushdown(int x) { if(t[x].lazy==1) return; t[x].p=1ll*t[x].p*t[x].lazy%mod; t[t[x].ls].lazy=1ll*t[t[x].ls].lazy*t[x].lazy%mod; t[t[x].rs].lazy=1ll*t[t[x].rs].lazy*t[x].lazy%mod; t[x].lazy=1; } inline void pushup(int x){t[x].p=(t[t[x].ls].p+t[t[x].rs].p)%mod;} inline int Merge(int x,int y) { // printf("%d %d\n",x,y); if(!x&&!y)return 0; pushdown(x),pushdown(y); if(!y) { (L+=t[x].p)%=mod,t[x].lazy=1ll*t[x].lazy*(R+P-2ll*R*P%mod+mod)%mod; pushdown(x);return x; } if(!x) { (R+=t[y].p)%=mod,t[y].lazy=1ll*t[y].lazy*(L+P-2ll*L*P%mod+mod)%mod; pushdown(y);return y; } t[x].rs=Merge(t[x].rs,t[y].rs);t[x].ls=Merge(t[x].ls,t[y].ls);pushup(x); return x; } inline void dfs(int x=1) { if(!c[x][0]) return; else if(c[x][0]==1) dfs(c[x][1]),root[x]=root[c[x][1]]; else { dfs(c[x][1]),dfs(c[x][2]);L=R=0;P=p[x]; root[x]=Merge(root[c[x][1]],root[c[x][2]]); } } inline void calc(int x=root[1],int l=1,int r=tot) { static ll ans=0;pushdown(x); if(l==r) { (ans+=(1ll*l*a[l].val%mod*t[x].p%mod*t[x].p%mod)%mod)%=mod; if(l==tot) printf("%lld\n",ans); return; } calc(t[x].ls,l,mid);calc(t[x].rs,mid+1,r); } int main() { // freopen("1.in","r",stdin); N=read();register int i; for(i=1;i<=N;++i) fa[i]=read(),c[fa[i]][++c[fa[i]][0]]=i; for(i=1;i<=N;++i) if(c[i][0]>0) p[i]=1ll*read()*INV_1e4%mod; else a[++tot]=(Node){read(),i}; std::sort(a+1,a+tot+1); for(i=1;i<=tot;++i) p[a[i].id]=i,Modify(root[a[i].id],1,tot,i); dfs();calc();return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10275295.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=5461