P5445记录中提到的内容是什么？

收获比较大，就从做题记录与反思中单独拿出来了 首先注意到修改 \([i , i + 1]\) 只影响了 query([l , i] , [i + 1 , r]) ，其中 \(l\) 是与 \(i\) 相连通的最左的节点，\(r\) 是与 \(i + 1\) 相连通的最右的节点 询问是求有多少个时刻联通。可以把时间看作权值，\(i\) 时刻联通就将询问 \(+(q - i)\)，\(i\) 时刻断开就 \(-(q - i)\) 问题变为了矩阵加，单点求和。差分一下，变为单点加，前缀矩阵求和。 用动态开点线段树套树状数组。即可解决 总共要写三棵树，一棵用来维护是与 \(i\) 相连通的最左最右的节点，另外两颗是树套树 疑问：这个问题已经很久没有解决了。不会算线段树的空间复杂度。从 \(maxn \times 20\) 开到 \(\times 40\)，\(\times 60\) 最后到 \(\times 80\)，终于过了。提交记录 与教练讨论并查看 luogu 讨论区，得出结论：最坏情况下要开 \(4 q log^2 n\)。这是绝对MLE的。至于为什么能过，只不过数据没有卡我们罢了 代码都快200行了，题解才100出头。