快落古做水的一道题！
发现题解区的大佬们讲解重构点分树部分蒟蒻不是很能理解，当时就是卡在了如何重构部分，于是来写一篇题解。
题意大概就是给出一棵支持插入点的树，每个点有和自己父亲的距离 $w_i$ 和自己的探索半径 $r_i$，问每次插入一个新的点之后有多少对点满足 $r_i+r_j\geq dis(i,j)$。
首先我们可以记录一个答案变量，每次加入新点时统计这个新点的贡献就可以了。由于答案和树的形态无关，所以可以考虑建造点分树。
那么我们一步一步来：
统计贡献
先对强的关系进行连边（由强到弱）。由于强具有传递性，那么题目就等价于求从每个点出发能到达的点的个数。
一个一个点搜是 $O(n2)$ 的，显然会超时。考虑优化，可以在数组中由弱到强排序，这样 $i$ 能到的 $i+1$ 也能到，搜过的点不用再搜，搜 $i+1$ 时只用在 $i$ 的答案上叠加即可。
重构点分树
给上下同乘一个 $Q(-x)$，变成 $[xk]\frac{P(x)Q(-x)}{Q(x)Q(-x)}$。显然分母的奇数项都会抵消变成 $0$，这样看起来就能把问题折半了。
对 $k$ 的奇偶性分类讨论，对于分子，我们只关心与 $k$ 同奇偶的那些项。对于 $k$ 为偶数，可以得到一个 $\frac{F(x2)}{G(x2)}$，对于 $k$ 为奇数，可以得到一个 $\frac{xF(x2)}{G(x2)}$。这里 $F,G$ 只需要计算 $P(x)Q(-x)$ 和 $Q(x)Q(-x)$ 就能得到。然后就能折半到 $[x^{\lfloor\frac{k}{2}\rfloor}]\frac{F(x)}{G(x)}$ 的问题上了。继续递归即可，时间复杂度 $\mathcal O(n\log n\log k)$。
- 常系数齐次线性递推：有了 Bostan-Mori 算法，我们只要构造出合理的 $P,Q$ 即可。分式远处求值和线性递推是可以互相转化的。
现在要构造 $P,Q$ 使得 $[xn]\frac{P(x)}{Q(x)}=a_n$。由于 $P,Q$ 都得是有限次多项式，我们可以取一个 $>\deg P$ 的次数，此时 $P$ 对应系数为 $0$，再带入求解：
\sum\limits_{i=0}^{n}a_iq_{n-i}=0
把 $a_nq_0$ 移过去除掉，得到：
a_n=-\sum\limits_{i=0}^{n-1}\frac{q_{n-i}}{q_0}a_i
那么 $Q$ 就很容易取了：构造 $q_0=1$，$q_i=-f_i(i\ge 1)$ 即可。若记 $a_0,\dots,a_{n-1}$ 对应的多项式为 $A$，$P$ 就是 $Q\cdot A \bmod x^{k}$。于是 $P,Q$ 可以在 $\mathcal O(k\log k)$ 的时间复杂度内求出，再使用 Bostan-Mori 方法即可做到 $\mathcal O(k\log k\log n)$。
当然有一种用特征多项式 + 多项式取模的经典做法可以做到相同复杂度，但是常数相对大很多（一轮只要两次卷积的优越性）。
一些小细节
- 我们发现重构点分树和替罪羊树时如果自己子树不平衡，自己的父亲子树也不平衡时直接重构自己父亲的子树就可以了，因为如果重构自己子树，自己的父亲还是会不平衡，所以还不如直接重构父亲，这样也可以让自己平衡。这样的话我们每次如果要重构就找到最上面的不平衡的父亲重构即可。
- 重构点分树时，清空替罪羊树的节点后可以回收到内存池中，重复利用，这样可以避免内存爆炸。
- 由于 1 号节点处理答案时有一些奇奇怪怪的问题所以可以拿出来单独判断处理。
- 边权很大所以要开 long long。
- 在清空子树时一定要判一下当前节点不是 0 再扔到内存池里面，否则会把 0 扔进去，然后一个节点 pushup 的时候就会把0的信息统计进去，然后就会炸裂，
别问我怎么知道的
然后就没了。放一下代码：
#include<bits/stdc++.h>
#define Lson(x) node[x].Son[0]
#define Rson(x) node[x].Son[1]
using namespace std;
typedef long long ll;
const int MAXN=1e5,LOGN=17;
const ll MOD=1e9;
inline int Read()
{
int ret;char c;
while(1) {c=getchar();if('0'<=c && c<='9') {ret=c-'0';break;}}
while(1) {c=getchar();if('0'<=c && c<='9') ret=ret*10+c-'0';else break;}
return ret;
}
//---------------------- fhqTreap --------------------------
struct fhqTreap
{
int Son[2],SIZE,data,KEY;
//KEY in [0,RAND_MAX]
}node[2*MAXN*LOGN+5];int Tail;
int New(int x)
{
node[++Tail].data=x;
node[Tail].SIZE=1;
node[Tail].KEY=rand();
node[Tail].Son[0]=node[Tail].Son[1]=0;
return Tail;
}
void PushUp(int now) {node[now].SIZE=node[Lson(now)].SIZE+1+node[Rson(now)].SIZE;}
void Split(int now,int x,int &a,int &b)//值域分裂
{
if(!now) {a=b=0;return;}
if(node[now].data<=x) a=now,Split(Rson(now),x,Rson(now),b);
else b=now,Split(Lson(now),x,a,Lson(now));
PushUp(now);
}
int Merge(int a,int b)
{
if(!a || !b) return a^b;
if(node[a].KEY>node[b].KEY) {Rson(a)=Merge(Rson(a),b),PushUp(a);return a;}
Lson(b)=Merge(a,Lson(b)),PushUp(b);return b;
}
int Ask(int now,int x)
{
if(!now) return 0;
if(x<node[now].data) return Ask(Lson(now),x);
return node[Lson(now)].SIZE+1+Ask(Rson(now),x);
}
void Add(int &x,int v)
{
int a,b;Split(x,v,a,b);
x=Merge(Merge(a,New(v)),b);
}
//---------------------- daq Tree --------------------------
struct DE {int nxt,val;};
int n,S,q,R[MAXN+5];
vector<DE> Tree[MAXN+5];
ll ans;
vector<int> ance[MAXN+5],depth[MAXN+5],subt[MAXN+5];
//点分树上祖先，每层的深度，每层所在子树编号
vector<int> subfhq[MAXN+5];//成为根时每个子树的 fhq 根
int beRoot,root[MAXN+5];//编号最大的成为点分树根的结点，成为根时 fhq 的根
vector<DE> Left[MAXN+5];//剩余结点构成的树
bool V[MAXN+5];int Size[MAXN+5];
void CalSize(int now,int lst)
{
Size[now]=1;
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(rear==lst || V[rear]) continue;
CalSize(rear,now),Size[now]+=Size[rear];
}
}
int FindCG(int now,int lst,int ALL)
{
bool OK=1;
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(rear==lst || V[rear]) continue;
if(2*Size[rear]>ALL) {OK=0;break;}
}
OK&=(2*Size[now]>=ALL);
if(OK) return now;
for(int i=0,rear,res;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(rear==lst || V[rear]) continue;
res=FindCG(rear,now,ALL);
if(res) return res;
}
return 0;
}
void BuildMainfhq(int now,int lst,int x,int dep)
{
ance[now].push_back(x);
depth[now].push_back(dep);
Add(root[x],dep-R[now]);
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(rear==lst || V[rear]) continue;
BuildMainfhq(rear,now,x,dep+Tree[now][i].val);
}
}
void BuildSubfhq(int now,int lst,int x,int y,int dep)//根与第几个子树
{
subt[now].push_back(y);
Add(subfhq[x][y],dep-R[now]);
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(rear==lst || V[rear]) continue;
BuildSubfhq(rear,now,x,y,dep+Tree[now][i].val);
}
}
void daq(int now)//分治建树
{
CalSize(now,0),now=FindCG(now,0,Size[now]);
BuildMainfhq(now,0,now,0);
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(V[rear]) continue;
subfhq[now].push_back(0);
BuildSubfhq(rear,now,now,subfhq[now].size()-1,Tree[now][i].val);
}
V[now]=1;
for(int i=0,rear;i<Tree[now].size();i++)
{
rear=Tree[now][i].nxt;
if(V[rear]) continue;
daq(rear);
}
}
void Build()
{
for(int i=1;i<=n;i++)
{
ance[i].clear();
depth[i].clear();
subt[i].clear();
subfhq[i].clear();
V[i]=root[i]=0;
}
for(int i=beRoot+1;i<=n;i++) Left[i].clear();
Tail=0,daq(1),beRoot=n;
}
void Link(int a,int c)
{
if(a>beRoot)
{
Left[a].push_back(DE{n,c});
Left[n].push_back(DE{a,c});
for(int i=0,now,dep;i<ance[a].size();i++)
{
now=ance[a][i];
dep=depth[a][i]+c;
ance[n].push_back(now);
depth[n].push_back(dep);
subt[n].push_back(subt[a][i]);
Add(root[now],dep-R[n]);
Add(subfhq[now][subt[n][i]],dep-R[n]);
}
}
else
for(int i=0,now,dep;i<ance[a].size();i++)
{
now=ance[a][i];
dep=depth[a][i]+c;
ance[n].push_back(now);
depth[n].push_back(dep);
if(i==ance[a].size()-1)
{
subfhq[a].push_back(0);
subt[n].push_back(subfhq[a].size()-1);
}
else subt[n].push_back(subt[a][i]);
Add(root[now],dep-R[n]);
Add(subfhq[now][subt[n][i]],dep-R[n]);
}
}
int LeftQuery(int now,int lst,int x,int dist)
{
int res=(dist<=R[x]+R[now] && now!=x);
for(int i=0,rear;i<Left[now].size();i++)
{
rear=Left[now][i].nxt;
if(rear==lst) continue;
res+=LeftQuery(rear,now,x,dist+Left[now][i].val);
}
return res;
}
int Query(int x)
{
int res=0;
for(int i=0,now;i<ance[x].size();i++)
{
now=ance[x][i];
res+=Ask(root[now],R[x]-depth[x][i]);
if(x==ance[x][i]) --res;
else
{
res-=Ask(subfhq[now][subt[x][i]],R[x]-depth[x][i]);
if(i==ance[x].size()-1) res+=LeftQuery(x,0,x,0);
}
}
return res;
}
void Insert(int a,int c)//插入结点 n
{
if(!a)
{
beRoot=1;
ance[n].push_back(n),depth[n].push_back(0);
root[n]=0,Add(root[n],-R[n]);
return;
}
Tree[a].push_back(DE{n,c});
Tree[n].push_back(DE{a,c});
if(n%S==0) Build();//n-S+1 ~ n 没有成为过点分树的根
else Link(a,c);
ans+=Query(n);
}
int main()
{
int T=Read();
q=Read();
S=ceil(sqrt(q)*log(q)/log(2));
int a,c;
for(n=1;n<=q;n++)
{
a=Read(),c=Read(),R[n]=Read();
a^=ans%MOD;
Insert(a,c);
printf("%lld\n",ans);
q++;
}
return 0;
}