---
slideOptions:
theme: sky
---
## 真．資料結構EX
#### 成為十萬序列大師
###### wangyenjen
----
## WHOAMI
喵
----
#### JAW
- Johnchen902：字串、噁心模擬題、小品、DP、慘題
- nonamefour0210：數學、DP、吉祥物！
- 我：打雜、資結、dp優化、幾何
---
### 前備知識
- 線段樹和BIT
- 線段樹和BIT
- 線段樹和BIT
---
CONTENT
- 穿越時空的線段樹
- 切塊、Mo's、分case
- 擁抱分治，向資結說不
----
遺珠之憾...
- O(1) 求斐波那契數列
- 把PI、e存在月球上
---
### 小複習
----
## 線段樹
----
### 區間開根號
問題：
給你 $N$ 個數字 $a_i(1 \le i \le N)$，跟 $Q$ 個操作，操作有兩種：
1. ```query x y```: 查詢序列 $a$ 在區間 $[x, y]$ 的和。
2. ```sqrt x y```: 把 $a_x, a_{x + 1}, ..., a_y$ 的值個別開根號後取高斯。
----
### 區間開根號
問題：
給你 $N$ 個數字 $a_i(1 \le i \le N)$，跟 $Q$ 個操作，操作有兩種：
1. ```query x y```: 查詢序列 $a$ 在區間 $[x, y]$ 的和。
2. ```sqrt x y```: 把 $a_x, a_{x + 1}, ..., a_y$ 的值個別開根號後取高斯。
$1 \le N, Q \le 10^5$
$1 \le a_i \le 10^9$
---
## 穿越時空的線段樹
----
先來看看一個問題：
給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。
現在有 $Q$ 個操作，每個操作會是以下兩種中的一種：
1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。
2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。
每次操作完後請輸出當前的連通塊數量。
$1 \le N, Q \le 10^5$
$1 \le A_i, B_i \le N$
----
當發現一個問題太難的時候，我們往往可以從較簡單的版本著手，試著找出解決難題的方向。
----
把兩種操作分開來看看吧！
----
### easy version 1.
給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。
現在有 $Q$ 個操作，每個操作會是以下形式：
- 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。
每次操作完後請輸出當前的連通塊數量。
$1 \le N, Q \le 10^5$
$1 \le A_i, B_i \le N$
----
### 並查集(Disjoint Set)的標準應用
並查集可以...
1. 合併兩個連通塊
2. 詢問每個連通塊有多少點
3. 詢問當前有多少連通塊
etc...
----
### easy version 2.
給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。
現在有 $Q$ 個操作，每個操作會是以下形式：
- 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。
每次操作完後請輸出當前的連通塊數量。
$1 \le N, Q \le 10^5$
$1 \le A_i, B_i \le N$
----
似乎沒有現成的資料結構可以維護（？
----
當題目沒要求強制在線時，往往有簡單的離線做法！
----
## 時光倒流
----
把所有操作先存起來
對於最終的Graph，如果把操作到回去做？
----
變成只有加邊的問題了！
----
#### 回到原問題
給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。
現在有 $Q$ 個操作，每個操作會是以下兩種中的一種：
1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。
2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。
每次操作完後請輸出當前的連通塊數量。
$1 \le N, Q \le 10^5$
$1 \le A_i, B_i \le N$
----
#### 還是不會做
----
### 時間線段樹！
----
時間線段樹，顧名思義就是將線段樹的每個節點當成對應的時間區間，並存放著該時間區間對應的所有>
操作，即在這邊操作是有時效性的。
----
使用上會把詢問與具有時效性的操作一起當成時間點，將這些時間點所形成的區間視為線段樹上的節點。
----
```C++11=
void insert_event(vector<Event> tr[], int idx,
int lb, int rb, int ql, int qr, Event e) {
// tr[] := 時間線段樹存事件所使用的陣列
// idx := 當前在時間線段樹上哪個節點
// 當前節點對應到的時間區間為 [lb, rb]
// 當前要在時間區間 [ql, qr] 插入一個事件e
// 當前區間 [lb, rb] 完全被 事件區間 [ql, qr] 包含
if (ql <= lb && rb <= qr) {
// 插入事件至時間線段樹對應的節點
tr[idx].push_back(e);
return;
}
int m = (lb + rb) / 2;
// 事件區間 [ql, qr] 完全位於 mid 左邊
if (qr <= mid)
insert_event(tr, idx*2, lb, mid, ql, qr, e);
// 事件區間 [ql, qr] 完全位於 mid 右邊
else if (mid < ql)
insert_event(tr, idx *2+1, mid+1, rb, ql, qr, e);
// 事件區間 [ql, qr] 跨過 mid 這個時間點
else {
insert_event(tr, idx*2, lb, mid, ql, qr, e);
insert_event(tr, idx*2+1, mid+1, rb, ql, qr, e);
}
}
```
----
```C++11=
void traversal(vector<Event> tr[], int idx, int lb, int rb)
{
int cnt = 0; // 用來記錄在這一層做了多少事情
for (auto e : tr[idx])
if (do_things(e))
cnt++;
if (lb == rb) // 記錄在這個時間點的答案
else {
int mid = (lb + rb) / 2;
// 遍歷時間線段樹的左子樹
traversal(tr, idx * 2, lb, mid);
// 遍歷時間線段樹的右子樹
traversal(tr, idx * 2 + 1, mid + 1, rb);
}
while (cnt--)
undo(); // 將所做的事情進行undo操作
}
```
----
如果對於每條邊，我們考慮它存活的時間...
----
#### 時間線段樹的undo?
----
#### 並查集again
----
#### 支援undo操作的並查集
----
```C++11=
int cc_cnt; // 當前連通塊數量
int sz[MAX_N]; // 用來記錄每個連通塊大小
int par[MAX_N]; // 用來記錄每個節點所指向的父節點
stack<pair<int*, int> > stk_sz; // 用來記錄每次操作前的sz
stack<pair<int*, int> > stk_par; // 用來記錄每次操作前的par
```
----
```C++11
void init(int n) {
while (!stk_sz.empty())
stk_sz.pop();
while (!stk_par.empty())
stk_par.pop();
cc_cnt = n;
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
```
----
不能路徑壓縮！
```C++11=
int find(int x) { // 找根
while (x != par[x])
x = par[x];
return x;
}
```
----
不能路經壓縮，所以一定要啟發式合併！
```C++11=
bool merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y)
return 0;
if (sz[x] < sz[y]) // 啟發式合併
swap(x , y);
// 記錄操作前的sz
stk_sz.push(make_pair(&sz[x], sz[x]));
// 記錄操作前的par
stk_par.push(make_pair(&par[y], par[y]));
cc_cnt--;
sz[x] += sz[y];
par[y] = x;
return 1;
}
```
----
```C++11=
void undo() {
pair<int*, int> p_par = stk_par.back();
pair<int*, int> p_sz = stk_sz.back();
stk_par.pop();
stk_sz.pop();
*p_par.first = p_par.second; // 將par回復成操作前的par
*p_sz.first = p_sz.second; // 將sz回復成操作前的sz
cc_cnt++;
}
```
----
至此，對於可undo的並查集，每次merge操作的時間複雜度為$O(\log N)$，每次undo操作為$O(1)$
----
- 單次插入事件$O(\log (M + Q))$
- merge操作$O(\log N)$
- undo操作$O(1)$
- traversal $O((M + Q))$
總時間複雜度為$O((M + Q) \log N + (M + Q) \log (M + Q))$
----
#### 總結
總結一下，通常題目只要滿足以下兩個條件便可以考慮使用時間線段樹了：
- 操作具有時效性
- 搭配的資料結構支援undo操作（一般的資料結構幾乎都可以支援）
----
#### 小習題 - BZOJ 4025 二分圖
給定一張$n$個點的圖，有$m$條邊與$T$個時間點，每條邊只存在於$(st, ed]$這些時間點，求每個時間點時這張圖是否為二分圖。
- $1 \le n \le 10^5$
- $1 \le m \le 2 \times 10^5$
- $1 \le T \le 10^5$
- $0 \le st \le ed \le T$
---
## 切塊
----
#### 先來看個問題吧！
給你一個長度 $N$ 的序列 $A[0], A[1], ..., A[N - 1]$
緊接著 $Q$ 筆詢問，每筆詢問是一個數對 $x, y$
請你回答 $min${ $A[x], A[x + 1], ..., A[y]$ }
A = {5, 2, 8, 1, 7}
Query = {(0, 2), (1, 4), (2, 2)}
答案：2 1 8
----
```C++11=
int ans = A[x];
for (int i = x + 1; i <= y; i++)
ans = min(ans, A[i]);
```
時間複雜度 $O(QN)$
特性：$min(a, b, c) = min(a, min(b, c))$
可以對一部分數字先求最小值，再從每個部份的最小值中取最小的！
----
一部分？
每連續 $k$ 個分一組，先把每組的最小值算好並存下來
對於詢問
綠色每塊都先算好了，時間花費是塊數：最多 $\frac{N}{k}$
紅色部份每個數字跑一遍，時間花費是一塊大小：最多 $2k$
----
每次詢問 $O(\frac{N}{k} + k)$
取個好的 $k$？
算幾不等式：$\frac{N}{k} + k \le 2 \times sqrt(\frac{N}{k} * k) = 2 \times sqrt(N)$
在 $\frac{N}{k} = k$ 也就是 $k = sqrt(N)$ 時最小
所以取 $k$ 為 $sqrt(N)$ 就有了每次詢問 $O(sqrt(N))$ 的解法了
----
### 分塊的好處
1.大部分的區間詢問問題都需要用某種平衡二元搜尋樹來維護，若能用set,map,或是簡單的線段樹維護那還好，但如果性質很難維護或是要用到複雜的資料結構，寫起來會比較久也比較難debug。
2.分塊時跟陣列一樣只有一層，比較好想我們要維護什麼
3.code易懂
----
### IOI 2011 Elephants
有 $N$ 隻可愛的大象在舞台上排成一條線跳舞。
接下來有$M$次操作，每次操作可以把 左邊數來第$a$隻大象移動到數線上的位置$b$，每次操作完後請輸出最少需要幾張照片才可以拍到所有的大象。
（每張照片可以cover一個長度為$L$的區間）
$1 \le N,M \le 150000 , 0 \le b \le 10^9$
----
### 如果大象不會移動位置？
Greedy！
----
### 將大象序列切成$K$塊吧！
對於每一隻大象我們可以紀錄如果從他開始，我們要幾台相機才能蓋滿該塊的所有大象，且最後會蓋到哪個位置。
----
### 操作
對某一塊加一隻大象，對某一塊刪除一隻大象
----
### 如果某塊大象太多？
令一塊大小為$X$，如此修改時間為$O(X \log X)$，查詢時間便是$O(K \log X)$，
但悲劇的是每次操作後每一塊大小並不是固定的，
在經過$Q$次操作後，我們也許會獲得$X = \frac{N}{K} + Q \le N$
----
### 打掉重練！
當有一塊過大時（可以定為$\frac{2N}{K}$），我們便整個打掉重新分塊
----
我們令$K=\sqrt{N}$
建表時間為$O(N \log N)$，
每次修改與查詢的時間複雜度為$O(\sqrt{N} \log \sqrt{N})$
重建表總時間為$O\big(\frac{Q}{\sqrt{N}} \times N \log N\big) = O(Q \sqrt{N} \log N)$
---
### mo's
----
### 經典問題 - 區間眾數
給定一個序列$S_1 , \ldots , S_N$，接著有$Q$組詢問，
每次詢問$[L_i, R_i]$出現最多的數字出現幾次。
$(1 \le N,Q \le 10^5)$
----
$app[x] :=$ 數字$x$出現幾次
$cnt[y] :=$ 有$cnt[y]$個數字出現過$y$次
$cnt[0]$初始為$N$。
```C++11=
void add(int x) {
int now = ++app[x];
cnt[now - 1]--;
cnt[now]++;
curMax = max(curMax, now);
}
void sub(int x) {
int now = --app[x];
cnt[now + 1]--;
cnt[now]++;
if (!cnt[curMax])
curMax--;
}
```
----
```C++11=
for (int i = 1, curL = 1, curR = 0; i <= Q; i++) {
while (curR < qry[i].R) {
curR++;
add(S[curR]);
}
while (curR > qry[i].R) {
sub(S[curR]);
curR--;
}
while (curL > qry[i].L) {
curL--;
add(S[curL]);
}
while (curL < qry[i].L) {
sub(S[curL]);
curL++;
}
answer[qry[i].qid] = curMax;
}
```
----
### 對於左界
左界屬於同一塊的詢問，每次都不會移動超過$\frac{N}{K}$次；
而左界屬於不同塊的操作，移動次數加起來也不超過$N$次。
所以左界移動的時間複雜度為$O(\frac{NQ}{K})$。
----
### 對於右界
相同塊：因為$R_i$是遞增的，所以對於同一塊最多花費$O(N)$的時間。
對於不同塊因為交界最多只有$O(K)$次，每次最多也花費$O(N)$，故維護右界的時間複雜度為$O(KN)$。
----
取$K = \sqrt{N}$，於是我們得到一個時間複雜度為$O(\frac{NQ}{K} + KN) = O(Q\sqrt{N} + N\sqrt{N})$的做法
---
## 分case
----
<font color="red" style="font-size: 200%">遺珠QQ</font>
---
## 擁抱分治，向資結說不
----
### WHY 離線?
- 在線作法不好做
- 在線太久太滿太胖
---
### 整體二分
----
#### METEOR
長度 $M$ 的序列，一開始都是$0$
$N$ 個人瓜分這個序列，每個人有他的目標 $g_i$
$K$ 次操作，每次都是序列某個區間全部加上 $x_i > 0$
問每個人什麼時候達到目標
也就是擁有的元素加起來 $\ge g_i$
----
每個人二分搜何時達到目標
用可持久線段樹維護每個操作做完的序列長相
----
時間 $O((M+N) \log K \log M)$
空間 $O(K \log M)$
----
<font color="red" style="font-size: 200%">MLE</font>
mempry limit: 64 mb
----
開 $K$ 棵線段樹真的太虧了
看來不能每個人各自二分搜了
----
```C++11=
typedef vector< int > VI;
void totBS( int s , int e , VI nation ) {
if(s > e || nation.size() == 0)
return ;
int mid = (s + e) / 2;
do_things( s , mid );
VI ok, notok;
split( mid , nation , ok , notok );
undo_things( s , mid );
totBS( s , mid-1 , ok );
totBS( mid+1 , e , notok );
}
```
----
看那些人可以在 mid 之前達到目標
可以的丟去二分搜 $[s,mid−1]$
不行的丟去二分搜 $[mid+1,e]$
----
把 [s,mid] 的操作作用一番
BIT 維護之
```C++11=
void do_things( int s , int mid ) {
for( int i = s ; i <= mid ; i++ ) {
int nl = in[ i ].l , nr = in[ i ].r;
ll nnu = in[ i ].nu;
bit.upd(nl, nnu);
bit.upd(nr+1, -nnu);
}
}
```
----
看那些人在 mid 前可以被滿足
並且更新他們的目標 (把 [s,mid] 對他們貢獻扣掉)
```C++11=
void split( int mid , VI& nation , VI& ok , VI& notok ) {
for( int nat : nation ) {
tem[nat] = 0ll;
for( int it : satel[ nat ] ) {
tem[nat] += bit.qry(it);
if(tem[nat] >= need[nat])
break;
}
if(tem[nat] >= need[nat]) {
ok.push_back(nat);
if(ans[nat] > 0) ans[nat] = min(ans[nat], mid);
else ans[nat] = mid;
}
else {
need[nat] -= tem[nat];
notok.push_back(nat);
}
}
// 真的把 nation 佔的記憶體釋放掉
VI ().swap( nation );
}
```
----
把 BIT 還原
還給子孫乾淨的 BIT
```C++11=
void undo_things( int s , int mid ) {
for(int i = s; i <= mid; i++) {
int nl = in[i].l, nr = in[i].r;
ll nnu = in[i].nu;
bit.upd(nl, -nnu);
bit.upd(nr+1, nnu);
}
}
```
----
時間： $O((N+M+K) \log M \log K)$
空間： $O(M)$ (這寫法空間真的是線性嗎^^)
----
<font color="green" style="font-size: 200%">MLE</font>
----
<font color="green" style="font-size: 200%">AC</font>
其實這作法好好寫可以不用 BIT
時間少一個 O(logM)
空間也是好好線性
---
## 操作分治
----
在線好難做
把操作們整理成方便處理的順序
變得好做
----
#### MACHINE WORKS
給你 $N,t_i,g_i,r_i,p_i$
$1 \le N \le 10^5$ , $t_i$ 遞增
計算下列 DP 式 :
$dp[i]=max_{j<i}$ {$g_j \times t_i+(r_j−p_j+dp[j]−(t_j+1)\times g_j)$}
----
阿不就斜率優化 DP
deque 做過去就沒啦
----
可是 $g_j$ 沒有單調性
<font color="red" style="font-size: 200%">慘</font>
----
用平衡樹維護下凸包
算好一個 $dp[i]$ 後
把 $y = g_i \times x + (r_j − p_j + dp[i] − (t_j + 1) \times g_j)$ 塞進去
把附近斜率不必要的線拔掉
一堆邊界條件好難寫
----
### 好希望 $g_j$ 有單調性阿~~
----
想想分治
先把 $dp[1 \dots \frac{N}{2}]$ 做完
按照 $g_j$ 排好
那就可以輕鬆做 $dp[\frac{N}{2} + 1 \dots N]$ 了耶
----
所以可以得到長這樣的作法
```C++11=
void solve( int l , int r ) {
if( l == r ) return ;
int mid = ( l + r ) / 2;
solve( l , mid );
// 把 [l, mid] 整理好
// 算 [l, mid] 對 [mid+1, r] 答案的影響
solve( mid+1 , r );
}
```
----
整理好就只是
先把線做出來，排序好
```C++11=
vector< Line > lns , stk;
lns.clear();
for( int i = l ; i <= mid ; i++ )
if( in[ i ].dp >= in[ i ].P ) {
Ln l1{
in[ i ].G ,
in[ i ].dp-in[ i ].P+in[ i ].R
-( in[ i ].D+1ll )*in[ i ].G
};
lns.push_back( l1 );
}
sort( lns.begin() , lns.end() );
```
----
然後做出下凸包，把不必要的線拿走
```C++11=
stk.clear();
for( Ln l1 : lns ) {
while( stk.size()
&& stk.back().m == l1.m
&& stk.back().b < l1.b )
stk.pop_back();
if( stk.size() && stk.back().m == l1.m ) continue ;
while( stk.size() >= 2
&& !ok( stk[ stk.size() - 2 ] ,
stk[ stk.size() - 1 ] , l1 ) )
stk.pop_back();
stk.push_back( l1 );
}
```
----
## 不必要的線？
像圖中紅色的線就是爛線
----
接下來就是要去更新 $[mid+1,r]$ 的 $dp$ 值了
```C++11=
int j = 0;
for( int i = mid+1 ; i <= r ; i++ ) {
ll x = in[ i ].D;
while( j + 1 < (int)stk.size()
&& stk[ j ]( x ) < stk[ j+1 ]( x ) )
j++;
in[ i ].dp = max( in[ i ].dp , stk[ j ]( x ) );
}
dq( mid + 1 , r );
```
----
這裡只處理 $[l,mid]$ 對 $dp[i]$ 的影響
$[mid+1,i−1]$ 的影響透過 $dq(mid+1, r)$ 遞迴搞定
----
好好 merge sort 線的斜率的話
時間 : $O(N \log N)$
----
#### 矩形面積和
在一個二維平面上有 $n$ 個點，大家都知道，任兩個點可以形成一個矩形，而現在要你求出所有任兩點形成的矩形(共 $n * (n - 1) / 2$ 個矩形)面積和。
$2 \le n \le 100000$
$0 \le x_i, y_i \le 10000$
----
#### ADA Farm
在ADA農場中有 $N$ 隻貓咪，第 $i$ 貓咪位於 $(x_i, y_i)$。
貓咪如果上下左右移動的話，會耗費$1$單位時間。
貓咪如果走日字形移動的話，會耗費$2$單位時間。
定義 $D(i, j)$ 代表第$j$隻貓咪走到第$i$隻貓咪所在位置的最小花費時間
對於每隻貓咪$i$，請求出$D(i, 1) + D(i, 2) + \dots + D(i, N)$
----
```C++11=
int calc(int dx, int dy) {
if (dx < dy) swap(dx, dy);
if (dx >= 2 * dy) return dx;
else return 2 * (dx + dy + 1) / 3;
}
```
---
## Q&A
Sign in with Wallet
Connect another wallet