线段树合并

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;
}