<style type="text/css"> .slides { text-align: left !important; } </style> # 根號分塊 #### Author:H1de_on_bruH ---- ## 概要 根號RMQ 根號分塊 --- ## 淺談分塊:RMQ(Range Maxium Query) 給你一個長為$N$的數列 詢問$Q$次$[L,R]$區間的最大值 $(1\le N,Q\le 10^5)$ ---- ### 想法1 爆搜 對每次詢問的[L,R]爆搜 也就是直接從L遍歷到R 直接找最大值 複雜度$O(NQ)$ ---- 算法可以說是對的 但是效率太差了 絕對會超時的 那有沒有加速的方法? ---- ### 想法2 切塊 那我在詢問前預先把這個序列先切成一塊一塊的 這樣只要這塊在L,R裡面 我就可以直接存取這塊的訊息  ---- #### 怎麼切? 要怎麼切才可以讓複雜度健康一點呢? ---- 假設我們切成$K$個 每個長 $\frac{N}{K}$ 邊邊不足一塊的地方我們用爆搜的 最多有$2 \cdot (\frac{N}{K}-1)$個 這邊的複雜度是$O(\frac{N}{K})$ 塊狀的也是 把每一塊在範圍內的用爆蒐的看完 最多會有$K$塊 複雜度$O(K)$  ---- 這樣切的話複雜度會是$O(Q\cdot (K+\frac{N}{K}))$ 利用算幾不等式 $\frac{K+\frac{N}{K}}{2}\ge \sqrt{K\cdot \frac{N}{K}}=\sqrt{N}$ 所以我們只要切成$\sqrt{N}$塊就可以把複雜度壓到$O(Q\sqrt{N}+N)$ :::spoiler 還可以更快 但通常我們都會用其他更快的做法去做這個題目(線段樹、稀疏表等，複雜度為$O(NlogN)$) 不過這個做法算比起其他的來說相對直觀 也不失為一個認識根號分塊的好例子 ::: --- ## 根號分塊例題 [Atcoder競プロ典型90問:no.83](https://atcoder.jp/contests/typical90/tasks/typical90_ce) 給你$N$個節點$M$個邊的圖 並且要回應$Q$次操作 每次操作輸入$x,y$ 先輸出$x$點目前的顏色 再將$x$點跟$x$點周遭所有顏色都塗成$y$色(每個點一開始的顏色都是1) ($1\le N,M,Q\le 2\cdot 10^5$) ---- ### 想法 一樣思考分塊 也就是說考慮各個點他所相鄰的點的數量 假設一個點有$\sqrt{N}$以上個相鄰的點的時候 我們稱他為重點 剩餘的稱為輕點 ---- 顏色打在輕點上 我們可以直接爆搜更改周圍的點 那如果是重點呢? ---- #### 先不要打下去? 對 就是先不要打下去 ---- 要詢問這個點的時候再去看周圍的重點 看自己身上的點和周圍的重點哪個比較晚打下去 最晚打下去的那個顏色就是該點現在的顏色 那因為重點數量最多$\sqrt{N}$個 所以時間複雜度是 $O(Q\sqrt{N})$ --- 根號分塊其實是個很少見的算法 我個人覺得蠻直觀 感覺也很酷 有時候分塊也不一定是切成根號 題目的設定也可以很有趣 題目多寫就可以碰到更加有趣的東西 ---- # {感謝各位|夕張超可愛的>w<}