# 111 選手班 - 綜合應用
###### tags: `宜中資訊` `CP`
2022.08.26

## 持久化線段樹
[110 slide](https://hackmd.io/@Ccucumber12/B1PqClBlY#/6)
### 問題
給定數列 $a_1, a_2, \cdots, a_N$，請支援以下操作 $Q$ 次
- $\text{add x v}$：將 $a_x$ 加上 $v$
- $\text{query l r k}$：詢問第 $k$ 次修改號的狀態（sum, max, ...）

$N, Q, a_i \le 10^6$

### 操作
#### 離線 Offline
- 整理好需要那些詢問
- 正常操作過程中直接查詢那些詢問
- 最後再次排序輸出
- $\mathcal O(Q\log N)$

#### 在線 Online
- 回到過去的某個版本
- 每次更新都重新開一顆線段樹
- 空間複雜度：$\mathcal O(QN)$

### Copy on Write
- 指備份被修改的點 $\mathcal O(\log N)$
- 每個版本用一個新的 root 指下去
- 空間複雜度：$\mathcal O(N + Q\log N)$

### Code
:::spoiler

struct node{
    node *lch, *rch;
    int val;
    
    node () {
        lch = rch = nullptr;
        val = 0;
    }
    
    void pull(){
        val = lch -> val + rch -> val;
        // val = max(lch -> val, rch -> val) ;
    }
};

void build(int l, int r, node *&p){
    p = new node();
    if(l == r) { 
        p -> val = a[l] ;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, p -> lch);
    build(mid+1, r, p -> rch);
    p -> pull() ;
}
 
void modify(int pos, int val, int lb, int rb, node *pre, node *&cur){
    cur = new node();
    
    if(lb == rb) {
        cur -> val = pre -> val + val;
        return ;
    }
    
    cur -> lch = pre -> lch;
    cur -> rch = pre -> rch;
    int mid = (lb + rb) >> 1;
    
    if(pos <= mid) modify(pos, lb, mid, pre -> lch, cur -> lch);
    if(mid <  pos) modify(pos, mid+1, rb, pre -> rch, cur -> rch);
    
    cur -> pull();
}
 
int query(int l, int r, int lb, int rb, node *p) {
    if(l <= lb && rb <= r) {
        return p -> val ;
    }

    int mid = (lb + rb) >> 1 ;
    if(l <= mid) query(l, r, lb, mid, p -> lch) ; 
    if(mid <  r) query(l, r, mid+1, rb, p -> rch) ;
}

int main() {
    node *ti[100010] ;

    build(1, n, ti[0]) ;

    for(int i=1; i<=Q; ++i) {
        int op ;
        cin >> op ;
        if(op == 1) {
            int x, v ;
            cin >> x >> v ;
            modify(x, v, 1, n, ti[i-1], ti[i]) ;
        } else {
            int l, r, k ;
            cin >> l >> r >> k ;
            cout << query(l, r, 1, n, ti[k]) << endl ;
            ti[i] = ti[i-1]
        }
    }
}

:::

## 值域線段樹
### 問題：區間第 k 小
給定數列 $a_1, a_2, \cdots, a_N$，請支援以下操作 $Q$ 次
- $\text{query l r k}$：詢問區間 $a_l, \cdots, a_r$ 中第 $k$ 小的數字

$N, Q, a_i \le 10^6$

### 值域線段樹
- 將 $\text{seg}[i]$ 定為數字 $i$ 有多少個
- 區間和 $\text{seg[L, R]}$ 代表介於 $[L, R]$ 區間的數字有多少個

**Case 1：只詢問 $[1, N]$**
- 依序把每個數字塞進去線段樹
- 尋找最小的 $i$，使得區間和 $\text{seg}[1, i]$ 恰好大於等於 $k$
- 二分搜：$\mathcal O(\log N)$

**Case 2：只詢問 $[1, R]$**
- $[1, R]$ 相當於塞到第 $R$ 個數字時線段樹的 Case 1
- 持久化線段樹查詢：第 $R$ 個版本

**General：詢問 $[L, R]$**
- 詢問第 $L$ 到第 $R$ 個版本的數字
- 持久化線段樹查詢：版本 $R$ - 版本 $(L-1)$

## 單調隊列優化
### 題目
請支援以下 $Q$ 筆操作
- 插入一條直線：$f(x) = a_i(x) + b_i$
- 查詢目前直線中 $x_i$ 的最大值：$\max (f(x_i))$

限制
- $Q \le 10^6$
- 對於直線有：$a_1 \ge a_2 \ge \cdots \ge a_n \ge 1$
- 對於查詢有：$1 \le x_1 \le x_2 \le \cdots \le x_n$

### 單調性
- 斜率只會越來越小
- 查詢位置越來越大

### 單調隊列優化
- 加入一條新的直線
- 可能會壓過某些之前的直線
- 那些直線再也不會用到了
- 往後查詢某個 $x$
- 可能會離開某些直線的最大值範圍
- 那些直線再也不會用到了
- 用 stack 維護目前跟之後有可能成為最大值的直線
- top 是目前 $x$ 最大值的位置
- 每次加入新的直線可能會 pop 掉某些人
- 每次往後移動 $x$ 也可能會 pop 掉某些人

## 斜率優化
### 題目
請支援以下 $Q$ 筆操作
- 插入一條直線：$f(x) = a_i(x) + b_i$
- 查詢目前直線中 $x_i$ 的最大值：$\max (f(x_i))$

限制
- $Q \le 10^6$

### 覆蓋區間
- 每個直線都的最大值區域必定是一個連續區間
- 用線段樹維護每個區間的最大值是被哪條直線覆蓋
- 每次插入直線都是一些區間修改
- 如果完整覆蓋 or 被完整覆蓋就結束遞迴
- 否則繼續往下遞迴


### 時間複雜度
- 每次必定只有其中一邊會往下遞迴（因為是線性函數）
- 最多往下遞迴 $\log (N)$ 層
- 總時間複雜度 $\mathcal O(Q\log N)$

## 李超線段樹
### 題目
請支援以下 $Q$ 筆操作
- 插入一條線段：$f(x) = a_i(x) + b_i,\quad x\in [L, R]$
- 查詢目前直線中 $x_i$ 的最大值：$\max (f(x_i))$

### 李超線段樹
- 把線段拆分成 $\log N$ 個完整覆蓋的線段
- 每個再各自往下遞迴修改
- 單次操作時間複雜度 $\mathcal O(\log^2 N)$

## DP 優化應用
### 題目
有 $N$ 個石頭，第 $i$ 個石頭的高度是 $h_i$，目標從第 $1$ 個石頭跳到第 $N$ 個石頭。若現在位於第 $j$ 個石頭，可以跳到任何一個編號大於 $j$ 的石頭 $i$，但需要花費 $(h_i - h_j)^2 + C$ 能量。請問最少需要花費少能量才能到達石頭 $N$？

限制
- $N \le 2\times 10^5$
- $C \le 10^12$
- $1 \le h_i \le 10^6$

### DP
- 定義：$\text{dp}[i]$ 為跳到石頭 $i$ 的最小花費
- 轉移：$\text{dp}[i] = \max\{(h_j - h_i)^2 + C + \text{dp}[j]\ |\ j < i\}$
- 時間複雜度：$\mathcal O(N^2)$

### 把轉移拆開
- $(h_j - h_i)^2 + C + \text{dp}[j]$
- $h_j^2 -2h_ih_j + h_i^2 + C + \text{dp}[j]$
- $2h_j\cdot (h_i) + h_j^2 + \text{dp}[j] + h_i^2 + C$
- $\max\{2h_j\cdot(h_i) + h_j^2 + \text{dp}[j]\ |\ j < i\} + h_i^2 + C$
- $\max\{a_j\cdot(h_i) + b_j |\ j < i\} + h_i^2 + C$
- 斜率優化！
- 時間複雜度：$\mathcal O(N\log N)$

## 題單
- [contest](https://vjudge.net/contest/512270)
- password：`111apcs`