线性结构 —— 分块算法 —— 分块九讲
模型1:區(qū)間加法,單點(diǎn)詢問(wèn)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,以及 n 個(gè)操作,操作涉及區(qū)間加法,單點(diǎn)查值。
對(duì)每個(gè)塊設(shè)置一個(gè)加法標(biāo)記,記錄這個(gè)塊中元素一共加了多少,每次操作對(duì)整塊直接 O(1) 標(biāo)記,而不完整塊元素較少,暴力修改元素的值即可,每次詢問(wèn)時(shí)返回元素的值加上其所在塊的加法標(biāo)記。
模型2:區(qū)間加法,詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的元素個(gè)數(shù)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,以及 n 個(gè)操作,操作涉及區(qū)間加法,詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的元素個(gè)數(shù)。
對(duì)于區(qū)間操作,其實(shí)只有三項(xiàng)東西需要思考:
- 要預(yù)處理的信息
- √n?個(gè)整塊的處理
- 不完整塊的 2√n?個(gè)元素的處理
考慮詢問(wèn)的情況:對(duì)于不完整的塊的 2√n?個(gè)元素,直接枚舉統(tǒng)計(jì)即可,而在整塊內(nèi)尋找小于某個(gè)值的元素,暴力枚舉的時(shí)間復(fù)雜度過(guò)高,因此考慮使用二分查找,這就要求塊內(nèi)元素是有序的,因此需要在預(yù)處理時(shí)對(duì)每塊做一遍排序,每次查詢?cè)?√n 個(gè)塊內(nèi)二分,然后暴力不完整塊的 2√n 個(gè)元素即可
再考慮區(qū)間操作的情況:區(qū)間操作仍為區(qū)間加法,這樣就可以套用 模型 1 的方法,維護(hù)一個(gè)加法標(biāo)記,但不同的地方在于,不完整塊修改后,可能會(huì)使得該塊內(nèi)數(shù)字亂序,所以頭尾兩個(gè)不完整塊需要進(jìn)行重新排序
這樣一來(lái),在加法標(biāo)記下的詢問(wèn)操作,在塊外暴力查詢小于 (x-加法標(biāo)記) 的元素個(gè)數(shù),塊內(nèi)使用 (x-加法標(biāo)記) 作為二分查找的值即可
模型3:區(qū)間加法,詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的前驅(qū)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,以及 n 個(gè)操作,操作涉及區(qū)間加法,詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的前驅(qū)。
所謂前驅(qū),是指對(duì)于某個(gè)值 x ,比其小的最大元素
該模型可以延續(xù) 模型 2 的方法,將塊內(nèi)查詢的二分進(jìn)行修改,由于是要找的是 x 的前驅(qū),因此暴力找左右不完整塊的比 x 小最大值,再二分找整塊比 x 小的最大值,取其中最大即可
模型4:區(qū)間加法,詢問(wèn)區(qū)間和
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,以及 n 個(gè)操作,操作涉及區(qū)間加法,詢問(wèn)區(qū)間和。
相較于 模型 1 來(lái)說(shuō),該模型只是將單點(diǎn)詢問(wèn)改為了區(qū)間詢問(wèn),不完整塊仍是需要暴力,而要快速統(tǒng)計(jì)整塊的答案,需要維護(hù)每個(gè)塊的元素和,這就需要進(jìn)行預(yù)處理。
在預(yù)處理時(shí):求得每個(gè)塊內(nèi)的和,修改時(shí)對(duì)于邊角料暴力修改值,修改了 a[i] 的值同時(shí)也要把 a[i] 所在塊的值修改,對(duì)于中間的 k 塊,修改標(biāo)記 tag[i],表示第 i 個(gè)塊加上了 tag[i],簡(jiǎn)單來(lái)說(shuō),即整塊用一個(gè) ans 數(shù)組來(lái)維護(hù)整塊的和,不完整的塊直接暴力加
在詢問(wèn)時(shí):在 tag 里記下對(duì)于一個(gè)塊一共加上了多少,然后對(duì)于邊角料的處理與模型 1 類似,暴力+a[i]+tag[pos[i]],對(duì)于中間的 k 塊,加上 ans[i],因?yàn)槠渲杏?block 個(gè)數(shù),因此要加 block 個(gè) tag[i]
模型5:區(qū)間開(kāi)方,詢問(wèn)區(qū)間和
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,數(shù)列中的元素最大為 2^31-1,以及 n 個(gè)操作,操作涉及區(qū)間開(kāi)方,詢問(wèn)區(qū)間和。
由于在整塊開(kāi)方時(shí),必須要知道每一個(gè)元素才能知道他們開(kāi)方后的和,難以快速的對(duì)一個(gè)塊進(jìn)行信息更新,但不難發(fā)現(xiàn),修改操作只有向下取整開(kāi)方,而一個(gè)數(shù)經(jīng)過(guò)幾次開(kāi)方后,其值最終會(huì)變成 1
因此,如果每次區(qū)間開(kāi)方只涉及不完整塊,那么仍然對(duì) 2√n 個(gè)元素直接暴力‘;如果涉及到整塊,由于這些塊經(jīng)過(guò)若干次操作后都變?yōu)?1,此時(shí)可采用一種分塊優(yōu)化的暴力,即只要每個(gè)整塊開(kāi)方后,記錄元素是否都變成了 1,這樣在區(qū)間修改時(shí),可以設(shè)置一個(gè) flag 數(shù)組,用于標(biāo)記塊中元素是否全為 1,若是,則跳過(guò)那些全為 1 的塊即可,若不是,則對(duì)塊中元素進(jìn)行暴力,由于數(shù)列中的元素最大為?2^31-1,因此最多開(kāi)方 5 次后就為 1,時(shí)間復(fù)雜度在允許范圍之內(nèi)
模型6:單點(diǎn)插入,單點(diǎn)詢問(wèn)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,操作涉及單點(diǎn)插入,單點(diǎn)詢問(wèn),數(shù)據(jù)隨機(jī)生成。
可以在塊內(nèi)維護(hù)數(shù)組以為的數(shù)據(jù)結(jié)構(gòu)使其更具有拓展性,比如在每個(gè)塊內(nèi)存放?vector、set、multiset 等數(shù)據(jù)結(jié)構(gòu)?,這樣如果還有插入、刪除元素的操作,會(huì)更加的方便。
對(duì)于本模型來(lái)說(shuō),數(shù)據(jù)是隨機(jī)生成的,可以在每塊內(nèi)維護(hù)一個(gè) vector,每次插入時(shí)找到位置所在的塊,再暴力插入,將塊內(nèi)其他元素直接向后移動(dòng)一位,這樣來(lái)實(shí)現(xiàn)插入操作,時(shí)間復(fù)雜度不會(huì)太高。
但對(duì)于數(shù)據(jù)不是隨機(jī)的情況,如果在一個(gè)塊內(nèi)有大量的單點(diǎn)插入,會(huì)使得這個(gè)塊的大小超過(guò) √n,這樣對(duì)塊內(nèi)暴力的復(fù)雜度就沒(méi)有保證了,此時(shí)需要引入一個(gè)新的操作:重構(gòu),即重新分塊。
重構(gòu),是每 √n 次插入后,重新將數(shù)列進(jìn)行分塊,由于重構(gòu)所需的時(shí)間復(fù)雜度為 O(n),重構(gòu)次數(shù)為 √n,因此重構(gòu)的時(shí)間復(fù)雜度沒(méi)有問(wèn)題,且保證了每個(gè)塊的大小相對(duì)均衡。
模型7:區(qū)間乘法與加法,單點(diǎn)詢問(wèn)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,操作涉及區(qū)間乘法,區(qū)間加法,單點(diǎn)詢問(wèn)。
顯然,如果只有區(qū)間加法或區(qū)間乘法,那么與 模型 1 沒(méi)有本質(zhì)區(qū)別,但當(dāng)兩者同時(shí)出現(xiàn),需要考慮如何同時(shí)維護(hù)兩種標(biāo)記。
對(duì)于整塊來(lái)說(shuō),由于加法操作會(huì)影響乘法操作的值,因此令乘法標(biāo)記的優(yōu)先級(jí)高于加法標(biāo)記的優(yōu)先級(jí),則有:
- 若當(dāng)前的一個(gè)塊乘以 m1 后加上 a1,此時(shí)再進(jìn)行一個(gè)乘以 m2 的操作,那么原來(lái)的標(biāo)記變?yōu)?#xff1a;m1*m2、a1*m2
- 若當(dāng)前的一個(gè)塊乘以 m1 后加上 a1,此時(shí)再進(jìn)行一個(gè)加上?a2 的操作,那么原來(lái)的標(biāo)記變?yōu)?#xff1a;m1,a1+a2
因此,可以用 addTag[i] 來(lái)存放第 i 個(gè)整塊的加數(shù),mulTag[i] 存放第 i 個(gè)整塊的系數(shù),當(dāng)一個(gè)整塊進(jìn)行乘法操作乘以 x 時(shí),兩個(gè)標(biāo)記都要乘以 x,即:addTag[i]=addTag[i]*x,mulTaf[i]=mulTag[i]*x
對(duì)于不完整塊來(lái)說(shuō),由于前面的操作可能將其當(dāng)作完整塊處理,因此每次不完整塊都要更新為最新的值后再進(jìn)行暴力
模型8:詢問(wèn)區(qū)間某值個(gè)數(shù),區(qū)間賦值
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,操作涉及區(qū)間詢問(wèn)等于一個(gè)數(shù) x?的元素,并將這個(gè)區(qū)間的所有元素改為 x。
區(qū)間賦值沒(méi)有什么難度,但區(qū)間查詢比較難,因?yàn)闄?quán)值種類比較多,似乎沒(méi)有什么好的維護(hù)方法
但通過(guò)模擬一些數(shù)據(jù)可以發(fā)現(xiàn),詢問(wèn)后一整段區(qū)間都會(huì)被修改,幾次詢問(wèn)后數(shù)列可能就只剩下若干個(gè)不同的區(qū)間了
考慮使用 模型 5 的方法,采用分塊優(yōu)化的暴力,建立一個(gè)標(biāo)志數(shù)組,在維護(hù)每個(gè)整塊的時(shí)候,判斷該塊是否只有一種權(quán)值,這樣在區(qū)間操作的時(shí)候,對(duì)于同權(quán)值的一個(gè)塊能在 O(1) 即可統(tǒng)計(jì)答案,若不是只有一種權(quán)值,那么就暴力統(tǒng)計(jì)答案,然后修改標(biāo)記,而對(duì)于不完整塊,同樣使用暴力維護(hù)
這樣一來(lái),最差的情況每次都會(huì)消耗 O(n) 的時(shí)間,但實(shí)際上,可以這樣進(jìn)行分析:假設(shè)初始序列都是同一個(gè)值,那么查詢是 O(√n),如果此時(shí)進(jìn)行一個(gè)區(qū)間操作,其最多破壞首尾兩個(gè)塊的標(biāo)記,因此只能使后面的詢問(wèn)至多多兩個(gè)塊的暴力時(shí)間,因此均攤后每次操作的復(fù)雜度仍為 O(√n),簡(jiǎn)單來(lái)說(shuō),要想讓一個(gè)操作花費(fèi) O(n) 的時(shí)間,就要先花費(fèi) √n 個(gè)操作對(duì)數(shù)列進(jìn)行修改
模型9:詢問(wèn)區(qū)間眾數(shù)
問(wèn)題:給出一個(gè)長(zhǎng)為 n 的數(shù)列,以及 n 個(gè)操作,操作涉及詢問(wèn)區(qū)間的最小眾數(shù)。
分塊算法的優(yōu)越性之一在于能詢問(wèn)區(qū)間眾數(shù),這是線段樹(shù)解決不了的問(wèn)題
對(duì)于 n 個(gè)數(shù)的序列,首先進(jìn)行分塊,預(yù)處理兩塊之間的眾數(shù),將兩塊間的最小眾數(shù)記錄下來(lái),然后再進(jìn)行查詢
在每次查詢時(shí),首先將中間的整塊的眾數(shù)記錄下來(lái),然后再依次處理左邊角料和右邊角料,二分尋找是否能夠更新,最后處理完成后,返回尋找到的值即可
值得注意的是,在進(jìn)行分塊時(shí),有時(shí)題會(huì)卡常數(shù),即將塊分為 √n 時(shí)仍會(huì) TLE,此時(shí)需要用兩塊分塊大小不同的代碼對(duì)拍,根據(jù)運(yùn)行時(shí)間來(lái)不斷調(diào)整分塊大小,以減少常數(shù)
總結(jié)
以上是生活随笔為你收集整理的线性结构 —— 分块算法 —— 分块九讲的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: 信息学奥赛一本通(1002:输出第二个整
- 下一篇: 图论 —— 图的连通性 —— Tarja