---
tags: APCS
---

# APCS 20210905 題解

[題目](https://hackmd.io/@yungyao/HyFRzzWfF)

## pC

這題唯一的難點是要找區間裡最小的數，其他都很簡單。

可以暴力地用能夠 RMQ 的資料結構來做，時間是 $O(n \log n)$，不過注意到這題的詢問區間肯定被上一個詢問包含，利用這個性質就可以不寫資料結構。

### $O(n \log n)$ 版

把 $1$ 到 $n$ 按 $p_i$ sort，在算 $f(l,r)$ 的時候，看剛剛 sort 的那堆裡的第一個，假設它是 $p$，如果 $p$ 不在 $[l,r]$ 裡就可以把它丟了，以後也不會再用到，因為之後的詢問範圍也會在 $[l,r]$ 裡面，如果 $p$ 在 $[l,r]$ 裡，那 $p$ 就是你要的最小值位置。至於區間和用前綴和算。

:::spoiler code

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

int n;
vector<int> a, p;
vector<ll> s;
int np = 0;

int f(int l, int r){
    if(l == r) return a[l];
    while(p[np] < l || r < p[np]) np++;
    int m = p[np];
    if(s[m - 1] - s[l - 1] > s[r] - s[m]){
        return f(l, m - 1);
    }
    else{
        return f(m + 1, r);
    }
}

int main(){
    StarBurstStream

    cin >> n;
    a.resize(n + 1);
    p.resize(n);
    s.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        p[i - 1] = i;
    }

    sort(iter(p), [](int u, int v){
        return a[u] < a[v];
    });

    cout << f(1, n) << "\n";

    return 0;
}

:::

### $O(n)$ 版

（感謝 dreamoon 在某篇貼文下的留言讓我想到有這個作法）

> Cartesian Tree 定義：
> 一個數字皆相異的序列 $a_1,a_2,\dots,a_n$ 的 Cartesian Tree 是一個有 $n$ 個節點的數，每個節點上都有一個值，根節點的值為 $\min_{1 \leq i \leq n} a_i$，若這個值是 $a_m$，則左子樹為 $a_1,a_2,\dots,a_{m-1}$ 的 Cartesian Tree、右子樹為 $a_{m+1},a_{m+2},\dots,a_n$ 的 Cartesian Tree。空序列的 Cartesian Tree 定義為空樹。

可以發現到，題目的 $f(l,r)$ 遞迴過程就是從 Cartesian Tree 的根節點走的某個葉節點的路徑，根節點就是 $[1,n]$ 內的最小值，它的左右子樹就是最小值的左側和右側，因此 $f(l,r)$ 就變成了：如果左子樹的總和較右子樹大，就往左子樹走，否則往右子樹走。

$O(n)$ 蓋 Cartesian Tree 的方法是，從左邊看到右邊，把現在看到的數加進 Cartesian Tree 裡。因為加進 $a_i$ 的時候，它就是序列最右邊的那個數，所以它在 Cartesian Tree 上肯定是由根節點一路向右，直到沒有右子節點為止所到達的節點，因此只要在原本的樹上找到它應該放的位置即可。維護根節點一路往右走的路徑，這條路徑上的值是遞增的，找到（上到下）第一個 $> a_i$ 的節點，把它變成 $a_i$ 的左子節點，而 $a_i$ 的父節點就是它原本的父節點（或根）。

區間和可以邊蓋 Cartesian Tree 邊算。

:::spoiler code

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);

using namespace std;

typedef long long ll;

int n;
vector<int> a;
vector<ll> s;
vector<int> l, r; // 左右子節點

int f(int now){
    if(l[now] == 0 && r[now] == 0) return a[now];
    if(s[l[now]] > s[r[now]]) return f(l[now]);
    else return f(r[now]);
}

int main(){
    StarBurstStream

    cin >> n;
    a.resize(n + 1);
    s.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);

    stack<int> st;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = a[i];
        int lst = 0;
        while(!st.empty() && a[st.top()] > a[i]){
            lst = st.top();
            st.pop();
            s[lst] += s[r[lst]];
        }
        if(!st.empty()){
            r[st.top()] = i;
        }
        st.push(i);
        l[i] = lst;
        s[i] += s[lst];
    }
    int root;
    while(!st.empty()){
        root = st.top();
        s[root] += s[r[root]];
        st.pop();
    }

    cout << f(root) << "\n";

    return 0;
}

:::

~~應該是不會有人想要在考試中寫這個~~

## pD

定義如果一個區間當中沒有重複數字，則它是一個合法區間。

肯定有一個最佳解滿足其中每一個肯定滿足其中任兩個區間不相交，首先，當然不會有區間完全包含另一個區間，否則只要留下比較大的那個就好了，如果有兩個區間 $[l_1,r_1]$、$[l_2,r_2]$ 部分相交，也就是 $l_1 \leq l_2 \leq r_1 \leq r_2$，那可以換成 $[l_1,l_2-1]$、$[l_2,r_2]$，讓這兩個區間變得不相交、聯集範圍不變。

所以我們只要考慮所有區間都不重疊的狀況，令 $dp[i][j]=$ 選了 $i$ 個區間、最後一個區間右端點在 $j$ 或之前的答案，$\forall 0 \leq j \leq n,\ dp[0][j]=0$，轉移式：

\\[dp[i][j]=\max\{dp[i-1][k-1] + j - k + 1 \mid k \leq j,\ [k,j] \text{ is valid}\}\\]

也就是在 $k$ 之前選 $i-1$ 個區間，再選 $[k, j]$。

令 $t(j)=$ 以 $j$ 為右端點的合法區間中，最左邊的左端點，上式中的 $k$ 範圍就是 $t(j) \leq k \leq j$，轉移式可以改為

\\[dp[i][j]=j+1 + \max\{dp[i-1][k-1] - k \mid t(j) \leq k \leq j\}\\]

所以目標就是在 $t(j) \leq k \leq j$ 的範圍裡找到最小的 $dp[i-1][k-1]-k$。注意到 $t(j)$ 是遞增的，因此可以用雙指標搭配 multiset 來做，時間複雜度是 $O(kn \log n)$。也可以用單調隊列，時間複雜度會降為 $O(nk)$。

計算 $t(j)$ 的方法是，從 $1$ 看到 $n$，記錄每一種數字出現的位置，$t(j)$ 的值就是「最右邊的某種數字倒數第二次出現的位置 $+1$」，因此可以在看到 $j$ 時，用 $a_j$ 上一次出現的位置更新這個值。

:::spoiler 單調隊列版 code

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define eb(a) emplace_back(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second

using namespace std;

using pii = pair<int, int>;

int main(){
    StarBurstStream

    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> lst(100001, -1);

    vector<int> t(n + 1);
    int now = 0;
    for(int i = 1; i <= n; i++){
        if(lst[a[i]] != -1) now = max(now, lst[a[i]]);
        t[i] = now + 1;
        lst[a[i]] = i;
    }

    vector<vector<int>> dp(k + 1, vector<int>(n + 1));
    for(int i = 1; i <= k; i++){
        deque<pii> dq;
        for(int j = 1; j <= n; j++){
            while(!dq.empty() && dq.front().S < t[j]) dq.pof;
            while(!dq.empty() && dq.back().F <= dp[i - 1][j - 1] - j) dq.pob;
            dq.eb(mp(dp[i - 1][j - 1] - j, j));
            dp[i][j] = max(dp[i][j - 1], j + 1 + dq.front().F);
        }
    }

    cout << dp[k][n] << "\n";

    return 0;
}

:::