---
tags: 基礎算法
title: 分治法2 (divide & conquer No.2)
---

# 分治法2 (divide & conquer No.2)

:::info
- 預備知識：基礎DP
:::

## 再談逆序數對
- *如果沒聽過逆序數對，請看[這篇筆記](https://hackmd.io/Uw2u5wLDSQOo3D2kgdQLLg)*
:::info
題目：
- 給定序列$A_1, A_2, A_3, ..., A_n$，求出有幾個數組$(i,j,k)$滿足
- $1 <= i < j < k <= n$ 且 $A_i > A_j > A_k$
constraints:
- $n <= 10^5$
:::
:::success
如果你已經會做兩個數字的逆序數對，這題應該不難。

對於原本的逆序數對，我們合併時使用兩個指針求出

這邊只講MERGE的部份～
一樣令左半序列$L$, 右半序列$R$
- 先對於$L$的每個元素求出在自己左邊且比自己大的數有幾個（求二個數字的逆序數對，$O(|L|log|L|)$）
- 再對於$R$的每個元素求出在自己右邊且比自己小的數有幾個（求二個數字的逆序數對，$O(|R|log|R|)$）

最後合併的方式其實就跟二維的一樣了～
- $L$序列一個元素+$R$序列兩個元素
- $L$序列兩個元素+$R$序列一個元素

完成～
Time Complexity: $O(n×log^2n)$
:::

## 用分治法解一維DP問題？！
*如果能用分治法解DP問題，之後講到的「區間查詢問題」就不再是問題了～*
:::info
直接看例題ㄅ
題目：
- 給定序列$A_1, A_2, A_3, ..., A_n$，求整個區間的最大連續子區間和

Constraints:
- $n <= 2×10^6$
- $-10^9 <= A_i <= 10^9$
:::
:::success
用DP解的話大家都會ㄅ

這邊用分治解法～

一樣講MERGE的地方就好。
一樣令左半序列$L$, 右半序列$R$。
我們發現，整個區間的答案可能是$L$的答案，也可能是$R$的答案，還有可能是橫跨$L,R$的區間。
那我們不如維護區間的最大前綴合＆最大後綴合（？）
- 令$prefix\_max(L)$為$L$的最大前綴和，$R$也如此
- 令$suffix\_max(L)$為$L$的最大後綴和，$R$也如此

我們發現這個區間的答案是
- $max\{L$的答案$,R$的答案$,suffix\_max(L)+prefix\_max(R)\}$

然後，我們如何維護prefix_max跟suffix_max呢？
- $prefix\_max(L,R) = max(prefix\_max(L),sum(L)+prefix\_max(R))$
- $suffix\_max(L,R) = max(suffix\_max(R),sum(R)+suffix\_max(L))$

這麼一來，合併複雜度$O(1)$
Time Complexity: $O(n)$
:::

再看一個經典題
:::info
- 給定序列$A_1, A_2, A_3, ..., A_n$，需要選取一些數字，使的選取數字之和最大。
- 任意兩個被選取的數字不得相鄰。

Constraints:
- $n <= 2×10^6$
- $0 <= A_i <= 10^9$
:::
:::success
解法也很簡單～

一樣令左半序列$L$, 右半序列$R$。
為了處理數字不相鄰的問題，這次我們多維護一些東西：
- 整個序列中選取合法數字的最大和
- 第一個數不選取的情況下，選取合法數字的最大和
- 最後一個元數不選取的情況下，選取合法數字的最大和
- 第一個數跟最後一個數都不選取的情況下，選取合法數字的最大和

維護這幾個資訊，我們也成功把合併複雜度壓到$O(1)$

至於怎麼維護，就給各位自己去想喔～

Time Complexity: $O(n)$
:::
最後給個Bonus
:::info
各位自己想想看喔～
- 使用分治法求LIS
- [之前的LIS筆記](https://hackmd.io/5np7TpYDRqiJHruJfuIDmA)
- 三圍偏序問題
- [ZJ c571]((https://zerojudge.tw/ShowProblem?problemid=c571))
:::