题解：P12693 BZOJ3589 动态树

· · 题解

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

链的并集好可怕啊，怎么维护？直接上重链剖分，一条链变成 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);

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