多省省选联考全真模拟考试6

http://csp.ac/contest/14

ShadowsocksR天下第一

T1T3都少了20,没办法

把n个线段分成p组每组交集和最大且不能有空交集组

考虑把线段分成有包含的线段b和没有包含的线段a两类

然后你会发现没有包含的部分直接可以DP, $f_{i,j}$ 表示前i个线段(按照左端点排序后),划分为j组且i必须在j组的最大和

f_{i,j}=\max {f_{k,j-1}+cost(k+1,i)}

然而你会发现那些有包含的部分可以通过贪心从大到小选啊

就是枚举下i组给b单独放,然后 $Sum_b$ + $f_{n,p-i}$ 即可

因为剩下的直接放进去也是不会使答案变小的qwq全覆盖了

先算出1e7内质数和1e7内每个合数最小质因子

然后考虑一个 $a_i$ 最向左向右和谁互质...这个是独立的考虑一边

考虑向左每个质因子最后出现位置,然后所有这些位置取个max就是向左最长了,记为L,向右最长为R

那么中序遍历一个区间对应原树的一颗子树,如果这个区间里有一个L比l小,R比r大那么一定可以作为跟,并划分开递归下去qwq

所以最后我们发现直接递归n^2,要用下启发式分裂,从两侧同时跳才行,这样就是O(nlogn)了,相当于启发式合并的逆操作

当然,我们也可以想笛卡尔树一样去维护右链和栈来构造答案qwq虽然O(n)但复杂度不变

首先可以直接树剖,然后每个点维护轻子树中点深度最大点-2*这个点深度,然后再把这个值+点u的深度就是以这个点做lca的答案了然后处理修改时可以用一个线段树维护下每个点的深度,因为dfn序连续的一段是边v下边深度受影响的

然后不断的向上挑重链,用第二棵线段树区间查询一个重链的答案最大值qwq

你会发现修改一条重链是可以同时改的,因为一条祖先重链的信息是没有变化的啊,u肯定不是他的轻儿子,所以不管就好的qwq

子树内的信息可以直接区间加法啊,然后答案要相应变化一下

当然我们还可以动态维护树的直径,然后答案另一端点一定是树直径了qwq,树的直径和深度都可以用线段树维护

完结散花!

夏晓光(loveJY)的博客