APCS 20210905 題解

題目

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$ 就是你要的最小值位置。至於區間和用前綴和算。

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$ 個節點的數，每個節點上都有一個值，根節點的值為

$\underset{1\le i\le n}{min}{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 邊算。

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\le l_2\le r_1\le r_2$，那可以換成

$[l_1,l_2-1]$、

$[l_2,r_2]$，讓這兩個區間變得不相交、聯集範圍不變。

所以我們只要考慮所有區間都不重疊的狀況，令

$dp[i][j]=$ 選了

$i$ 個區間、最後一個區間右端點在

$j$ 或之前的答案，

$\mathrm{\forall }0\le j\le n,dp[0][j]=0$，轉移式：

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

也就是在

$k$ 之前選

$i-1$ 個區間，再選

$[k,j]$。

令

$t(j)=$ 以

$j$ 為右端點的合法區間中，最左邊的左端點，上式中的

$k$ 範圍就是

$t(j)\le k\le j$，轉移式可以改為

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

所以目標就是在

$t(j)\le k\le 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$ 上一次出現的位置更新這個值。

單調隊列版 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;
}