---

type: slide

---

<style>
.reveal .slides {
text-align: left;
font-size:35px;
}
</style>

## 分治

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$

算出來的答案數量相加為答案

----

分治的難點在於要去思考小區間怎麼去計算答案，然後把小區間算答案的方式帶到大區間

接下來用更多例題帶大家思考🐳

---

## 例題：[太陽軍團(互動題)](https://neoj.sprout.tw/problem/127/)

給你一個不知道長怎樣，很大很大的$N*M$陣列，你可以多次詢問某一格的值是多少，且已知每一列的最大值出現位置都在上一列最大值的右邊，請你找出每一列的最大值出現在哪裡。
$2 \leq N \leq M \leq 10^6$，最多詢問$10^8$次


----

直接暴力$O(NM)$檢查每個格子顯然是不行的
要怎麼用分治來解這題呢，給大家幾分鐘時間想一下

----

我們可以先找中間那排，用一次$O(M)$掃過去，找最大值在哪

----

因為這題的最大值有單調性的限制，所以右上角和左下角絕對不會有最大值，剩下紅色部分的陣列要找


----

一直二分下去，複雜度是$O(MlogN)$


---

## 例題：[糟糕陣列](https://neoj.sprout.tw/problem/128/)
給你一個$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](https://codeforces.com/problemset/problem/1849/E)

給一個長度為$n$的序列，序列為$1$~$n$的permutation，有幾個子區間符合「區間中最大的數字出現在區間中最小的數字右邊」。

----

思考時間:D
先透露這裡分治要二分，如果說兩個小區間的答案已經算完了，目前只要思考如何計算跨越兩個區間的答案就好了

可以仔細想一下有哪些case要考慮？

----

1. 最大在右邊，最小在左邊

2. 最大和最小值都在左邊

3. 最大和最小值都在右邊
你想到了嗎：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

---

## 例題：[好的連續子序列😈](https://neoj.sprout.tw/problem/788/)

給一個長度為$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

1. 最小值和最大值都在左區間

2. 最小值和最大值都在右區間

----

3. 最小值在右區間，最大值在左區間

4. 最小值在左區間，最大值在右區間

你想到了嗎：)

----

先講第一個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'$都可以採用嗎？
你會發現偏左的<!-- .element: class="fragment" data-fragment-index="1" -->$R'$<!-- .element: class="fragment" data-fragment-index="1" -->不能是一個合理的<!-- .element: class="fragment" data-fragment-index="1" -->$R'$<!-- .element: class="fragment" data-fragment-index="1" -->
它不滿足<!-- .element: class="fragment" data-fragment-index="1" -->$R-L+1=$<!-- .element: class="fragment" data-fragment-index="1" -->$Ｍax$<!-- .element: class="fragment" data-fragment-index="1" -->$-$<!-- .element: class="fragment" data-fragment-index="1" -->$Min$<!-- .element: class="fragment" data-fragment-index="1" -->$+1$<!-- .element: class="fragment" data-fragment-index="1" -->這個式子<!-- .element: class="fragment" data-fragment-index="1" -->

----

$R-L+1=$$Ｍax$$-$$Min$$+1$這個式子我們可以化簡成
$R+Min=L+Max$
因此我們要找哪些$R'$滿足上面這個式子

----

由於$L'$已經確定了，代表$L'+Max$為一個定值
右邊有很多種$R'+Min$，你可以用一個陣列$cnt$紀錄每種$R'+Min$的次數，然後找$cnt[L'+Max]$就好了

---

來練習8
[題目連結](https://vjudge.net/contest/605791)