自动搬运

查看原文

来自洛谷，原作者为

	zyn_ 而最终，一切往事都被追忆。

搬运于2025-08-24 23:17:29，当前版本为作者最后更新于2025-06-03 22:14:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：一棵树，点有点权，支持子树加，求若干条链的并集的点权和。

链的并集好可怕啊，怎么维护？直接上重链剖分，一条链变成 $O(\log n)$ 个区间，区间的并集就很和蔼了。

按左端点从小到大排序遍历区间，维护当前的区间并集 $[l,r]$。设遍历到 $[l_0,r_0]$，若 $l_0>r$ 则用 $[l,r]$ 更新答案，以后的区间不会包含 $\le r$ 的数了，直接 $[l,r]\gets [l_0,r_0]$；否则将 $[l_0,r_0]$ 合并，$r\gets \max\{r,r_0\}$ 即可。给出代码：

l=f[1].l,r=f[1].r;
for(int i=2;i<=c;++i){
    if(f[i].l>r)ans+=qr(l,r,1,n,1),l=f[i].l,r=f[i].r;
    else r=max(r,f[i].r);
}
ans+=qr(l,r,1,n,1);

剩下的就是区间加区间和，线段树即可。