有哪些分塊好題，最好是純資料結構做不了的？

1樓：RhmBWT

你可以看看YNOI2018

裡面好多分塊題的

Problem 5143. -- [Ynoi2018]五彩斑斕的世界Problem 5144. -- [Ynoi2018]末日時在做什麼？有沒有空？可以來拯救嗎？

Problem 5145. -- [Ynoi2018]未來日記（感覺比無腦分塊好一些的）

2樓：

退役多年的老鹹魚厚顏無恥地來強答一發

bzoj3744和bzoj3787

似乎的確不分塊是做不了的，至於算不算好題，只能說當年我和@AutSky JadeK 出這道題的時候還沒見過一樣的idea，雖然實現難度和思維難度都算不上多大。

時過境遷，各奔東西，大概唯一沒怎麼變化的就是我們仍然沒有妹子吧（x

3樓：艾慶興

Kth這個題啊，用莫隊還是可以的，假設你現在已經知道了區間[L,R]的第k大了，並且為之維護了乙個線段樹，以權值作為下標插入了[L,R]之間的每乙個數字。那麼，[L,R+1]這個區間的第K大，利用[L,R]的結果，你可以在O（logn）的時間做出來，[L,R-1]顯然也可以。

那麼，如果我們能把詢問的這些區間合理的安排，使得相鄰的區間不一樣的元素個數並不多，那麼複雜度就降下來了，這個做法就是莫隊了（莫濤大神發明的，他應該親自來答）。

把所有詢問排序，排序的規則如下：如果L在同乙個塊內（每sqrt(n)分一塊），那麼按R遞增排序，如果L不在同乙個塊內，按L所在塊排序，這樣詢問相當於被分為了sqrt(n)個部分，每個部分裡面，R遞增，L相差不超過sqrt(n)。

那麼，對於每乙個塊來說，任何相鄰兩個點，L的差最多sqrt(n)，塊內R的差，一共是n。

一共sqrt(n)個塊，L最多要走sqrt(n) * n歩（每個L最多走sqrt(n)就能走到下乙個L），而R最多要走sqrt(n) * n歩（一共sqrt(n)個塊，每個塊內的R一共走n歩）。

所以問題就解決了，複雜度nsqrt(n)*logn + Qlogn

現在來考慮有沒有辦法把線段樹替換掉，顯然是有的：

我們呢，把權值可取的範圍MAXN，分成sqrt(MAXN)塊，維護這樣兩個陣列：

num[i]：第i個塊內有多少個元素

vis[i]：數字i出現了多少次

對於每乙個詢問的區間[L,R]，首先通過莫隊轉移到這個區間，然後，求第K大，就是個sqrt(MAXN)複雜度的暴力了，一共Q組詢問，複雜度就是Qsqrt(MAXN)，總複雜度：

nsqrt(n)*logn+Qsqrt(MAXN)。