「51nod1462」树据结构

Source and Judge

51nod1462

Analysis

请先思考后再展开

dffxtz师兄出的题

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//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();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d8f8.html
转载请注明出处,谢谢!