馬大師的分塊練習

• 2021 年 12 月 9 日
• 筆記
• 分塊

[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)\) 的了。