100+70+70+20=260
感觉如果时间够感觉还能写一下，结果T3超大数据结构写死了
T1
观察到最短路径仍然最优，直接dij即可，注意判断终点不用等红灯
T2
暴力是\(O(n^4)\)的，是dp，但是我写的是分层图，同样时间，还没有优化空间，寄
设计\(dp_{i,j}\)为跳到\((i,j)\)所需最小花费
每次从所有点转移，算曼哈顿距离
\[dp_{i,j}=min(dp_{i',j'})+|i-i'|+|j-j'| \]假如从左上角转移，柿子就可以写成
\[dp_{i,j}=min(dp_{i',j'}-i'-j')+i+j \]发现可拆，直接分层扫描x轴维护上述柿子即可
正着扫一遍处理第3，4象限
反着扫一遍处理第1，2象限
时间复杂度:\(O(n\log n)\)
T3
考场写出来了树上莫队，但是维护丑了，用了bitset，复杂度多一个\(\frac{n}{w}\)，没有这部分的部分分，沦为暴力70分
树上莫队不用说，维护询问，主要的是如何维护curans，我们插入一个数，最多3个质因数，我们可以想到一个简单的容斥：加上与自己没有重叠质因数的数，减去与自己至少有一个质因数重叠的数，加上至少与自己有两个质因数重叠的数......
依此，我们去枚举x的质因数的组合，并开一个桶记录全局质因数组合的个数，就可以做到上述效果，就不用bitset了
时间复杂度:\(O(q \sqrt n)\)
标签：8.2,重叠,day9,复杂度,70,维护,质因数,dp From： https://www.cnblogs.com/Linnyx/p/17601030.html