马大师的分块练习马大师的分块练习

[COCI2006-2007#4] ISPITI link
Solution 思路还挺好想的，就是先按 b 排序，然后按时间顺序一个一个加就好了。实现起来确实是有点麻烦。
[COCI2020-2021#6] Index link
Solution

正经人谁写分块啊？你写么？
不写！你写么？
不写！
下贱！

序列 link
Solution 【马大师的分块练习】挺有意思的。你发现 \([l,r]\) 加上 \(v\) 可以拆成 \([l,n]\) 加 \(v\)，\([r+1,n]\) 加 \(-v\)。那么我们就可以扫描线过去，相当于后缀加值，再前缀查排名。
\(\Theta(n\sqrt n\log n)\)。
[APIO2019]桥梁 link
Solution 我们考虑把询问分块，那么对于一个块，我们就可以做到 \(\Theta(m\log n+S^2\log n)\)。
[Ynoi2011] 初始化 link
Solution 直接值域分块，对于 \(\le \sqrt n\)，你发现相当于 \(i\equiv y\pmod x\) 的位置加上 \(v\)，直接求个前缀和后缀就好了。
复杂度 \(\Theta(n\sqrt n)\)。
[Ynoi2077] stdmxeypz link
Solution 你可以发现可以把树摊下来，然后区间的限制可以拆成后缀的限制，然后我们可以用 cdq 分治做到类似于上面一题。
复杂度 \(\Theta(n\sqrt n\log n)\)，可以加一些剪枝进行优化。
[Ynoi2009] rla1rmdq link
Solution 你发现对于一个块，可以维护一个答案集合使得走过的路径总点数 \(\le n\)，那么我们复杂度就是 \(\Theta(n\sqrt n)\) 的了。