A.小睿睿的等式
题目分析
送温暖题
注意不要对每个数暴力拆分算，对于每个数预处理即可
时间复杂度：O(n)
B.小睿睿的询问
题目分析
送温暖题++
ST表O(1)即可解决
为了鼓励多种写法，特意在生成数列时限制各数的大小<100
时间复杂度：O(nlogn+m)
C. 小睿睿的方案
题目分析
总方案数易求，考虑不合法的方案数：
每对情侣对方案的负贡献：
当两个结点非祖先-后代关系时，两个结点的子树间的路径方案数
当两个结点为祖先-后代关系时，贡献为后代的子树与（整颗树除祖先子树的部分+祖先子树除 祖先含后代的子树）间的路径方案数
考虑用一n*n的矩阵里的三角形来表示方案数，矩阵上(i,j)或(j,i)点表示i与j的方案是不合法的，那么用dfs序来映射点，一个点的子树的dfs序连续，每个贡献可以表示为若干矩形区域，那么用线段树+扫描线即可计算出不合法的方案数
注意与矩阵对角线对称的点应同时更新
时间复杂度：O(nlogn)
题解及代码Link：https://mczhuang.cn/?p=2106
全部评论
(1) 回帖