or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
分治
Advanced Competitive Programming
2/17
這堂課不會講技巧,全都是例題講解。
希望大家邊聽邊想,時不時會抽人回答問題。
例題:區間和小於t
給一個長度為\(n\)的序列,有幾個子區間的總和會小於\(t\)
\(1 \leq n \leq 2*10^5\),\(\left| t \right| \leq 10^{14}\)
這題雖然有資結作法,但我們這裡用分治的方法想一下
想一下怎麼把小區間的答案轉移到大區間
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →當兩個小區間長這樣,這時候有一段連續的區間和小於\(t\)
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →不難發現你會用到左區間的後綴和加上右區間前綴和
這個例子為5+11
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →可以把左區間的後綴和排序,右區間的每個前綴和用二分搜去找左區間的有幾個後綴和可以相加<\(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',做一遍。
這個case就解決了
關於第二個case,最大和最小值都在左邊,看一下合理的區間[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\)是子區間的最小值:
\(R-L+1=\)\(Max\)\(-\)\(Min\)\(+1=\)區間長度
誒,好像跟上一題類似,這裡分4個case
最小值和最大值都在左區間

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

最小值在右區間,最大值在左區間

最小值在左區間,最大值在右區間

你想到了嗎:)
先講第一個case,講完之後你就會做第二個case了

一樣需要前綴後綴最大值最小值
用下面的區間來舉例
第一個case為:「最大值和最小值都在左區間」

你可以先決定一個\(L'\)指針代表一個合法的區間左界觀察看看
假設\(L'\)在下圖的這個位置
既然這個case叫:「最大值和最小值都在左區間」
那圖中已經赤裸裸地跟你講了最大值和最小值應該要是多少
提示一:\(R-L+1=\)\(Max\)\(-\)\(Min\)\(+1\)

有了最大值、最小值、以及\(L'\)在哪個地方。
區間長度和、\(R'\)的位置就可以得出來了
要滿足最大值和最小值都在左邊

那右邊一定不能出現更大的值或更小的值
所以要去檢查\(R'\)的前綴最大值和最小值
經過檢查之後發現他是一個合理的區間
你可以把\(L'\)從\(L\)到\(mid\)計算一遍
那第二個case也是相同道理
好的,相對難的case要來了

接著是第三個case:「最小值在右區間,最大值在左區間」
觀察這兩個區間,用一個合理的\([L',R']\),來想想要怎麼做
首先,既然最小值在右區間,最大值在左區間的話
代表
會發現好像跟上一題一樣

可以用雙指針或二分搜找到合理的區間
圖中的例子可以找到兩個合理的\(R'\)
這時候有一個問題?

兩個\(R'\)都可以採用嗎?
你會發現偏左的\(R'\)不能是一個合理的\(R'\)
它不滿足\(R-L+1=\)\(Max\)\(-\)\(Min\)\(+1\)這個式子
\(R-L+1=\)\(Max\)\(-\)\(Min\)\(+1\)這個式子我們可以化簡成
\(R+Min=L+Max\)
因此我們要找哪些\(R'\)滿足上面這個式子
由於\(L'\)已經確定了,代表\(L'+Max\)為一個定值
右邊有很多種\(R'+Min\),你可以用一個陣列\(cnt\)紀錄每種\(R'+Min\)的次數,然後找\(cnt[L'+Max]\)就好了
來練習8
題目連結