P7746 WA+RE(给关注)
  • 板块学术版
  • 楼主liyuan2023
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/30 19:15
  • 上次更新2024/7/30 20:39:16
查看原帖
P7746 WA+RE(给关注)
1188691
liyuan2023楼主2024/7/30 19:15
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,fa,cnt,w[N],ll[N],rr[N],x,y;
long long d[N*40],b[N*40];
char op;
vector<int> v[N];
void dfs(int x){
	ll[x]=++cnt;
	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i]);
	}
	rr[x]=cnt;
}
void build(int l,int r,int p){
	if(l==r){
		d[p]=w[ll[l]];
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2),build(mid+1,r,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
}
void pushdown(int l,int r,int p){
	int mid=(l+r)/2;
	d[p*2]+=b[p]*(mid-l+1);
	d[p*2+1]+=b[p]*(r-mid);
	b[p*2]+=b[p];
	b[p*2+1]+=b[p];
	b[p]=0;
}
void update(int l,int r,int c,int s,int t,int p){
	if(l<=s&&t<=r){
		d[p]+=(t-s+1)*c;
		b[p]+=c;
		return ;
	}
	pushdown(s,t,p);
	int mid=(s+t)/2;
	if(l<=mid){
		update(l,r,c,s,mid,p*2);
	}
	if(r>mid){
		update(l,r,c,mid+1,r,p*2+1);
	}
	d[p]=d[p*2]+d[p*2+1];
}
int query(int l,int r,int s,int t,int p){
	if(s==t){
		return d[p];
	}
	pushdown(s,t,p);
	int mid=(s+t)/2,sum=0;
	if(l<=mid){
		return query(l,r,s,mid,p*2);
	}
	if(r>mid){
		return query(l,r,mid+1,r,p*2+1);
	}
	d[p]=d[p*2]+d[p*2+1];
	return sum;
}
int main(){
	cin>>n>>m;
	cin>>w[1];
	for(int i=2;i<=n;i++){
		cin>>w[i]>>fa;
		v[fa].push_back(i);
	}
	dfs(1);
	build(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op=='p'){
			cin>>x>>y;
			update(ll[x]+1,rr[x],y,1,n,1);
		}
		else{
			cin>>x;
			cout<<query(ll[x],ll[x],1,n,1)<<endl;
		}
	}
	return 0;
}

求调,给关注。

2024/7/30 19:15
加载中...