线段树合并分裂小练

· · 个人记录

线段树分裂通常跟dp搞在一起，而dp是我最不擅长的算法之一。。。

[Lydsy1706月赛]大根堆

先离散化一下值

然后考虑dp。设f[x][i]表示在以i为根的子树中选择，最大值不超过i，最多选多少个数。

先转移儿子节点f_{x,i}=\sum_{y\in son(x)}f_{y,i}

然后考虑加入x点的贡献，即f[x][val[x]~maxval]对f[x][val[x]-1]+1取max

可以用线段树维护这个东西，具体来说，维护一个二元标记(a,b)表示当前区间内的每个数都要先+a然后和b取max。

合并标记：max(max(x+a,b)+a',b')=max(x+a+a',max(b+a',b'))

然后维护时需要注意让a<b,不然b对a取个max。这样的话b可以直接当成dp值，写起来比较方便。

维护的话只能一个叶子和节点合并比较好写，所以如果一个节点只有左右儿子中的一个就吧另一个建出来，不难证明复杂度对的

code

NOI2020 命运

博主太懒，估了

code

「TJOI / HEOI2016」排序

线段树分裂/二分答案

线段树分裂强的1p，不仅是在线的，而且还少个log

code

「ZJOI2019」语言

考虑对于每个点计算能和他产生贡献的点的个数，那么就是把所有经过他的路径上的点拿出来建虚树，虚树上点的个数。

考虑线段树合并，线段树的下标是dfs序，那么把经过当前点的所有路径的端点放进线段树中，（线段树里相邻的点的距离和+第一个点和最后一个点的距离）/2就是能和当前这个点产生贡献的点数。

然后一个点在端点处被加入线段树（对于两个端点处，两个端点都要加，因为是虚树。相当于端点被加入两次。），在lca处删除即可

code

「PKUWC2018」Minimax

对于叶子，$f_{i,v_i}=1$,其他都是0 对于只有一个儿子,直接继承 对于两个儿子 $f_{i,j}=f_{ls,j}(p_i\sum_{a<j}f_{rs,a}+(1-p_i)\sum_{a>j}f_{rs,a})+f_{rs,j}(p_i\sum_{a<j}f_{ls,a}+(1-p_i)\sum_{a>j}f_{ls,a})

考虑线段树合并，当递归到其中一棵树的节点为空的时候，说明在当前区间的贡献都相同了不必再向下递归，那么维护一个区间f和，然后打个区间加的标记就可。

大概是因为v_i唯一，保证了复杂度正确

可以不离散化，只是会慢的邪恶。nkoj 998ms

code