分治
Advanced Competitive Programming
2/17
這堂課不會講技巧，全都是例題講解。
希望大家邊聽邊想，時不時會抽人回答問題。
例題：區間和小於t
給一個長度為\(n\)的序列，有幾個子區間的總和會小於\(t\)
\(1 \leq n \leq 2*10^5\)，\(\left| t \right| \leq 10^{14}\)
這題雖然有資結作法，但我們這裡用分治的方法想一下
想一下怎麼把小區間的答案轉移到大區間
當兩個小區間長這樣，這時候有一段連續的區間和小於\(t\)
不難發現你會用到左區間的後綴和加上右區間前綴和
這個例子為5+11
可以把左區間的後綴和排序，右區間的每個前綴和用二分搜去找左區間的有幾個後綴和可以相加<\(t\)
算出來的答案數量相加為答案
分治的難點在於要去思考小區間怎麼去計算答案，然後把小區間算答案的方式帶到大區間
接下來用更多例題帶大家思考🐳
例題：太陽軍團(互動題)
給你一個不知道長怎樣，很大很大的\(N*M\)陣列，你可以多次詢問某一格的值是多少，且已知每一列的最大值出現位置都在上一列最大值的右邊，請你找出每一列的最大值出現在哪裡。
\(2 \leq N \leq M \leq 10^6\)，最多詢問\(10^8\)次
直接暴力\(O(NM)\)檢查每個格子顯然是不行的
要怎麼用分治來解這題呢，給大家幾分鐘時間想一下
我們可以先找中間那排，用一次\(O(M)\)掃過去，找最大值在哪
因為這題的最大值有單調性的限制，所以右上角和左下角絕對不會有最大值，剩下紅色部分的陣列要找
一直二分下去，複雜度是\(O(MlogN)\)
例題：糟糕陣列
給你一個\(N\)，你要生出\(N*N\)的二維陣列，對於所有\(i\) \((1 \leq i \leq N)\)，使得「第\(i\)列的所有數值」和「第\(i\)行的所有數值」聯集起來為{\(1,2,...,2N-1\)}
\((1 \leq N \leq 1024)\)，存在一正整數\(K\)使得\(N=2^k\)
一樣先想一下怎麼分治:D，你可以隨便生一個\(4*4\)的陣列放數字看看，也可能需要通靈一下
試著把一個數字放在(i,i)的位置
再把一個數字亂放在某個位置上，像是把2放在紅色的位置，會有以下兩種可能，那我們要取哪種呢
既然我們分治的觀念是解決小問題合併到大問題
那相同的小問題重複越多越好，我們寫code就不用思考太多
我們盡量把左上四塊、右下四塊長得一樣
無腦填3，剩下[4,5,6,7]
隨便填4，假設放在下面紅色的位置，會有兩種可能
經過一番亂填之後，上面的這兩種可能 可能會長得像這樣
看起來好像都是對的，那哪個比較好做、有規律呢？
對於左邊的圖，你要去紀錄左下角\(2*2\)方格的4,5,6,7放在哪裡
再去放右上角\(2*2\)方格的4,5,6,7
左下角和右上角的排列方式會不太一樣
反觀右邊的圖
左下角\(2*2\)方格只有4,5兩種數字，右上角\(2*2\)方格只有6,7兩種數字
並且排列方式基本一模一樣
既然排列方式一模一樣，不難發現這可能就是解決這題的一種方法
可以試試在這個二維方格切兩刀，分成四個\(2*2\)方格
在1~7這些數字中
選1,2,3到左上右下、4,5到左下、6,7到右上
按照規律去排數字
因為每次都是分成大小一樣的四塊，往下遞迴左上左下右上三塊，加上要填完所有的格子，複雜度為\(O(3^{logN}+N^2)\)
例題：Max to the right Min
給一個長度為\(n\)的序列，序列為\(1\)~\(n\)的permutation，有幾個子區間符合「區間中最大的數字出現在區間中最小的數字右邊」。
思考時間:D
先透露這裡分治要二分，如果說兩個小區間的答案已經算完了，目前只要思考如何計算跨越兩個區間的答案就好了
可以仔細想一下有哪些case要考慮？
-
最大在右邊，最小在左邊
-
最大和最小值都在左邊
-
最大和最小值都在右邊
你想到了嗎：D
不難發現你可能會需要前綴、後綴、最小值、最大值這些東西
所以我們弄出來左區間的後綴最小最大值、右區間的後綴最小最大值
先來處理第一個case
對於一個合理的區間\([L',R']\)，需要符合兩個情況
- 後綴最小值 \(_{L'} <\) 前綴最小值 \(_{R'}\)
- 後綴最大值 \(_{L'} <\) 前綴最大值 \(_{R'}\)
因為這些前綴後綴最小最大值們都有單調性，你要找符合兩個情況的數字可以用二分搜分別去找。
那他們交集的位置就是L'可能的位置
你可以掃過右區間的每個位置當作R'，做一遍。
這個case就解決了
關於第二個case，最大和最小值都在左邊，看一下合理的區間[L',R']有什麼性質
沒錯！！！！！就是
- 後綴最小值 \(_{L'} <\) 前綴最小值 \(_{R'}\)
- 後綴最大值 \(_{L'} >\) 前綴最大值 \(_{R'}\)
所以其實跟第一個case一樣可以利用二分搜找到交集的位置
還要多判斷左區間的Max有沒有在左區間的Min右邊
第三個case也是大同小異。
總體複雜度是\(O(nloglogn)\)，上述所講的二分搜可以用雙指針優化成\(O(nlogn)\)，大家可以自己想一下怎麼移指針：D
例題：好的連續子序列😈
給一個長度為\(n\)的序列，序列為\(1\)~\(n\)的permutation，有幾個子區間里的元素排序之後是公差為\(1\)的等差數列。
\(1 \leq n \leq 5\cdot 10^5\)
一樣，思考時間:D
這裡給點提示，定義\(Max\)是子區間的最大值、\(Min\)是子區間的最小值：
- 一個區間\([L,R]\)要滿足：
\(R-L+1=\)\(Ｍax\)\(-\)\(Min\)\(+1=\)區間長度 - 橫跨中間的子區間又要分成幾種情況？
誒，好像跟上一題類似，這裡分4個case
-
最小值和最大值都在左區間
-
最小值和最大值都在右區間
-
最小值在右區間，最大值在左區間
-
最小值在左區間，最大值在右區間
你想到了嗎：)
先講第一個case，講完之後你就會做第二個case了
一樣需要前綴後綴最大值最小值
用下面的區間來舉例
第一個case為：「最大值和最小值都在左區間」
你可以先決定一個\(L'\)指針代表一個合法的區間左界觀察看看
假設\(L'\)在下圖的這個位置
既然這個case叫：「最大值和最小值都在左區間」
那圖中已經赤裸裸地跟你講了最大值和最小值應該要是多少
提示一：\(R-L+1=\)\(Ｍax\)\(-\)\(Min\)\(+1\)
有了最大值、最小值、以及\(L'\)在哪個地方。
區間長度和、\(R'\)的位置就可以得出來了
要滿足最大值和最小值都在左邊
那右邊一定不能出現更大的值或更小的值
所以要去檢查\(R'\)的前綴最大值和最小值
經過檢查之後發現他是一個合理的區間
你可以把\(L'\)從\(L\)到\(mid\)計算一遍
那第二個case也是相同道理
好的，相對難的case要來了
接著是第三個case：「最小值在右區間，最大值在左區間」
觀察這兩個區間，用一個合理的\([L',R']\)，來想想要怎麼做
首先，既然最小值在右區間，最大值在左區間的話
代表
- 後綴最小值 \(_{L'} >\) 前綴最小值 \(_{R'}\)
- 後綴最大值 \(_{L'} >\) 前綴最大值 \(_{R'}\)
會發現好像跟上一題一樣
可以用雙指針或二分搜找到合理的區間
圖中的例子可以找到兩個合理的\(R'\)
這時候有一個問題？
兩個\(R'\)都可以採用嗎？
你會發現偏左的\(R'\)不能是一個合理的\(R'\)
它不滿足\(R-L+1=\)\(Ｍax\)\(-\)\(Min\)\(+1\)這個式子
\(R-L+1=\)\(Ｍax\)\(-\)\(Min\)\(+1\)這個式子我們可以化簡成
\(R+Min=L+Max\)
因此我們要找哪些\(R'\)滿足上面這個式子
由於\(L'\)已經確定了，代表\(L'+Max\)為一個定值
右邊有很多種\(R'+Min\)，你可以用一個陣列\(cnt\)紀錄每種\(R'+Min\)的次數，然後找\(cnt[L'+Max]\)就好了
來練習8
題目連結