NKOJ 2703 （WC 2014）紫荆花之恋 （点分治+平衡树+替罪羊）

发表于 |
字数统计: 1,993字 | 阅读时长 ≈ 10min

P2703【WC2014】紫荆花之恋（强数据版）

问题描述

强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花废物的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。
仔细看看的话，这棵大树实际上是一个带权树。每个时刻他会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵i都有一个感受能力ri，小精灵i,j成为朋友当且仅当在树上i和j的距离dist(i,j)<=ri+rj，其中dist(i,j)表示在这棵树上i和j的唯一路径上所有边的边权和。
强强和萌萌很好奇每次新长出了一个叶子节点之后这棵树上总共有几对朋友。
我们假定这棵树一开始为空，节点按照加入的顺序从1开始编号。由于强强非常好奇，你必须在每次出现新的节点后马上给出总共的朋友对数不能拖延哦。

输入格式

输入文件共有n+2行。
第一行包含一个正整数T，表示测试点编号。
第二行包含一个正整数n，表示总共要加入的节点数。
我们令加入前的总工朋友对数是last_ans，在一开始时last_ans=0。
接下来n行中第i行有三个数ai,ci,ri，表示节点i的父亲节点的编号为(ai xor ( last_ans mod 109))，与父亲节点之间的边权为ci，节点i上小精灵的感受能力为ri。
注意a1=c1=0，表示1号点事根节点。对于i>=2，父亲节点的编号至少是1，至多是i-1。

输出格式

输出文件包含n行，每行输出1个整数，表示加入第i个点之后，树上共有几对朋友。

样例输入

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

样例输出

0
1
2
4
7

考虑点分治，一个点对合法仅当他们不在同一颗子树上且$dep[i]+dep[j]<=r[i]+r[j]，dep表示点到根的距离$
移项得到$dep[i]-r[i]<=r[j]-dep[j]$，那么只需要维护$dep[i]-r[i]$的信息即可。
需要支持添加，查找比某个数小的数的个数，那么用平衡树。

查询点分治树上两点距离的时候在原树上暴力LCA查找即可。

关于加点，直接在点分治树上添加即可，然后进行链查询，链修改，但是这样可能使得点分治树非常的不平衡
采用替罪羊树的思想解决，设定常数$ki$，当过于不平衡时重构即可，这里$ki$大概取$0.8?$
复杂度$O(nlog^3n)$

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#define ll long long
#define N 300005
#define M 12345678
using namespace std;
const int mod=1e9;
const double ki=0.8;
typedef pair<int,int> par;
int n,R[N];
ll Ans;
int fa[N][20],dis[N][20],dep[N],S=18;
int TOT,LA[N],NE[N],EN[N],LE[N];
int Art[N],Ort[N],tot,ls[M],rs[M],v[M],w[M],si[M];
int rt,Min,SS[N],Fa[N],Si[N];
vector<int>to[N];
bool mark[N];
queue<int>bin;
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y],s=0;
	for(i=0;i<=S;i++)
	if(t>>i&1)s+=dis[x][i],x=fa[x][i];
	if(x==y)return s;
	for(i=S;i>=0;i--)
	if(fa[x][i]!=fa[y][i])
	{
		s+=dis[x][i]+dis[y][i];
		x=fa[x][i];y=fa[y][i];
	}
	return s+dis[x][0]+dis[y][0];
}
void MT(int x)
{si[x]=si[ls[x]]+si[rs[x]]+1;}
int Merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(w[x]<w[y])
	{
		rs[x]=Merge(rs[x],y);
		MT(x);return x;
	}
	else
	{
		ls[y]=Merge(x,ls[y]);
		MT(y);return y;
	}
}
par Split(int x,int k)
{
	if(k==0)return par(0,x);
	int l=ls[x],r=rs[x];
	if(k==si[l])return ls[x]=0,MT(x),par(l,x);
	if(k==si[l]+1)return rs[x]=0,MT(x),par(x,r);
	if(k<si[l])
	{
		par tmp=Split(l,k);
		ls[x]=tmp.second;MT(x);
		return par(tmp.first,x);
	}
	else
	{
		par tmp=Split(r,k-si[l]-1);
		rs[x]=tmp.first;MT(x);
		return par(x,tmp.second);
	}
}
int Rank(int x,int p)
{
	if(p==0)return 0;
	if(v[p]<=x)return si[ls[p]]+1+Rank(x,rs[p]);
	return Rank(x,ls[p]);
}
int Ins(int x,int &p)
{
	int t,k=Rank(x,p);
	par tmp=Split(p,k);
	if(bin.size())t=bin.front(),bin.pop();
	else t=++tot;
	ls[t]=rs[t]=0;
	v[t]=x;w[t]=rand();si[t]=1;
	p=Merge(tmp.first,t);
	p=Merge(p,tmp.second);
}
void Gmark(int x)
{
	mark[x]=0;
	for(int i=0;i<to[x].size();i++)Gmark(to[x][i]);
}
void Grt(int x,int s,int f)
{
	int i,y,Max=0;SS[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y==f||mark[y])continue;
		Grt(y,s,x);SS[x]+=SS[y];
		if(SS[y]>Max)Max=SS[y];
	}
	if(s-Max>Max)Max=s-Max;
	if(Max<Min)Min=Max,rt=x;
}
void Gdis(int x,int d,int f,int &k1,int &k2)
{
	Ins(d-R[x],k1);Ins(d-R[x],k2);
	for(int i=LA[x];i;i=NE[i])
	if(!mark[EN[i]]&&EN[i]!=f)Gdis(EN[i],d+LE[i],x,k1,k2);
}
void Del(int x)
{
	if(!x)return;
	bin.push(x);
	Del(ls[x]);
	Del(rs[x]);
	ls[x]=rs[x]=0;
}
void ReDC(int x)
{
	int i,y;mark[x]=1;Si[x]=1;
	to[x].clear();
	Del(Art[x]);Art[x]=0;
	Ins(-R[x],Art[x]);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y])continue;
		Min=1e9;Grt(y,SS[y],x);
		to[x].push_back(rt);
		Fa[rt]=x;Del(Ort[rt]);Ort[rt]=0;
		Gdis(y,LE[i],0,Art[x],Ort[rt]);
	}
	for(i=0;i<to[x].size();i++)ReDC(to[x][i]),Si[x]+=Si[to[x][i]];
}
void Rebuild(int x)
{
	int i,p=Fa[x];Gmark(x);
	Min=1e9;Grt(x,Si[x],p);
	if(p)
	{
		for(i=0;i<to[p].size();i++)
		if(to[p][i]==x){to[p][i]=rt;break;}
	}
	Ort[rt]=Ort[x];
	if(x!=rt)Ort[x]=0;//！！！！！！
	Fa[rt]=Fa[x];ReDC(rt);
}
void Solve(int x,int f,int le)
{
	int i,j,k=f,d,p=Fa[f],las=x;mark[x]=1;
	Si[x]=1;Fa[x]=f;Si[f]++;
	Ins(-R[x],Art[x]);
	to[f].push_back(x);
	Ins(le-R[x],Ort[x]);
	Ans+=Rank(R[x]-le,Art[f]);
	Ins(le-R[x],Art[f]);
	while(p)
	{
		d=LCA(x,p);
		Ans+=Rank(R[x]-d,Art[p]);
		Ans-=Rank(R[x]-d,Ort[k]);
		Ins(d-R[x],Art[p]);
		Ins(d-R[x],Ort[k]);
		Si[p]++;k=p;p=Fa[p];
	}
	for(p=x;Fa[p];p=Fa[p])
	if(1.0*Si[p]>=1.0*Si[Fa[p]]*ki)las=Fa[p];
	if(las!=x)Rebuild(las);
}
int main_main()
{
	srand(time(NULL));
	int i,j,k,x,y,z;
	scanf("%d%d",&x,&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(i==1)
		{
			printf("0\n");
			R[i]=z;Si[i]=1;
			Ins(-R[i],Art[i]);
			mark[i]=1;continue;
		}
		fa[i][0]=x^(Ans%mod);
		dep[i]=dep[fa[i][0]]+1;
		dis[i][0]=y;R[i]=z;
		ADD(fa[i][0],i,y);
		ADD(i,fa[i][0],y);
		for(j=1;j<=S;j++)fa[i][j]=fa[fa[i][j-1]][j-1],dis[i][j]=dis[fa[i][j-1]][j-1]+dis[i][j-1];
		Solve(i,fa[i][0],y);
		printf("%lld\n",Ans);
	}
}
const int main_stack=16;
char my_stack[128<<21];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
  return 0;
}