P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
有 \(n(n≤10^5)\) 个点，形成树状结构。
有 \(m(m≤10^5)\) 次发放操作，每次选择两个点 \(x,y\) ，对 \(x\) 到 \(y\) 的路径上（包括 \(x,y\)）的每个点发放一个 \(z(z≤10^5)\) 类型的物品。
求完成所有操作后，每个点存放最多的是哪种类型的物品。
思路：
每个点维护一个权值线段树，用差分修改，最后累加得出答案。
为保证空间复杂度，需要动态开点。
在最后累加差分时，需要线段树合并。
用权值线段树维护最大值 \(maxx\)，以及最大值的编号 \(id\)
void pushup(int id) {
int lc = tr[id].ls, rc = tr[id].rs;
if (tr[lc].maxx >= tr[rc].maxx) { //左子树的id一定比右子树小
tr[id].maxx = tr[lc].maxx;
tr[id].id = tr[lc].id;
}
else {
tr[id].maxx = tr[rc].maxx;
tr[id].id = tr[rc].id;
}
}
动态开点（每一次插入操作至多新开 \(\log n\) 个空间）
void insert(int &u,int l,int r,int pos,int v)
{
if(!u)u=++cnt;
if(l==r){
tr[u].maxx+=v;
tr[u].id=l;
return;
}
int mid=l+r>>1;
if(pos<=mid)insert(tr[u].ls,l,mid,pos,v);
else insert(tr[u].rs,mid+1,r,pos,v);
pushup(u);
}
线段树合并：
将一些线段树的值累加成一颗，并维护相应的值。
指针 \(p,q\) 分别从两颗线段树的根节点出发,分别向下递归。
若 \(p,q\) 之一为空，则直接替换。
否则递归左右子树，删除节点 \(q\)
最多合并 \(n-1\) 次，每次复杂度 \(O(\log n)\)
int merge(int p,int q,int l,int r)
{
if(!p)return q;
if(!q)return p;
if(l==r){
tr[p].maxx+=tr[q].maxx;
return p;
}
int mid=l+r>>1;
tr[p].ls=merge(tr[p].ls,tr[q].ls,l,mid);
tr[p].rs=merge(tr[p].rs,tr[q].rs,mid+1,r);
pushup(p);
return p;
}