「51nod1462」树据结构

Source and Judge

51nod1462

Analysis

dffxtz师兄出的题

做法一：
暴力树剖+分块，时间复杂度为 $O(nlogn\sqrt n)$

做法二：
利用矩阵乘法的优秀性质，树剖
时间复杂度为 $O(8nlog^2 n)$

做法三：
考虑时间倒流，考虑每次操作1的增量的总系数，就是后面有多少次操作2
不太好整体做，不妨考虑树上启发式合并，树状数组边插边弄
时间复杂度为 $O(nlog^2 n)$

做法四：
把树上启发式改为线段树合并，开两棵以时间为下标的动态开点线段树
统计答案就是类似cdq的过程，而复杂度则和合并是一样的
时间复杂度为 $O(nlogn)$

//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;

namespace mine
{
	typedef long long ll;
	const int INF=0x3f3f3f3f;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(int num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void writeln(int num){write(num);puts("");}
	#define pr pair<int,int>
	#define FR first
	#define SE second
	#define MP make_pair
	inline void chmin(ll &x,ll y) {x=x<y?x:y;}

	const int MAX_N=110000;
	vector<int> son[MAX_N];

	int id=0;
	void insert(ll s[],int lc[],int rc[],int &x,int l,int r,int p,ll c)
	{
		if(x==0) x=++id;
		s[x]+=c;
		if(l==r) return;
		int mid=(l+r)>>1;
		if(p<=mid) insert(s,lc,rc,lc[x],l,mid,p,c);
		else insert(s,lc,rc,rc[x],mid+1,r,p,c);
	}
	void merg(ll s[],int lc[],int rc[],int x,int &y,int l,int r)
	{
		if(x==0) return;
		if(y==0) {y=x;return;}
		s[y]+=s[x];
		if(l==r) return;
		int mid=(l+r)>>1;
		merg(s,lc,rc,lc[x],lc[y],l,mid);
		merg(s,lc,rc,rc[x],rc[y],mid+1,r);
	}

	ll s[2][MAX_N*20];
	int rt[2][MAX_N],lc[2][MAX_N*20],rc[2][MAX_N*20];
	ll ans[MAX_N];
	void calc(ll &sum,int x,int y,int l,int r)
	{
		if(x==0 or y==0) return;
		sum+=s[0][lc[0][x]]*s[1][rc[1][y]];
		if(l==r) return;
		int mid=(l+r)>>1;
		calc(sum,lc[0][x],lc[1][y],l,mid);
		calc(sum,rc[0][x],rc[1][y],mid+1,r);
	}
	int q;
	void solve(int x)
	{
		calc(ans[x],rt[0][x],rt[1][x],1,q);
		for(int t=0;t<(int)son[x].size();t++)
		{
			int y=son[x][t];
			solve(y);
			ans[x]+=ans[y];
			calc(ans[x],rt[0][x],rt[1][y],1,q);
			calc(ans[x],rt[0][y],rt[1][x],1,q);
			merg(s[0],lc[0],rc[0],rt[0][y],rt[0][x],1,q);
			merg(s[1],lc[1],rc[1],rt[1][y],rt[1][x],1,q);
		}
	}
	void main()
	{
		int n;scanf("%d",&n);
		for(int i=2;i<=n;i++) son[qread()].push_back(i);
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			int op=qread(),x=qread();ll d=qread();
			if(op==1) insert(s[0],lc[0],rc[0],rt[0][x],1,q,i,d);
			else insert(s[1],lc[1],rc[1],rt[1][x],1,q,i,d);
		}
		memset(ans,0,sizeof ans);
		solve(1);
		for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
 	}
};
int main()
{
	srand(time(0));
	mine::main();
}