WA on #7 求助
查看原帖
WA on #7 求助
914391
P_BisectorGo ahead楼主2024/5/14 21:56
#include<iostream>
#include<vector>
#include<algorithm>
#define N 300500
#define mod 998244353
#define re1e4 796898467
#define ll long long
using namespace std;
struct tnode{
	ll l,r,x;
}b[N];
struct ltnode{
	ll l,r,x,mul;
	void pushdown(ll c){
		x*=c,x%=mod,mul*=c,mul%=mod;
	}
}a[N*80];
int n;
ll rt[N],tot,ans,tmp[N],cnt;
vector<ll>v;
ll newnode(){
	++tot;
	a[tot].x=a[tot].mul=1;
	return tot;
}
ll update(ll p,ll l,ll r,ll x){
	p=newnode();
	if(l!=r){
		ll m=(l+r)/2;
		if(x<=m)a[p].l=update(a[p].l,l,m,x);
		else a[p].r=update(a[p].r,m+1,r,x);
	}
	return p;
}
void pushdown(ll x){
	if(a[x].mul==1)return;
	if(a[x].l)a[a[x].l].pushdown(a[x].mul);
	if(a[x].r)a[a[x].r].pushdown(a[x].mul);
	a[x].mul=1;
}
ll merge(ll p1,ll p2,ll l1,ll r1,ll l2,ll r2,ll lp,ll rp){
	if(p1==0&&p2==0)return 0;
	if(p1&&p2){
		pushdown(p1),pushdown(p2);
		ll t1=a[a[p1].l].x,t2=a[a[p2].l].x;
		a[p1].l=merge(a[p1].l,a[p2].l,l1,r1+a[a[p1].r].x,
		l2,r2+a[a[p2].r].x,lp,rp);
		a[p1].r=merge(a[p1].r,a[p2].r,l1+t1,r1,
		l2+t2,r2,lp,rp);
		a[p1].x=a[a[p1].l].x+a[a[p1].r].x;
		a[p1].x%=mod;
	}else{
		if(!p1)swap(p1,p2),r2=r1,l2=l1;
	l1%=mod,l2%=mod,r1%=mod,r2%=mod;
		a[p1].pushdown((r2*lp%mod+l2*rp)%mod);
	}
	return p1;
}
void dfs(int x){
	if(b[x].l==0){
		rt[x]=update(rt[x],1,cnt,b[x].x);
	}else if(b[x].r==0){
		dfs(b[x].l),rt[x]=rt[b[x].l];
	}else{
		dfs(b[x].l),dfs(b[x].r);
		ll lp=mod+1-b[x].x,rp=b[x].x;
		rt[x]=merge(rt[b[x].l],rt[b[x].r],0,0,0,0,lp,rp);
	}
}
void getans(ll x,ll l,ll r){
	pushdown(x);
	if(l==r){
		ans+=(l*tmp[l]%mod*a[x].x%mod*a[x].x%mod);
		ans%=mod;
		return;
	}
	ll m=(l+r)/2;
	getans(a[x].l,l,m);
	getans(a[x].r,m+1,r);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int fa;
		cin>>fa;
		if(fa==0)continue;
		if(b[fa].r==0)b[fa].r=i;
		else b[fa].l=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i].x;
		if(b[i].l){
			b[i].x*=re1e4,b[i].x%=mod;
		}else{
			tmp[++cnt]=b[i].x;
		}
	}
	sort(tmp+1,tmp+1+cnt);
	for(int i=1;i<=n;i++){
		if(!b[i].l)b[i].x=lower_bound(tmp+1,tmp+1+cnt,b[i].x)
		-tmp;
	}
	dfs(1);
	getans(rt[1],1,cnt);
	cout<<ans;
	return 0;
}

rt。

2024/5/14 21:56
加载中...