Source and Judge
Analysis
dffxtz师兄出的题
做法一:
暴力树剖+分块,时间复杂度为 $O(nlogn\sqrt n)$
做法二:
利用矩阵乘法的优秀性质,树剖
时间复杂度为 $O(8nlog^2 n)$
做法三:
考虑时间倒流,考虑每次操作1的增量的总系数,就是后面有多少次操作2
不太好整体做,不妨考虑树上启发式合并,树状数组边插边弄
时间复杂度为 $O(nlog^2 n)$
做法四:
把树上启发式改为线段树合并,开两棵以时间为下标的动态开点线段树
统计答案就是类似cdq的过程,而复杂度则和合并是一样的
时间复杂度为 $O(nlogn)$
1 | //Zory-2019 |