【题解】牛客练习赛14

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 n的约数
发现询问次数较少，考虑搜索
一个数的约数个数即分解质因数后，每个质因数出现次数+1的乘积
搜索的时候f(i,j,k)表示搜索了前i个质因数，现在乘积为j，上一个质因数出现次数为k
贪心的考虑，可以发现用越小的质因数越好，于是k不增
这样就可以搜出来了

T2 区间的连续段
首先发现可以贪心，这样是O( nm )的
由于k固定，考虑数组中每个位置i向最大的j+1使得a[i..j]的和<=k连边
这个连边的结构是个森林
每次查询即查询树的一条链
可以倍增维护
O( nlogn + mlogn )

T3 区间的值域连续段
扫描线，扫右端点，维护左端点的答案
那个1...10定义k=10
发现每次右端点拓展一个数x的时候只需要更新x-k -> x+k上一次出现的位置按这个分段的答案，也就是只会更新O(k)段答案，于是可以暴力更新
O( nklogn + mlogn )

T4 比较月亮大小
暴力

T5 无向图中的最短距离
考虑用位运算优化
记录f[i][j]表示距离点i <= j的所有点构成的bitset
预处理的时候对于每个点BFS一下，顺便维护这个bitset
查询的时候直接把一堆bitset or起来即可
可以通过此题
O( n^3/w + nm + na/w + q )
当然你也可以选择压位BFS

T6 树
树链剖分
一个点的孩子中只有一个不是重链头，每次修改只会修改 O(log n) 个重链头的值
对于每个点用一个数据结构，维护除了他自己、父亲、重儿子之外所有相邻点的值，自己、父亲、重儿子在询问的时候查找一下就好了
修改 O(log^2n)，查询 O(logn)
考虑优化这个做法
瓶颈在于对 O(logn)个重链头修改时每次要花 O(logn)的时间
我们不必直接修改它们，而是在它们的父亲上打标记，这个儿子被修改了，查询的时候暴力把所有修改过的孩子修改一下
修改的个数可以证明是均摊 O(1)的

证明：
复杂度等价于：
有一棵树，每次操作可以把一条链染黑，或者把一个点一圈染白

后者有一个 O(这一圈里面黑色点个数) 的代价 可以考虑把所有被染白一圈的点的树构成的虚树进行缩链
对这个链进行染黑色的时候即把这一条链都缩到一个点上，每次把一个点一圈染成白色时则把这个点加入虚树，即把这个点从缩的大点里面分离开来，可以发现每次把一个点一圈染白这个操作只会增加 O(1)个点，而链染黑的操作是均摊 O(1) 的
总复杂度O( nlogn + mlogn )

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305