資源簡介

(共76張PPT)
分治算法
2023年高中信息技術教學課件
主要內容
1.分治思想
2.經典問題
3.基于一維的分治
4.基于二維的分治
5.點分治
分治思想
分治(Divide-And-Conquer)就是“分而治之”的意思，其實質就是將原問題分成n個規模較小而結構與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結果就得到原問題的解。
其三個步驟如下：
①劃分問題(Divide)：將原問題分成一系列子問題。
②遞歸解決(Conquer)：遞歸地解各子問題。若子問題足夠小，則可直接求解。
③合并問題(Combine)：將子問題的結果合并成原問題的解。
如快速排序、歸并排序等都是采用分治思想。
分治算法設計過程圖
問題S
問題S
問題S
S的解
問題S1
……
問題S2
問題Si
問題Sn
……
S1的解
……
S2的解
Si的解
Sn的解
……
問題的分解
子集解的合并
遞歸求解子問題
經典問題1—棋盤覆蓋
有一個2k*2k的方格棋盤，恰有一個方格是黑色的，其他為白色。你的任務是用包含3個方格的L型牌覆蓋所有白色方格。黑色方格不能被覆蓋，且任意一個白色方格不能同時被兩個或更多牌覆蓋。如下圖所示為L型牌的4種旋轉方式。
經典問題1—棋盤覆蓋
題目是要求用L型牌覆蓋一個2k*2k的方格棋盤，棋盤有且只有一個黑色方格，且此方格不能被覆蓋。
用分治來解決，把原棋盤平均分為4塊，通過用1個L型牌覆蓋棋盤正中間2*2的區域中的三個格子，把原棋盤分成4塊2k-1*2k-1的方格棋盤,且每塊中只含有一個黑色方格(不能覆蓋的格子)。
此時把原問題分解成4個結構與原問題一樣的子問題，棋盤的大小(邊長)每次減半，最終會出現邊長為1的情況，直接求解即可。
經典問題1—棋盤覆蓋
定義cover(x,y,len,x0,y0)表示求解左上角格子在(x,y)邊長為len,其中(x0,y0)不能覆蓋的棋盤覆蓋方案。
根據黑色格子的位置分為以下四種情況：
情況1：黑點位于左上部分
情況2：黑點位于左下部分
遞歸求解
劃分問題
左上:cover(x,y,len/2,x0,y0)
左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1)
右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2)
右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2)
遞歸求解
劃分問題
左上:cover(x,y,len/2,x+len/2-1,y+len/2-1)
左下:cover(x+len/2,y,len/2,x0,y0)
右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2)
右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2)
經典問題1—棋盤覆蓋
情況3：黑點位于右上部分
情況4：黑點位于右下部分
每個格子只會被處理一次，時間復雜度為O(n^2)，n為棋盤邊長。
遞歸求解
劃分問題
左上:cover(x,y,len/2, x+len/2-1,y+len/2-1)
左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1)
右上:cover(x,y+len/2,len/2,x0,y0)
右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2)
遞歸求解
劃分問題
左上:cover(x,y,len/2,x+len/2-1,y+len/2-1)
左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1)
右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2)
右下:cover(x+len/2,y+len/2,len/2,x0,y0)
經典問題1—棋盤覆蓋—代碼
void cover(int x,int y,int len,int x0,int y0)
{
int t,len1;
if (len==1)return;
t=++tot;
len1=len/2;
if (x0else{board[x+len1-1][y+len1-1]=t;cover(x,y,len1,x0+len1-1,y0+len1-1);}
if (x0>=x+len1&&y0else{board[x+len1][y+len1-1]=t;cover(x+len1,y,len1,x+len1,y+len1-1);}
if (x0=y+len1)cover(x,y+len1,len1,x0,y0);
else{board[x+len1-1][y+len1]=t;cover(x,y+len1,len,x+len1-1,y+len1);}
if (x0>=x+len1&&y0>=y+len1)cover(x+len1,y+len1,len1,x0,y0);
else{board[x+len1][y+len1]=t;cover(x+len1,y+len1,len1,x+len1,y+len1);}
}
經典問題2—歸并排序
給定一個長度為N的序列，對其進行排序。
歸并排序思想：
1.劃分問題：把長度為N的序列盡可能均分成左右兩部分；
2.遞歸求解：對左右兩部分分別進行歸并排序；
3.合并問題：把左右兩段排好序的序列合并出最終的有序序列。
經典問題2—歸并排序
舉例：N=8,8個數分別為6,1,5,3,2,4,8,7。過程如下：
6
5
1
3
4
2
7
8
6
5
1
3
4
2
7
8
6
1
5
3
4
2
7
8
6
1
5
3
2
4
8
7
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
劃分
合并
合并
合并
合并
合并
合并
合并
1
3
2
4
6
5
8
7
1
5
3
6
4
2
8
7
1
6
3
5
4
2
8
7
經典問題2—歸并排序
第3步如何把兩段排好序的序列合并成一個有序序列？
考慮第一段中兩個數A[i],A[j]，如果i策略：比較兩個序列最小的數, 誰小誰在前; 重復比較直到沒有數為止。時間復雜度為O(n)。
1
3
5
6
2
4
7
8
1
2
3
4
5
6
7
8
經典問題2—歸并排序—代碼
void merge(l,m,r)// 合并操作
{
// i 代表左半序列目前最小的位置
// j 代表右半序列目前最小的位置
// a：原數組b 數組：暫存數組（合并過程不能覆蓋原數組）
int i = l, j = m+1, k = l;
for(; i<=m && j<=r; )
if(a[i] <= a[j]) b[k++] = a[i++]; // 加入左邊最小的
else b[k++] = a[j++]; // 加入右邊最小的
// 加入剩余的數
for(; i<=m; b[k++] = a[i++]); // 加入剩余左半的數
for(; j<=r; b[k++] = a[j++]); // 加入剩余右半的數
for(i=l; i<=r; i++) a[i] = b[i]; // 從暫存數組中賦值
}
經典問題2—歸并排序—代碼
void merge_sort(int l, int r) // 排序位置從l 到r 的序列
{
if(l==r) return; // 長度為1 則不需要排序
int m = (l+r) / 2; // 分成兩段
merge_sort(l, m); // 排序左半段
merge_sort(m+1, r); // 排序右半段
merge(l,m,r);//把兩段排好序的序列合并成一個有序序列
}
經典問題2—歸并排序—時間復雜度分析一
F(n)表示對n個數進行歸并排序的時間復雜度
根據歸并排序思想有：
F(n)=2*F(n/2)+n
設n’=2^k,k=lgn’,則有：
F(n’)=2*F(n’/2)+n’=2*(2*F(n’/4)+n’/2)+n’=4*F(n’/4)+2*n’
=4*(2*F(n’/8)+n’/4)+2*n’=8*F(n’/8)+3*n’
=……=2^k*F(1)+k*n’=2^k+k*2^k=n’+n’*lgn’
設n’<=n<2*n’，則有F(n’)<=F(n)n’+n’lgn’<=F(n)<=2*n’+2*n’*lg(2*n’)
n’+n’lgn’<=F(n)<=2*n’+2*n’*lg2+2*n’*lgn’
所以F(n)=O(nlgn)。
經典問題2—歸并排序—時間復雜度分析二
畫出歸并排序的遞歸樹。
時間主要花費在合并上，每一層合并代價綜合為n,樹的深度為lgn，所以時間復雜度為O(nlgn)。
n
n/2
n/2
n/4
n/4
n/4
n/4
1
1
1
1
1
1
1
1
n
n
n
n
lgn
經典問題3—逆序對統計
給定一個長度為N 的序列，定義它的逆序對數為；
二元組(i,j)，滿足iA[j]。要求統計逆序對數。
例如：對于A=[3 2 5 1 4]，逆序對數為5：3>2, 3>1, 2>1,5>1, 5>4。
經典問題3—逆序對統計
下面介紹一種使用歸并排序計算逆序對的方法(利用分治算法的思想) 。
長度為N 的序列的逆序對數ans 可以分為3部分:
① 左半段的逆序對數L_ans
②右半段的逆序對數R_ans
③(i,j)分立兩側的逆序對數C_ans
* 結論：ans = L_ans + R_ans + C_ans
例如：對于A=[3 2 5 1 4]，分成兩段A1 = [3 2 5], A2 = [1 4]
L_ans= 1(3>2), R_ans = 0, C_ans = 4(3>1, 2>1, 5>1, 5>4)
ai
aj
ai
aj
ai
aj
經典問題3—逆序對統計
ans = L_ans + R_ans + C_ans
其中L_ans，R_ans是與計算ans相同類型的子問題，遞歸計算即可。主要考慮(i,j)分立兩側的逆序對數C_ans:
結論：對兩半段的數分別排序， (i 在左半段，j 在右半段，排在不同位置不影響先后關系) ，C_ans 不變
例如：對于A=[3 2 5 1 4]，分成兩段A1 = [3 2 5], A2 = [1 4]，對A1 和A2 進行排序，A’ = [2 3 5 1 4], C_ans 仍然為4(3>1,2>1, 5>1, 5>4)
經典問題3—逆序對統計
考慮(i,j)分立兩側的逆序對數C_ans:
考慮在合并過程中，統計它們的分立兩側逆序對總數：
左部分區間為[L,m],右部分[m+1,r]，在合并過程中，左右指針分別為i,j，當出現A[i]>A[j]時,(i,j)是一個逆序對，且A[L..m]是升序,所以(i+1,j),(i+2,j)…(m,j)也都是逆序對，答案ans可以直接增加m-i+1。
經典問題3—逆序對統計
如N=8，序列為[6,1,5,3,2,4,8,7],分成[6,1,5,3],[2,4,8,7]左右兩段, 遞歸計算出L_ans=4，R_ans=1,兩部分排好序分別為[1,3,5,6],[2,4,7,8],C_ans的計算如下：
1
3
5
6
2
4
7
8
1
2
3
4
5
6
7
8
C_ans=
0
+3=3
+2=5
經典問題3—逆序對統計—代碼
可以直接套用歸并排序的模板，在合并過程順便統計逆序對數。對于合并程序稍作改變。
void merge(l,m,r)// 合并操作,同時統計逆序對
{
int i = l, j = m+1, k = l;
for(; i<=m && j<=r; )
if(a[i] <= a[j]) b[k++] = a[i++]; // 加入左邊最小的
else ans += m-i+1,b[k++] = a[j++];
// 插入右半段的時候，逆序對數增加
for(; i<=m; b[k++] = a[i++]); // 加入剩余左半的數
for(; j<=r; b[k++] = a[j++]); // 加入剩余右半的數
for(i=l; i<=r; i++) a[i] = b[i]; // 從暫存數組中賦值
}
經典問題4—最近點對問題
給定平面上n(n>=2)個點,計算最近點對的距離。距離指歐幾里得距離。即點p1(x1,y1)和p2(x2,y2)之間的距離為。可能有點重合，在這種情況下，它們之間的距離為0。這一問題可以應用于交通控制等系統中，在空中或海洋交通控制系統中，需要發現兩個距離最近的交通工具，以便檢測出可能發生的相撞事故。
經典問題4—最近點對問題
方法一：暴力枚舉
共C(n,2)=n*(n-1)/2個點對，時間復雜度為O(n^2)。
經典問題4—最近點對問題
方法二：考慮用分治
ans表示n個點的最近點對距離,先判重,如有點重合ans=0。
否則把n個點盡可能均分為左右兩部分，ans的值只有以下3種情況：
1.左邊部分的最近點對距離d1
2.右邊部分的最近點對距離d2
3.左半部分的點與右半部分點形成的最小距離d3
ans=min(min(d1,d2),d3)
左右兩部分的最近點對問題是與原問題結構性質一樣的子問題，可以遞歸求解出d1,d2
第3部分d3的求解是問題的關鍵。
經典問題4—最近點對問題
分治法的時間復雜度T(n)=2*T(n/2)+D(n)，其中D(n)表示計算d3的時間復雜度。
如果d3的計算采用普通枚舉法,兩兩枚舉左右兩部分的點對,則D(n)=n*n/4
設n=2^k
T(n)=2*T(n/2)+n*n/4
=2*(2*T(n/4)+n*n/16)+n*n/4
=4*T(n/4)+n*n/8+n*n/4
=8*T(n/8)+n*n/16+n*n/8+n*n/4
=…=2^k*T(1)+n^2/4+n^2/8+…+n^2/(2^(k+1))
=(n^2+n)/2=O(n^2)
并沒有比暴力枚舉快多少。
經典問題4—最近點對問題
如果D(n)=c*n，則T(n)=2*T(n/2)+c*n=O(nlgn)
D(n)=c*n,說明計算d1,d2,d3時不能采用排序。做法如下：
1.前期準備：一開始，把輸入的n個點復制到A和B數組中，對A數組按x坐標單調遞增的順序排序，對B數組按y坐標單調遞增的順序排序，并建立映射Index[],Index[i]表示B數組第i個點在A數組的第Index[i]位置,即B[i]與A[Index[i]]是同一個點。接下來進行判重，如有點重合，則返回答案為0。否則進入第二步開始遞歸
2.算法的每一次遞歸調用的輸入都是點集對應的數組A和B,如果點數n<=3,則直接暴力枚舉。如n>3則：
經典問題4—最近點對問題
①劃分問題:直接用數組A的中間位置m作為分界點，A數組中m左側(含m)的點為左半部分的點，m右側的點為右半部分的點，數組A很容易就被劃分為AL和AR ，從左到右掃描B中的點,判斷Index[i]與m的大小關系,如Index[i]<=m,則該點屬于BL否則屬于BR,同時更新BL和BR對應的Index[]。時間復雜度為O(n)
②遞歸解決：遞歸求解出左右兩部分的最近點對距離d1,d2,取較小值d=min(d1,d2)
經典問題4—最近點對問題
③合并問題：答案ans=min(d,d3),d3表示左半部分的點到右半部分點的最短距離，如果存在點對使得d3為了找出這樣的點對(如果存在的話)，算法需要做如下工作：
經典問題4—最近點對問題
1)建立數組B’,它是把數組B中所有不在寬度為2d的垂直帶形區域內的點去掉后得到的數組,所以B’也是按y坐標順序排序的。
2)從左到右掃描B’中的每一個點p，嘗試找出后面與p距離小于d的點。下面將會看到，僅需考慮緊隨p后面的6個點,并記錄下B’中所有點對的最小距離d3。
3)如果d3這樣一來，合并問題的時間復雜度為O(n),總時間復雜度可以做到O(nlgn)。
經典問題4—最近點對問題
正確性
枚舉寬度為2d的帶形區域中的一點p，考慮其后面的點p’
如果dis(p,p’)d
d
d
p
經典問題4—最近點對問題
正確性
觀察屬于左半部分的d*d的正方形區域，如該區域內的點全部屬于左半部分，通過橫向縱向兩條直線把d*d的正方形區域均分為4個d/2*2/2的小正方形，因為每個小正方形最遠的兩個點的距離為對角線即sqrt(2)*d/2同理屬于右半區域的最多也只有4個點，所以整個2d*d區域內最多只有8個點。
經典問題4—最近點對問題
正確性
再仔細分析，如果有8個點，則一定有兩對點是重合的，而算法一開始就已經排除了重復。
那是不是就一共只有6個點，只需判斷后面的5個點呢？
下面如圖所示是7個點的情況，所以最多是7個點，只需判斷后面的6個點。
經典問題4—最近點對問題
算法導論中不嚴謹之處？
算法導論指出：只需考慮p后面的7個點，因為2d*d區域因為重合點最多有8個點。
問題是：如果有重合點可能就不是2個點重合，可能是3個，4個甚至更多。
當然：算法導論的做法不影響結果，因為如果更多的點重合，在遞歸時就已經算出d=0，后面判斷7個點不影響結果，如果沒有點重合，只需判斷6個點，那么判斷7個點也不影響正確性。
即使你不清楚上面的性質，但一開始進行了判重，且在枚舉p’時增加了縱坐標相差不超過d的判斷，一樣可以在O(nlgn)，因為你無形之中用了上面的性質。
一維分治1：CF429D Tricky Function
給出一個長度為N的序列a。
定義
求最小的f(i,j)
N ≤ 100000
Time Limit: 2s
一維分治1：CF429D Tricky Function
設Sum[i]表示a[1]+a[2]+…+a[i]
那么g(i,j)=Sum[j]-Sum[i]
問題變成：求形如( i , Sum[i] )點對間的最小距離。
用最近點對的方法求解。
時間復雜度：O(NlgN)
一維分治2：螞蟻(Ants,NEERC2008,LA4043)
給出n(1<=n<=10000)個白點和n個黑點的坐標(不超過10000的整數)，要求用n條不相交的線段把它們連接起來，其中每條線段恰好連接一個白點和一個黑點，每個點恰好連接到一條線段。如圖所示。
輸入保證沒有兩個坐標相同的點，且任意三點不共線。
所有白點和黑點均按照輸入順序編號為1~n
一維分治2：螞蟻(Ants,NEERC2008,LA4043)
本題可以使用最佳完美匹配解決。這里介紹一種分治的方法。
首先，找出所有的點中縱坐標最小的點(如果縱坐標相同,就取橫坐標小的點)記作X。
那么，對于所有除了它之外的點I，向量 XI 的極角就在[0,π)的范圍內。
將這些點按照極角從小到大排個序。
假設點X為黑點，一定可以找到一個白點Y，連接X和Y把原來的點分成兩部分，這兩部分 的黑點和白點數相同，這樣就分解出兩個問題性質一樣的子問題，遞歸下去即可。
一維分治2：螞蟻(Ants,NEERC2008,LA4043)
把黑點看做1，白點看做-1
則剩下的2n-1個點按照極角排序后就是n-1個1和n個-1組成的序列a[]
可以證明：該序列中一定存在位置i，使得a[i]=-1且序列前綴和s[i]=-1。
證明：在坐標系中畫出p1到p2n-1這2n-1個點,點pi橫坐標表示位置i,縱坐標表示前綴和s[pi], 相鄰點縱坐標相差1或-1,用線段連接相鄰點,線段有“/”與“\”兩種,“/”表示序列當前位置是1,所以縱坐標增加1,“\”表示序列當前位置是-1，所以縱坐標減少1。因此一定存在某個點px與px+1的連線如圖，假如不存在，則所有的點pi就都在x軸上或x軸以上，不可能到達點p2n-1。得證。位置x+1的點px+1就是要尋找的白點，因為a[x+1]=-1,且s[x+1]=-1。
連接X與px+1 ,因為s[x]=0,點集{p1,p2,…,px }和{px+2,px+3,…,p2n-1}都滿足黑色點數等于白色點數,可以接下去遞歸處理。
1
1
-1
2n-1
p1
P2n-1
Px
Px+1
一維分治2：螞蟻(Ants,NEERC2008,LA4043)
另一個分治方法。
直接把點集分成兩個不相交子集，兩個子集都滿足黑色點數等于白色點數
一樣，找出所有的點中縱坐標最小的點(如果縱坐標相同,就取橫坐標小的點)記作X。 那么，對于所有除了它之外的點I，向量 XI 的極角就在[0,π)的范圍內。將這些點按照極角從小到大排個序。
假設X是黑點，排序后如果第1個點是白點，則直接連接，再遞歸處理剩下的2N-2個點；如果第1個點是黑點，一樣把黑點看做1，白點看做-1，前綴和s[2n-1]=-1,s[1],相鄰前綴和相差1或-1，從 1(s[1])變成最后的-1(s[2n-1]),則一定存在位置i(1上面兩個分治法的時間復雜度都是O(n^2*lgn)。
一維分治3 ：UVA 1608 Non-boring sequences
如果一個序列的任意連續子序列至少有一個只出現一次的元素，則稱這個序列是不無聊(Non-boring)的。
給一個長度為N的序列A，現要判斷它是否是不無聊的。
1<=N ≤ 200000，0<=元素<=10^9
一維分治3 ：UVA 1608 Non-boring sequences
采用分治的方法。
如果原數組不存在只出現一次的數，則序列是“無聊”的。
否則假設原數組中僅出現一次的數的位置為p,則我們容易知道包含p的所有區間均是“不無聊”的。我們只需要判斷[1,p-1]和[p+1,n]其相應的子區間即可。
在判斷某一個區間內某一個數是否出現一次的時候，我們只需要判斷和他相同且距離其最近的左邊和右邊的數是否在此區間內即可，我們可以在O(n)內預處理出L[i]和R[i]。
這樣的時間復雜度為O(n^2)。
優化：在區間內尋找該元素的時候從兩端向中間尋找，這樣的時間復雜度極限為T(n)=2*T(n/2)+O(n)，即O(nlgn)。
一維分治3 ：UVA 1608 Non-boring sequences
證明如下：
算法時間主要消耗在枚舉區間內出現一次的位置p上，從兩邊枚舉，每個區間枚舉次數為分割成的較小那塊長度的兩倍。
T(n)=max{T(k)+T(n-k)+2*min(k,n-k)}
把上圖中紅色塊的長度累加起來就是總枚舉次數。
觀察每個紅色塊，其大小一定小于等于其父親塊大小的1/2。
上圖遞歸樹中的塊，只要長度>1就要繼續遞歸下去，遞歸樹中葉子節點都是長度為1的塊，考慮每個位置i對總枚舉次數產生的影響，即有多少個紅色塊包含位置i，從下往上考慮，由于Size(父親塊)>=2*Size(兒子塊)，所以包含位置i的紅色塊的數量為O(lgn)，所以總時間復雜度為 O(nlgn)。
一維分治4 ：CF549F Yura and Developers
給出一個長度為n的序列a和一個整數k。詢問有多少個長度大于1的區間滿足：在去掉最大值后剩下的數之和能被K整除。
1 ≤ n ≤ 300 000, 1 ≤ k ≤ 1 000 000, 1 ≤ ai ≤ 10^9
一維分治4 ：CF549F Yura and Developers
記當前分治區間[L,R]的最大值是am。顯然，這個區間的答案就是區間[L,m-1]和區間[m+1,R]以及跨過m的答案之和。
設前綴和數組S[i]，那么一個合法的區間[i,j]滿足：
所以只要維護左邊的Si-1+am就可以了。
一維分治4 ：CF549F Yura and Developers
遞歸樹示意如下：
每一層時間復雜度為O(n),深度最壞情況下是O(n),所以時間復雜度最壞情況下為 O(n^2)。
一維分治4 ：CF549F Yura and Developers
可以換個思路。剛才是從區間入手，現在從最大值入手。
枚舉每個最大值，然后確定出以它為最大值的區間，能向左和向右擴展到哪里，這個可以打兩個單調隊列解決。剩下就是統計答案了。
首先設s[i]為前綴和，假設最大值為a[m]，區間能向左(右)擴展到l[m],r[m]。如果一個以a[m]為最大值的區間[i,j](l[m]≤i≤m,m≤j≤r[m]）能夠滿足條件，當且僅當滿足：(s[j]-s[i-1]-a[m])%k=0
統計答案：枚舉每個a[m],再枚舉以a[m]為最大值的區間的左(或右)邊界i，然后就是插入一個形如(l,r,x)的詢問，詢問有多少個s[j](j∈[l,r]且s[j]=x)。假設有q個詢問，解決的時間復雜度為O(q*cost+n)。cost表示每次詢問的代價。
一維分治4 ：CF549F Yura and Developers
對于詢問個數q
如果對于一個m，以a[m]為最大值可以擴展到l[m],r[m]，那么相當于把區間[l[m],r[m]]切成兩部分，然后如果左半部分比右半部分小，就枚舉左邊界，否則枚舉右邊界，那么q是nlogn的。
配合下圖,與例1.7 UVA 1608 Non-boring sequences是一樣的原理。
一維分治4 ：CF549F Yura and Developers
對于詢問代價cost
詢問有多少個s[j](j∈[l,r]且s[j]=x)，直接枚舉太慢不可取。
可以把原數組a[i]%k后的值進行排序，并記錄每個數的左右界。這樣每個詢問就可以用二分在O(lgn)內完成。
總時間復雜度為O(n*lgn*lgn) 。用可持久化線段樹同樣可以做到。
更好的方法：
對于詢問(l,r,x)來說，詢問的答案為f[r][x]-f[l-1][x],f[r][x]表示s[1],s[2]到s[r]中等于x的個數，維護f很低效。
可以這樣做：處理所有詢問,每個詢問(l,r,x)插入2條記錄,一條插入記錄(x,-1)到結點l-1的詢問鏈表中,再插入(x,1)到結點r的詢問鏈表中。
記錄 cnt[x]表示前綴和為x的出現次數,從小到大枚舉位置i,更新cnt[s[i]]++,掃描結點i的詢問鏈表,對于其中的每一個記錄(value,sign)更新答案ans+=cnt[value]*sign
均攤下來cost為O(e)。總時間復雜度為O(nlgn)。
一維分治4 ：CF549F Yura and Developers
舉例：N=4,序列為{4,3,2,5},K=3
枚舉a[1],以a[1]為最大值的區間為[1,3],左部分小,枚舉左邊界L=1,右邊界的區間是[2,3],增加一個詢問(2,3,1),向結點1插入記錄(1,-1),向結點3插入記錄(1,1)
枚舉a[2],以a[2]為最大值的區間為[2,3],左部分小,枚舉左邊界L=2,右邊界的區間只能取[3,3],增加一個詢問(3,3,1),向結點2插入記錄(1,-1),向結點3插入記錄(1,1)
枚舉a[3],以a[3]為最大值的區間為[3,3],不需要考慮
枚舉a[4],以a[4]為最大值的區間為[1,4],右部分小，枚舉右邊界R=4,左邊界區間為[1,3],增加詢問(0,2,0)，向結點-1插入記錄(0,-1),向結點2插入記錄(0,1)
i -1 0 1 2 3 4
A[i] 0 0 4 3 2 5
L[i] 0 0 1 2 3 1
R[i] 0 0 3 3 3 4
A[i]%K 0 0 1 0 2 2
S[i]%K 0 0 1 1 0 2
-1
0
1
2
3
4
(1,-1)
(1,1)
(1,1)
(1,-1)
(0,-1)
(0,1)
一維分治4 ：CF549F Yura and Developers
舉例：N=4,序列為{4,3,2,5},K=3
一開始cnt[0]=cnt[1]=cnt[2]=0,ans=0
i=-1,cnt[]={1,0,0},枚舉結點-1的詢問鏈表,更新ans=-1
i=0,cnt[]={2,0,0},結點0后沒有詢問鏈表,ans保持不變
i=1,cnt[]={2,1,0},枚舉結點1的詢問鏈表,ans=ans+cnt[1]*-1=-2
i=2,cnt[]={2,2,0},枚舉結點2的詢問鏈表,ans=ans+cnt[1]*-1+cnt[0]*1=-2
i=3,cnt[]={3,2,0},枚舉結點3的詢問鏈表,ans=ans+cnt[1]*1+cnt[1]*1=2
i=4,cnt[]={3,2,1},結點4后沒有詢問鏈表,ans保持不變
Ans=2,對應的兩個區間是[4,3]和[4,3,2,5]。
i -1 0 1 2 3 4
A[i] 0 0 4 3 2 5
L[i] 0 0 1 2 3 1
R[i] 0 0 3 3 3 4
A[i]%K 0 0 1 0 2 2
S[i]%K 0 0 1 1 0 2
-1
0
1
2
3
4
(1,-1)
(1,1)
(1,1)
(1,-1)
(0,-1)
(0,1)
一維分治5：計蒜之道 百度地圖的實時路況
給一個有N(4<=N<=300)個點的無向圖。定義d(x,y,z)為從x號點出發，嚴格不經過y號點，最終到達z號點的最短路徑長度。如果這樣的路徑不存在，d(x,y,z)的值為-1.
求
一維分治5：計蒜之道 百度地圖的實時路況
這題類似Floyd，但是是求不經過某個點的時候，所有點之間兩兩的最短路。
可以枚舉不經過的點然后Floyd，時間復雜度為O(n^4)。
但是考慮到每個不經過的點的時候，其實有很多的兩點之間的距離并不會改變，有重復計算。
分治：對于一個分治區間[l,r]，我們會處理出一個最短路矩陣，表示不以[l,r]區間的點作為中轉點的最短路。那么從[l,r]遞歸到[l,mid]只需要枚舉[mid+1,r]的點作為k(中轉點)在原矩陣的基礎上跑Floyd，就能計算出[l,mid]對應的矩陣，[mid+1,r]也是同理在[l,r]最短路矩陣的基礎上把[l,mid]中的點添加到允許經過的點中就可以計算出[mid+1,r]對應的矩陣。
最后分治區間長度為1的時候，就是不以對應點為中轉點的最短路矩陣了。時間復雜度是O(n^3*lg n)。
二維分治1：CF480E Parking Lot
給出一個n×m(n,m<=2000)的網格圖，有的位置上有障礙物。給出k(k<=2000)個操作，每次將一個格子變為障礙物，再詢問沒有障礙物的最大子正方形。
Time Limit: 3s
二維分治1：CF480E Parking Lot
定義f[i][j]表示以第i行第j列為右下角的最大子正方形的邊長。
對于每次操作，利用動態規劃f[i][j]=min{f[i-1][j-1],f[i-1][j],f[i][j-1]}+1
時間復雜度為O(nmk)，超時。
可以用分治
定義f[L][R]表示原網格圖第L行到第R行k次操作后的最大子正方形大小。
將矩陣盡可能分成上下相等的兩部分。設中間一行為mid。
那么f[L][R]就是以下3部分的最大值。
①f[L,mid]
②f [mid+1,R]
③穿過mid這一行的最大子正方形
前兩個可以分治遞歸求解。
二維分治1：CF480E Parking Lot
對于跨過中間mid一行的正方形：
每個格點維護up[i][j]和down[i][j]，up[i][j]表示從位置(i,j)開始向上有多少個連續的無障礙的位置,down[i][j]表示從位置(i,j)開始向下有多少個連續的無障礙的位置，初始的up和down可以用遞推在O(nm)內完成。
按順序處理每個操作，對于每個在當前分治范圍內的操作(x,y)，只會影響第y列的up和down的值，在O(n)內更新這些值。
跨過中線的最大正方形，一定包含第mid行，考慮該正方形左邊界為列號i,右邊界為列號j。
先枚舉左邊界i,再枚舉右邊界j,則包含第x行第i列到第j列的矩形的寬度w=j-i+1,高度h=min_up+min_down-1,該情況下的最大子正方形的邊長為min(w,h),其中min_up=min{up[mid][i],up[mid][i+1],…,up[mid][j]},min_down{down[mid][i],down[mid][i+1],…,down[mid][j]}
第mid行
第i列
第j列
min_up
min_down
二維分治1：CF480E Parking Lot
min_up和min_down的計算可以通過維護兩個單調遞增的隊列來實現，因為是計算區間最小值，當后面出現更小的值時可以刪除前面比該值大的元素， min_up和min_down的值分別在隊列的第1個位置。
容易知道,寬度w在遞增,高度h非遞增，所以當h左邊界i向右枚舉過程中，最大的合法右邊界j也是非遞減的。
每次遞歸返回的是k次操作后的子正方形大小，可能只有其中一部分操作在當前遞歸區間內，對于不在區間的操作直接賦為最靠近的前面一個操作后的答案，比如第x操作后的答案為value，下一次操作是y,則第x+1,x+2,…,y-1操作后的答案直接賦為value即可。
所以對于每次操作,計算跨過中間mid一行的正方形的大小可以在O(m)內完成,分治過程中對于每個操作最多有lgn的分治區間包含它。所以總時間復雜度為O((m+n)*k*lgn)。
min_up
min_down
二維分治1：CF480E Parking Lot
更好的方法：
離線處理，先把最后的答案用動態規劃在O(n*m)完成。
從后往前做，每次相當于把一個障礙物變成非障礙物，答案肯定非遞減。
對于操作(x,y)，在O(n)內更新第y列的up和down的值。
如果答案增大，一定跟第x行有關系，所以我們就處理包含第x行的答案，處理方法跟前面計算跨過中線的答案一樣，處理每個操作的時間復雜度為O(m)。
總時間復雜度是O(n*m+m*k)。
二維分治2：CF364E Empty Rectangle
給出一個n*m(1<=n,m ≤ 2500)的01網格,求有多少矩形中恰好包含k(0<=k<=6)個1。
Time Limit: 12s
二維分治2：CF364E Empty Rectangle
方法一：
初始化s[i][j]表示以(1,1)為左上角(i,j)為右下角的矩形中的元素之和
遞推O(nm)內解決：s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]
枚舉左上角(x1,y1)和右下角(x2,y2)判斷s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]是否等于k。
時間復雜度為(n^2*m^2)。超時。
方法二：
枚舉左邊界L，右邊界R，下邊界B，上邊界是可以用二分計算出來。
時間復雜度為O(n*m^2*lgn)。
二維分治2：CF364E Empty Rectangle
方法三：分治法
像例1.10那樣定義f[L][R]表示原矩陣第L行到第R行1的個數等于k的子矩陣的數量。
將矩陣盡可能均分成兩部分。設中間一行為mid。
那么f[L][R]就是以下3部分的最大值。
①f[L,mid]
②f [mid+1,R]
③穿過mid這一行格點滿足要求的子矩陣的數量，注意該矩陣必須包含第mid行和第mid+1行。
前兩個可以分治遞歸求解。
二維分治2：CF364E Empty Rectangle
計算穿過第mid這一行的數量，可以枚舉左邊界i，再枚舉右邊界j
定義up[x]表示以i為左邊界、j為右邊界、mid為下邊界的1的個數不超過x的最大矩形的上邊界，則1的個數等于x的紅色矩形有up[x-1] -up[x]個。同理定義down[x]表示以i為左邊界、j為右邊界、mid+1為上邊界的1的個數不超過x的最大矩形的下邊界，則1的個數等于x的綠色矩形有down[x]-down[x-1]個。
隨著j的右移,up[x]是單調增的,down[x]是單調減的
統計答案：枚舉x,ans+=(up[x-1]-up[x])*(down[k-x]-down[k-x-1]),具體實現要注意其他細節。
合并這一步操作時間復雜度為O(m*m*k)
T(n)=2*T(n/2)+m*m*k
T(n)=O(n*m*m*k)(注意與上題的區別！！)
mid
i
j
二維分治2：CF364E Empty Rectangle
T(n)=2*T(n/2)+m*m*k
=2*(2*T(n/4)+m*m*k)+m*m*k
=4*T(n/4)+2*m*m*k+m*m*k
=…
≈2*n*m*m*k=O(n*m*m*k)
n
n/2
n/2
n/4
n/4
n/4
n/4
1
1
1
1
1
1
1
1
m*m*k
2*m*m*k
4*m*m*k
n*m*m*k
lgn
二維分治2：CF364E Empty Rectangle
采用二維分治,橫向劃分和縱向劃分相結合
遞歸樹示意圖如下：
總時間復雜度為O(k*(m*m*logn+n*n*logm))
也可以每次分成4塊分治下去，時間復雜度一樣。
m*m*k
m*m*k
n*n*k/2
n*n*k/2
點分治1：Poj1741 樹中點對統計
給定一棵N(1<=N<=10000)個結點的帶權樹，定義為dis(u,v)為u,v兩點間的最短路徑長度，路徑的長度定義為路徑上所有邊的權和。 再給定一個K(1<=K<=10^9)，如果對于不同的兩個結點a,b，滿 足dis(a,b)<=K，則稱(a,b)為合法點對。求合法點對個數。
點分治1：Poj1741 樹中點對統計
方法一：
以每一個點為起點出發做DFS，統計出任意點對的最短路徑長度，時間復雜度高達O(N^2)
方法二：
一條路徑要么過根結點，要么在根結點的某一個子樹中，可以用分治算法。
路徑在子樹中的情況遞歸處理即可，下面分析經過根結點的情況。
點分治1：Poj1741 樹中點對統計
定義Depth(i)表示點i到根結點的路徑長度，Belong(i)=X ( X 為根結點的某個兒子，且結點i在以X為根的子樹內)。那么我們要統計的就是：
滿足Depth(i)+Depth(j)<=K且Belong(i)≠Belong(j)的(i,j)個數
=滿足Depth(i)+Depth(j)<=K的(i, j)個數–
滿足Depth(i)+Depth(j)<=K且Belong(i)=Belong(j)的(i, j)個數
這兩個部分都是要求滿足Ai+Aj<=k的(i,j)的對數。可以將A排序后利用單調性我們很容易得出一個O(N)的算法，所以我們可以用O(NlogN)的時間來解決這個問題。
綜上，此題使用分治算法的時間復雜度為 O(N*logN*遞歸深度) 。
點分治1：Poj1741 樹中點對統計
遞歸深度取決于選擇的根結點。
最佳選擇是選一個點作為根結點，使得其結點最多的子樹的結點數最小，也被稱為“樹的重心”，可以用樹形DP在O(N)內求出。
定理：樹的重心分出的子樹的結點個數均不大于N/2。
證明：假設U是樹的重心，它與V1,V2,…,Vk相鄰，記Size(X)表示 以X為根的子樹的結點個數。記V為V1,V2,…,Vk中Size值最大的點。 采取反證法，假設Size(V)>N/2，那么我們考慮如果選取V作為根結點的情況，記Size’(X)表示此時以X為根的子樹的結點個數。 如下圖，對于A部分，顯然Size’(Ti)點分治1：Poj1741 樹中點對統計
每次遞歸選擇子樹的重心做為樹根，max_i表示第i層的子樹結點最多的結點數，有max_1<=N,max_2<=N/2,max_i<=N/(2^(i-1))，遞歸深度為O(logN)。
總時間復雜度為O(N*logN*logN)。
max_1<=N
max_2<=N/2
max_3<=N/4
O(logN)
點分治1：Poj1741 樹中點對統計—代碼
void solve(int u) //計算以u為根的子樹中dis(a,b)<=K的點對數。
{
int G = calcG(u);//尋找樹的重心G
vis[G] = true;
ans += calc(G, 0);//統計滿足Depth(i)+Depth(j)<=K的(i, j)個數
for (int e = adj[G]; e; e = nxt[e])
if (!vis[go[e]]) ans -= calc(go[e], len[e]);
//統計滿足Depth(i)+Depth(j)<=K且Belong(i)=Belong(j)的(i, j)個數
for (int e = adj[G]; e; e = nxt[e])
if (!vis[go[e]]) solve(go[e]);//遞歸處理G的子樹
}
點分治1：Poj1741 樹中點對統計—代碼
long long calc(int sv, int L){ //計算以sv為根的子樹中到根sv的距離<=K-L的結點數。
static int qn, que[N], d[N];
int u, v, e, d_n = 0;
que[qn = 1] = sv, dis[sv] = L, fa[sv] = 0;
for (int ql = 1; ql <= qn; ++ql) {
d[d_n++] = dis[u = que[ql]];
for (e = adj[u]; e; e = nxt[e]) {
if (vis[v = go[e]] || v == fa[u]) continue;fa[v] = u, dis[v] = dis[u] + len[e], que[++qn] = v;
}
}//寬搜
long long cnt = 0;
std::sort(d, d + d_n);
int l = 0, r = d_n - 1;
while (l < r) { if (d[l] + d[r] <= K) cnt += r - l++; else –r; }//使用雙指針利用單調性統計答案。
return cnt;
}
點分治1：Poj1741 樹中點對統計
也可以把前面已經完成的子樹中的距離加入到平衡樹，下一個子樹中每計算出一個距離就到平衡樹中統計答案，一個子樹中全部處理完再加入到平衡樹中。
常數更小的寫法：
增加B[],B[x]記錄x在root的哪個子結點的子樹中，B[root]=root
計算經過根結點路徑點對：“滿足Depth(i)+Depth(j)<=K的(i, j)個數”–
“滿足Depth(i)+Depth(j)<=K且Belong(i)=Belong(j)的(i, j)個數”時，可以不用多次調用clac()。直接把樹中的點都取出來放進數組中，按照D[x]遞增排序。
還是用兩個指針 i, j ,i從左開始枚舉，表示路徑到root距離較小的端點，j從后向前開始掃描數組，可以計算出滿足D[x]+D[y]<=k的合法點對(x,y)的個數，其中x、y分別是i、j指向的節點編號。
計算方法如下：
設F[i]表示在左、右指針中間滿足B[x]=i的點x的個數，先初始化F[]，枚舉過程中i向右加1前先執行F[B[node[i]]]--，j減1前線執行F[B[node[j]]]-- 。
設當前左指針指向點x，則 j-i-F[B[x]] 就是要求的答案。
排序是O(NlogN)的，掃描是O(N)的。總時間復雜度還是O(N*logN*logN)，但常數減小。
點分治2： CF293E Close Vertices
給一棵N個頂點的樹，求有多少條路徑的邊數不超過L，且邊權和小于等于W。
1 ≤ N ≤ 105 1 ≤ L ≤ N 0 ≤ W ≤ 109
Time Limit: 3s
點分治2： CF293E Close Vertices
用樹分治，比上題多邊數限制。做法與上一題類似：
把路徑分成兩類：
①在根的子結點為根的子樹中，遞歸處理即可；
②路徑經過根結點
②的處理方法跟上題代碼中一樣，等于calc(root,0)-∑calc(son_i,edge(root,son_i))
計算calc()時,一樣按照到根結點root的距離從小到大排序，從右往左一個端點i，另外一個端點j從小到大遞增，j每次向右移，就把新加入的結點node[j]對應的num[node[j]](到根結點的邊數)添加到樹狀數組中，再統計數狀數組中<=W-num[node[i]]的個數即可。
總時間復雜度是O(N*logN*logN)。
點分治3：WC2010重建計劃
給出一棵N個節點帶權樹。
求邊數在[L,R]之間的所有路徑中，最大的權值平均值。
N ≤ 100000
點分治3：WC2010重建計劃
二分答案mid，將圖中所有邊減mid，問題轉換為判斷是否存在邊數為x的路徑，路徑邊權和>=0，L<=x<=R。
對于遞歸執行的每棵樹，先找出重心，從重心剖開樹以后，得到若干棵子樹
順序處理每棵子樹，對于一棵子樹，Bfs得其所有路徑邊數及邊權和(起點從重心出發，終點在該子樹內)，由于是Bfs，所以路徑長度是從小到大
并維護mx[i]表示起點從重心出發，終點在子樹內，長度為i的路徑邊權和最值，當前正在處理的子樹中的信息先不添加到mx[]中，處理完再把這些信息更新到mx[]中
Bfs處理子樹中路徑i，路徑i的長度為x，則需要維護mx中長度在區間[L-x,R-x]內的最大值，該區間是向左平移的，可以維護單調遞減隊列。
時間復雜度為O(N*logN*logN)。

展開更多......

收起↑