# 成大邀請賽 初賽 題解

## A. 小業教授的研究計畫

###### tags: constructive algorithm

###### author: ColtenOuO, 難度定位: Easy

結論：只有唯一的 $1$ 種填法

如果要你輸出那組解呢？

::: spoiler 參考程式碼 (ColtenOuO)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	int a,b,c;
	cin >> a >> b >> c;
	
	cout << 1 << "\n";
	
	return 0;
}

:::

## B. 分組任務

###### tags: binary search, graphs, data structure

###### author: sam571128, 難度定位: Medium

### 子任務 1: $1 \le n \le 18$

可以直接用遞迴或者位元枚舉的方式

將每張牌分配到第一組或第二組

在枚舉的過程中，更新最大答案即可

複雜度：$\mathcal{O}(n^22^n)$

### 接下來的想法

觀察到其實我們可以將兩兩牌之間的關係畫成一張無向圖

而這個問題就轉化為「將點分成兩組，取兩組內最小的邊」

由於我們想要選的答案是最小的最大答案

可以很直覺的想到，其實我們可以「對答案二分搜」！

不過要怎麼檢查答案呢？

最容易想到的假解可能是：「檢查 $x$ 的時候，將 $\le x$ 的邊加入，如果連通塊數量是 $2$，就是合法的」

會發現到如果這樣做，有可能發現大的邊也會跟著被用到！

因此，其實正確的作法是

「把 $>x$ 的邊的兩點分別分到不同的組，如果可以達成這樣做沒有矛盾，$x$ 就是合法的」

### 子任務 2: $1 \le n \le 1000$

用上面的想法，暴力的將兩點分到不同組（作法可能滿多的）

### 滿分解

發現到其實在檢查的時候，如果我們把 $> x$ 的邊都加入

其實要檢查的是「這張圖是不是二分圖」！

所以可以用 DFS 或者 DSU 等方式做完

時間複雜度：$O((n+m) \log C)$, $O(m \alpha(n) \log C)$

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>

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


using namespace std;

const int N = 1e6+5;
vector<pair<int,int>> adj[N];
int dsu[N];

int find(int u){
    return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}

void unite(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    dsu[u] = v;
}

int n;

bool check(int x){
    iota(dsu,dsu+N,0);

    for(int i = 0; i < n; i++){
        for(auto [j,w] : adj[i]){
            if(w > x){
                if(find(i) == find(j) || find(i+n) == find(j+n)) return false;
                unite(i,j+n);
                unite(i+n,j);
            }
        }
            
    }


    return true;
}

signed main(){
    fastio

    int m;

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    int l = 0, r = 1e9+7;
    while(l < r){
        int mid = l+r>>1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }

    cout << r << "\n";
}

:::

### 真的需要二分搜嗎？

其實會發現，二分搜在做的事情其實也就只是判斷 $> x$ 的邊的圖是不是二分圖

那我們把邊從大到小排序好，依序從大到小加入圖

那這題的答案其實就是「第一個使得圖變成不是二分圖的邊權」

當然，如果這張圖本身就是二分圖，答案就是 $0$

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>

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


using namespace std;

const int N = 1e6+5;
vector<pair<int,pair<int,int>>> edges;
int dsu[N];

int find(int u){
    return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}

void unite(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    dsu[u] = v;
}

int n;

signed main(){
    fastio
    iota(dsu,dsu+N,0);

    int m;

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        edges.push_back({w,{u,v}});
    }

    sort(edges.begin(),edges.end(),greater<>());

    for(auto [w, p] : edges){
        auto [u,v] = p;
        if(find(u) == find(v)){
            cout << w << "\n";
            return 0;
        }
        unite(u,v+n);
        unite(v,u+n);
    }
    cout << 0 << "\n";
}

:::

## C. 大富翁

###### tags: greedy, dp, STL

###### author: sam571128, 難度定位: Medium

靈感來源：[Codeforces 1526C2 - Potions (Hard Version)](https://codeforces.com/problemset/problem/1526/C2)

### 子任務 2: $1 \le n \le 5, 1 \le a_i,b_i \le 10$

基本上就是給人唬爛用的，可以用遞迴或者迴圈直接暴力跑過所有情形

最後再去檢查答案即可

複雜度：$\mathcal{O}(10^5)$

### 子任務 3, 4: $1 \le n \le 100$, $1 \le n \le 10^4$

$dp$，會發現其實這個問題與背包很相似

有一個很直覺的 $dp$ 是這樣的

$$令 \ dp[i][j] \ 為前 \ i \ 輪遊戲中，最後的錢的數量為 \ j \ 所需花的最少輪$$

不過由於 $a_i, b_i$ 的範圍很大，沒有辦法直接設這樣的狀態

有寫過 [這題](https://atcoder.jp/contests/dp/tasks/dp_e) 的人，可能知道處理方式

既然將總共的錢的數量存起來空間存不下，那我們將狀態設計交換！

$$令 \ dp[i][j] \ 為前 \ i \ 輪遊戲中，在 \ j \ 輪花了錢，最少可以有的錢$$

那轉移式其實很好想，就會是底下這樣

$$dp[i][j] =
\max
\begin{cases}
\max(0,dp[i-1][j-1] + a[i] - b[i]) &, j \ne 0 \\
dp[i-1][j] + a[i]
\end{cases}$$

不過由於有 $k$ 輪必須要將錢花完，可以額外判斷如果 $i \in {t_1, t_2, \cdots, t_k}$，那當 $dp[i][j] > 0$ 的時候，就將答案設成 $\infty$ 等等

複雜度：$\mathcal{O}(n^2)$

::: spoiler 參考程式碼 (sam57128)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long 

using namespace std;

const int N = 1e3+5;
int dp[N][N]; //The minimum money one can have after spending j times
int arr[N], cost[N], val[N];

signed main(){
    fastio
    int n,k;
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        val[i] = 1e18;
    }

    for(int i = 1; i <= n; i++){
        cin >> cost[i];
    }

    while(k--){
        int t;
        cin >> t;
        val[t] = 0;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] = 1e18;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            dp[i][j] = dp[i-1][j] + arr[i];
            if(j != 0){
                dp[i][j] = min(dp[i][j], max(0LL, dp[i-1][j-1] + arr[i] - cost[i]));
            }
            if(dp[i][j] > val[i]){
                dp[i][j] = 1e18;
            } 
        }
    }
    
    for(int i = 0; i <= n; i++){
        if(dp[n][i] <= 1e15){
            cout << i << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
}

:::

### 滿分解

在這個情況下，單純的 $dp$ 已經沒辦法通過這題了

可以注意到，其實對於每一次要將錢歸零的 round，中間的情況都是獨立的

因此，其實對於題目的 $k$，可以想成是我們要解底下這個問題

「每一輪會得到 $a_i$ 元，而每輪最多可以花 $b_i$ 元，過程中，錢的數量必須 $\ge 0$，然後在結束時，錢必須是 $0$。最少需要在多少輪花費錢」

那對於這個問題，其實我們可以用貪心的方式去思考，對於每一天，能讓錢的數量越少，就花多少。當我們遇到錢要低於 $0$ 的時候，我們就將花最少錢的操作「反悔」掉！直到我們的錢回復到 $\ge 0$ 的情況。

因此，我們會需要一個可以儲存花過錢的情況的資料結構，並能夠得到最小值和刪除最小值。

而這個就是 Min Heap (`priority_queue`) 可以做到的事情，也可以使用 set, BIT, 線段樹等資結

時間複雜度：$\mathcal{O} (n \log n)$

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

const int N = 1e6+5;
int arr[N], arr2[N], has[N];

signed main(){
    fastio

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

    int sum = 0;
    priority_queue<int> pq;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }

    for(int i = 1; i <= n; i++){
        cin >> arr2[i];
    }

    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        has[x] = 1;
    }
    int ans = 0;

    for(int i = 1; i <= n; i++){
        sum += arr[i];
        if(arr2[i]!=0){
            sum -= arr2[i];
            pq.push(-arr2[i]);
        }
        while(sum < 0){
            auto x = pq.top(); pq.pop();
            if(sum + (-x) > 0){   
                pq.push(x-sum);
                sum = 0;
                break;
            }else{
                sum += (-x);
            }
        }


        if(has[i]){
            if(sum > 0){
                cout << -1 << "\n";
                return 0;
            }
            ans += pq.size();
            while(!pq.empty()) pq.pop();
        }
    }

    cout << ans << "\n";


}

:::

## D. 身分調查

###### tags: graphs, data structure, dp

###### author: sam571128, official solution: victor.gao, 難度定位: Hard

靈感來源： [Codeforces 1594D - The Number of Imposters](https://codeforces.com/problemset/problem/1594/D)

### 最重要的想法

首先，如果 $a$ 說 $b$ 是誠實的，那代表什麼？
- 如果 $a$ 是誠實派的，那 $b$ 也是誠實派的
- 如果 $a$ 是說謊派的，那 $b$ 也是說謊派的

反之，如果 $a$ 說 $b$ 是說謊的，那代表什麼？
- 如果 $a$ 是誠實派的，那 $b$ 是說謊派的
- 如果 $a$ 是說謊派的，那 $b$ 是誠實派的

也就是說，其實我們可以將敘述改寫成
- 如果 $a$ 說 $b$ 誠實，$a,b$ 相同陣營
- 如果 $a$ 說 $b$ 說謊，$a,b$ 不同陣營

### 子任務 1: $K = 2$

既然敘述只有兩個，就照上面的邏輯好好的判 case 即可

### 子任務 2: $K \le 100$

暴力做

可以去枚舉要刪掉的區間，將沒有刪掉的其他的邊加入圖，每次用 DFS 塗色，去判斷有沒有辦法走到 $x$。如果可以，就可以知道 $x$ 的陣營了。接著就將最小的區間更新即可

枚舉的時間會是 $\mathcal{O}(K^2)$，但每一次都要跑過整張圖（只要跑有被說過的點就好，不用跑過 $N$ 個），所以是 $\mathcal{O}(K)$

複雜度： $O(K^3)$

### 子任務 3: $K \le 5000$

跟上一題一樣，只是現在範圍變大了，沒辦法再每次都跑過整張圖

因此，我們會需要動態加邊，動態判斷答案的資料結構

而這個資料結構就是「並查集」

如果熟悉用並查集判斷二分圖的話，應該可以知道作法

對於每個點 $u$，建兩個 $u_0, u_1$，分別表示 $u$ 是誠實派和 $u$ 是說謊派的點

而對於兩種不同的操作，分別建的邊會是

1. 建 $u_0 - v_0$, $u_1 - v_1$（相同陣營）
2. 建 $u_0 - v_1$, $u_1 - v_0$（相反陣營）

判斷的時候，判斷 $1$ 與 $x_0$ 還是 $x_1$ 在同一個連通塊即可

複雜度：$\mathcal{O}(K^2 \alpha(n))$

### 子任務 4: 保證有一個敘述是 $(x,y)=(1,X)$

給人唬爛用的

### 滿分解（一）二分搜 + 動態圖連通 By sam571128

會發現我們想要找可以刪掉的最大區間，因此，考慮二分搜！

假設我們現在要搜尋的長度為 $l$，那其實現在問題變成「能不能刪掉連續的 $l$ 條邊，讓 $1$ 和 $x_0, x_1$ 是連通的」

這個動作其實和 sliding Window 在做的事情很像，因此其實我們可以考慮看看用 sliding window 來處理！

一開始先將 $1 \sim l$ 的邊加入，當我們要往右滑的時候，就將最左邊的邊加入，最右邊的邊刪除

因此，問題就轉變成了很經典的「[Dynamic Connectivity](https://codeforces.com/edu/course/2/lesson/7/3/practice/contest/289392/problem/C)」的問題

所以，這裡有兩種作法

1. 使用 Link-Cut Tree 或 Euler Tour Tree 等作法，每次滑窗需要花 $O(\log^2 n)$ 的時間
2. 這裡不用在線，所以其實可以考慮 時間線段樹 + rollback DSU 的作法！

如果是第一種做法，那其實就照做就好，所以這裡不特別提

這裡來講講第二種作法，仔細想一下 sliding window 在做的事情

會發現其實每條邊都會剛好存在於一個時間區間

因此可以用類似的方式在時間線段樹加邊

接著就可以維護好每一個 window 的答案了

接著就從左界最小的開始做即可！

複雜度：$\mathcal{O}(k \log n \log^2 k)$，常數太大可能會被卡

::: spoiler 參考程式碼（時間線段樹 sam571128）

#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  
using namespace std;
  
const int N = 2e5+5;
int dsu[N], sz[N], ans[N];
vector<pair<int,int>> st_dsu, st_sz;
vector<pair<int,int>> tr[4*N];
 
inline void rollback(){
    auto [a,b] = st_dsu.back(); st_dsu.pop_back();
    auto [c,d] = st_sz.back(); st_sz.pop_back();
    dsu[a] = b;
    sz[c] = d;
}
  
inline int find(int u){
    return dsu[u]==u ? u : find(dsu[u]);
}
  
inline void unite(int u, int v){
    u = find(u), v = find(v);
    if(u==v){
        st_dsu.emplace_back(pii(0,dsu[u]));
        st_sz.emplace_back(pii(0,sz[v]));
        return;
    }
    if(sz[u] > sz[v]) swap(u,v);
    st_dsu.emplace_back(pii(u,dsu[u]));
    st_sz.emplace_back(pii(v,sz[v]));
    dsu[u] = v;
    sz[v] += sz[u];
}
  
inline void add(int ml, int mr, pair<int,int> val, int idx, int l, int r){
    if(ml <= l && r <= mr){
        tr[idx].emplace_back(val);
        return;
    }
  
    int mid = l+r>>1;
    if(ml <= mid) add(ml,mr,val,idx<<1,l,mid);
    if(mr > mid) add(ml,mr,val,idx<<1|1,mid+1,r);
}
  
int n,m,x,flag=0;
  
inline void dfs(int idx, int l, int r){
    int cnt = 0;
    for(auto [u,v] : tr[idx]){      
        if(find(u)!=find(v)){
            unite(u,v);
            cnt++;
        }
    }
    if(l == r){
        if(find(1)==find(x)) ans[l] = 1;
        else if(find(1)==find(x+n)) ans[l] = 2;
    }
    else{
        int mid = l+r>>1;
        dfs(idx<<1,l,mid);
        dfs(idx<<1|1,mid+1,r);
    }
    while(cnt--) rollback();
    tr[idx].clear();
}
pair<pair<int,int>,int> queries[N];
  
int ll, rr, tmp;
  
inline bool check(int t){
    if(t == -1){
        return true;
    }
  
    if(x == 1){
        return true;
    }
  
    if(t == m){
        return false;
    }
  
    for(int i = 1; i <= m; i++){
        auto [p,s] = queries[i-1];
        auto [a,b] = p;
        if(i <= m-t){
            add(i,2*(m-t)-i,{a,b},1,1,2*m-2*t);
        }
        if(i > t){
            add(m-t+m-i+1,2*m-2*t,{a,b},1,1,2*m-2*t);
        }
    } 
  
    for(int i = 0; i <= 2*m-2*t; i++){
        ans[i] = 0;
    }
  
    dfs(1,1,2*m-2*t);
  
    int mn = 1e9;
  
    for(int i = 1; i <= m-t; i++){
        if(ans[i] == 1){
            mn = min(mn, i+1);
        }else if(ans[i] == 2){  
            mn = min(mn, i+1);
        }
    }
  
  
    for(int i = m; i >= t+1; i--){
        if(ans[m-i+1+m-t] == 1){
            mn = min(mn, i-t);
        }else if(ans[m-i+1+m-t] == 2){
            mn = min(mn, i-t);
        }
    }
  
    if(mn != 1e9){
        ll = mn, rr = mn+t-1;
        return true;
    }
    return false;
}
  
signed main(){
    fastio
    iota(dsu,dsu+N,0);
    fill(sz,sz+N,1);
    cin >> n >> m >> x;
  
    for(int i = 0; i < m; i++){
        int a,b,s;
        cin >> a >> b >> s;
        queries[i] = {{a,b},s};
        if (s==1){
            unite(a,b);
            unite(a+n,b+n);
        }
        else {
            unite(a+n,b);
            unite(a,b+n);
        }
    }
    if (find(1)==find(x)) tmp=0;
    else if (find(1)==find(x+n)) tmp=1;
    else {
        cout<<-1<<'\n';
        return 0;
    }
    iota(dsu,dsu+N,0);
    fill(sz,sz+N,1);
    int l = 0, r = m;
    while(l < r){
        int mid = l+(r-l+1)/2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    if(l == 0) cout << l << " " << 0 << " " << 0 << " " << tmp+1 << "\n";
    else cout << l << " " << ll << " " << rr << " " << tmp+1 << " " << "\n";
}

:::

### 滿分解（二）分治優化 By victor.gao
題目要求刪除最大一段中間區間，這問題等價把再陣列複製一倍，留下一段最小的區間
所以問題就變成在這兩倍長的陣列中選取一段最小區間，使得能確定 $x$ 的身分
把題目問題再簡化一點，假設現在有 $a$ 已經確認身分並指認 $b$，那顯然能確定 $b$ 的身分，反過來如果 $a$ 指認 $b$ 且 $b$ 已經確定身分，那也能確定 $a$ 的身分。那可以把 $a$ 指認 $b$ 視為一條無向邊，那整個問題就變成**用一段最小的區間的邊使 $1$ 與 $x$ 連通**。

那觀察一下
假如現在右界 $r_1$ 能成功的最大左界在 $l_1$，那現在有 $r_2 > r_1$，在這情況下加入的邊變多了，那一定可以刪除一些(可能沒有)左界不必要的邊來達成條件，所以在這時候 $l_2 \geq l_1$。
所以我們發現在 $r$ 遞增時，對應到的 $l$ 也會非嚴格遞增，這時候我們把每個 $r$ 對到的左界當做一個 dp 值和轉移來源，可以經過上面敘述的發現他有轉移點單調遞增的情況，而判斷連通性可以用 dsu。

我們考慮分治優化
這時候會遇到一個問題，在分治優化中能使複雜度保持在 $\mathcal{O}(n\ log\ n)$ 是因為每次對詢問的點 $mid$ 都暴力只跑一段他目前可能的轉移點，這樣最多遞迴 $log\ n$ 層，每層暴力跑總和都是 $O(n)$，但現在是要確認連通性，假設現在可轉移來源是 $ql \sim qr$ 現在在查詢的區間是 $l \sim r$ 且查詢的點是 $mid$，不可能每次都把 $qr \sim mid$ 的邊都放入 dsu 再去查詢 $ql \sim qr$，這樣複雜度會不再是 $\mathcal{O}(n\ log\ n)$，那假如我在往左遞迴下去前先把 $dp[mid]+1 \sim min(l-1,qr)$ 先放入 dsu ，往右遞迴前先把 $max(qr+1,l) \sim mid$ 放入 dsu，因為可以知道在後面的遞迴中這段都不會被動到過，離開的時候再 undo，這樣做在查詢一樣能保持分治優化的 $\mathcal{O}(n\ log\ n)$ ，而我們在遞迴前多加入的邊可以發現每層的次數都不超過 $(qr-dp[mid])+(mid-l+1)$ 而這複雜度與分治優化一樣也是 $\mathcal{O}(n\ log\ n)$，總複雜度就會是分治優化加可回溯 dsu 的複雜度 $\mathcal{O}(2k \log (2k) \log n)$

複雜度：$\mathcal{O}(k \log k \log n)$

:::spoiler 題外話
這東西超快好像才跑 300~400 ms，但我們認為初賽不必要把解法卡那麼緊，
所以也讓三個 log 的解過了，不過時間卡的比較緊一點官解跑 2.3 s
然後這想法出現在某次 JOISC 裡 (這樣應該不算暴雷)，然後是電方塊想出來並教我的 \\LCBorz/
:::

::: spoiler 參考程式碼 (分治優化 victor.gao)

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct dsu_data{
    int a,sz1,b,sz2;
    dsu_data(int _a,int _sz1,int _b,int _sz2):a(_a),sz1(_sz1),b(_b),sz2(_sz2){}
};
struct dsu{
    int boss[2*N],sz[2*N];
    stack<dsu_data>st;
    void init(int n){
        for (int i=0;i<=n+2;i++){
            boss[i]=i; sz[i]=1;
        }
        while (!st.empty()) st.pop();
    }
    int find(int x){
        if (boss[x]==x) return x;
        return find(boss[x]);
    }
    void Merge(int a,int b){
        int u=find(a),v=find(b);
        st.push(dsu_data(u,sz[u],v,sz[v]));
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        boss[v]=u;
        sz[u]+=sz[v];
    }
    void rollback(){
        if (st.empty()) return;
        dsu_data np=st.top(); st.pop();
        if (np.a==np.b) return;
        boss[np.a]=np.a;
        sz[np.a]=np.sz1;
        boss[np.b]=np.b;
        sz[np.b]=np.sz2;
    }
    void undo(int t){
        while (st.size()>t)
            rollback();
    }
}dsu;
int n,m,x,is[2*N],dp[2*N],ans=-1,pos;
pii edge[2*N];
// qr+1 ~ l-1 is inside
inline bool check(){
    return dsu.find(x)==dsu.find(1);
}
void Merge(int l,int r,int ql,int qr){
    if (l>r||ql>qr) return;
    int mid=(l+r)>>1,init_sz=dsu.st.size();
    for (int i=mid;i>=l&&i>qr;i--){
        dsu.Merge(edge[i].x,edge[i].y);
    }
    for (int i=min(qr,mid);i>=ql;i--){
        dsu.Merge(edge[i].x,edge[i].y);
        if (check()){
            dp[mid]=i;
            break;
        }
    }
    dsu.undo(init_sz);
    for (int i=min(l-1,qr);i>dp[mid];i--)
        dsu.Merge(edge[i].x,edge[i].y);
    Merge(l,mid-1,ql,dp[mid]);
    dsu.undo(init_sz);
    for (int i=mid;i>=max(l,qr+1);i--)
        dsu.Merge(edge[i].x,edge[i].y);
    Merge(mid+1,r,max(dp[mid],ql),qr);
    dsu.undo(init_sz);
}
void change_ans(int l,int r){
    if (l>r||(l>m&&r>m)||!l) return;
    if (r>m){
        swap(l,r);
        l-=m; l++; r--;
    }
    else {
        if (l-1>=m-r) r=l-1,l=1; 
        else l=r+1,r=m;
    }
    if (ans<r-l+1){
        ans=r-l+1;
        pos=l;
    }
    else if (ans==r-l+1)
        pos=min(pos,l);
}
int main(){
    fast
    cin>>n>>m>>x;
    for (int i=1;i<=m;i++){
        cin>>edge[i].x>>edge[i].y>>is[i];
        edge[i+m]=edge[i];
        is[i+m]=is[i];
    }
    if (x==1){
        cout<<m<<' '<<1<<' '<<m<<" "<<1<<'\n';
        return 0;
    }
    dsu.init(2*n);
    int col=-1;
    for (int i=1;i<=m;i++){
        if (is[i]==1){
            dsu.Merge(edge[i].x,edge[i].y);
            dsu.Merge(edge[i].x+n,edge[i].y+n);
        }
        else {
            dsu.Merge(edge[i].x,edge[i].y+n);
            dsu.Merge(edge[i].y,edge[i].x+n);
        }
    }
    if (dsu.find(1)==dsu.find(x)) col=1;
    else if (dsu.find(1)==dsu.find(x+n)) col=2;
    if (col==-1) cout<<-1<<'\n';
    else {
        dsu.init(n);
        Merge(1,2*m,1,2*m);
        for (int i=1;i<=2*m;i++){
            change_ans(dp[i],i);
        }
        if (ans==0) cout<<0<<" "<<0<<" "<<0<<" "<<col<<'\n';
        else cout<<ans<<' '<<pos<<" "<<pos+ans-1<<" "<<col<<'\n';
    }
    return 0;
}

:::

### 滿分解（三）Link Cut Tree by victor.gao
::: info
其實我根本不會 Link Cut Tree 我是抄中國人寫好的東西
如果有問題請不要怪我
:::
藉由上面的想法，我們需要找一段最小區間使得 $1$ ,$x$ 連通
假設現在為每個邊設邊權為他的 id，每次加 $i$ 第條邊後
這時刻的答案就會是 $i -$ $path(1,x)$ 上的邊權最小值
那現在加一條邊 $u,v$
- $u,v$ 不連通，就直接連起來
- $u,v$ 已經連通，把 $path(u,v)$ 上邊權最小的邊拔掉，然後加入 $u,v$

大致作法是把每條邊都變成一個點去做 Link Cut Tree
同時維護好最小值的邊

[詳細作法可自己看 oi-wiki
因為我根本不懂 Link Cut Tree 的運作](https://oi-wiki.org/ds/lct/#%E7%BB%B4%E6%8A%A4%E8%BE%B9%E6%9D%83)

複雜度應該是總共會有 $2k+n$ 個點加邊 $2k$ 次 $\mathcal{O}(2k \log (2k+n))$
總複雜度 $\mathcal{O}(k \log (k+n))$

實際跑起來分治優化 + dsu 兩個 log 更快
在洛谷那題我兩個 log 排全部 rk4

:::spoiler 參考程式碼 (Link Cut Tree 是抄洛谷上某個寫題解的人的)

#include<bits/stdc++.h>
using namespace std;
#define ls(x) Tree[x].son[0]
#define rs(x) Tree[x].son[1]
#define fa(x) Tree[x].fa
typedef long long LL;
const int maxn = 600010;
struct node{
    int son[2], Min, id, fa, lazy;
}Tree[maxn];
int n, m, w[maxn], num, Min;
bool vis[maxn];
struct Node{
    int u, v, w;
}a[maxn];
inline bool IsRoot(int x) { return (ls(fa(x)) == x || rs(fa(x)) == x) ? false : true; }
inline void PushUp(int x){
    Tree[x].Min = w[x]; Tree[x].id = x;
    if ( ls(x) && Tree[ls(x)].Min < Tree[x].Min ) { Tree[x].Min = Tree[ls(x)].Min; Tree[x].id = Tree[ls(x)].id; }
    if ( rs(x) && Tree[rs(x)].Min < Tree[x].Min ) { Tree[x].Min = Tree[rs(x)].Min; Tree[x].id = Tree[rs(x)].id; }
}
inline void Update(int x) { Tree[x].lazy ^= 1; swap(ls(x), rs(x)); }
inline void PushDown(int x){
    if ( !Tree[x].lazy ) return ;
    if ( ls(x) ) Update(ls(x));
    if ( rs(x) ) Update(rs(x));
    Tree[x].lazy = 0;
}
inline void Rotate(int x){
    int y = fa(x), z = fa(y), k = rs(y) == x, w = Tree[x].son[!k];
    if ( !IsRoot(y) ) Tree[z].son[rs(z) == y] = x;
    fa(x) = z; fa(y) = x; if ( w ) fa(w) = y;
    Tree[x].son[!k] = y; Tree[y].son[k] = w;
    PushUp(y);
}
inline void Splay(int x){
    stack<int> Stack; int y = x, z; Stack.push(y);
    while ( !IsRoot(y) ) Stack.push(y = fa(y));
    while ( !Stack.empty() ) { PushDown(Stack.top()); Stack.pop(); }
    while ( !IsRoot(x) ) 
    {
        y = fa(x); z = fa(y);
        if ( !IsRoot(y) ) Rotate((ls(y) == x) ^ (ls(z) == y) ? x : y);
        Rotate(x);
    }
    PushUp(x);
}
inline void Access(int root) { for ( int x = 0; root; x = root, root = fa(root) ) { Splay(root); rs(root) = x; PushUp(root); } }
inline void MakeRoot(int x) { Access(x); Splay(x); Update(x); }
inline int FindRoot(int x) { Access(x); Splay(x); while ( ls(x) ) x = ls(x); Splay(x); return x; }
inline void Link(int u, int v) { MakeRoot(u); if ( FindRoot(v) != u ) fa(u) = v; }
inline void Cut(int u, int v) { MakeRoot(u); if ( FindRoot(v) != u || fa(v) != u || ls(v) ) return ; fa(v) = rs(u) = 0; }
inline void Split(int u, int v) { MakeRoot(u); Access(v); Splay(v); }
inline bool Check(int u, int v) { MakeRoot(u); return FindRoot(v) == u; }
struct DSU{
    int f[maxn];
    void init(int n){for(int i=1;i<=n;i++)f[i]=i;}
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
    void merge(int x,int y){x=find(x),y=find(y);f[x]=y;}
}dsu;
int start=1e9,ans=-1,pos,tmp=1;
void change_ans(int l,int r){
    if (l>r||(l>m&&r>m)||!l) return;
    if (r>m){
        swap(l,r);
        l-=m; l++; r--;
    }
    else {
        if (l-1>=m-r) r=l-1,l=1; 
        else l=r+1,r=m;
    }
    if (ans<r-l+1){
        ans=r-l+1;
        start=l;
    }
    else if (ans==r-l+1)
        start=min(start,l);
}
int main(){
    cin>>n>>m>>pos;
    dsu.init(2*n);
    for (int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        if (a[i].w==1){
            dsu.merge(a[i].u,a[i].v);
            dsu.merge(a[i].u+n,a[i].v+n);
        }
        else {
            dsu.merge(a[i].u,a[i].v+n);
            dsu.merge(a[i].u+n,a[i].v);
        }
        a[i].w=i; a[i+m]=a[i]; a[i+m].w=i+m;
    }
    if (dsu.find(1)==dsu.find(pos)) tmp=1;
    else tmp=2;
    for (int i=1;i<=n;i++)
        w[i] = 0x3f3f3f3f;
    for (int i=n+1;i<=n+2*m;i++)
        w[i] = a[i - n].w;
    if (pos==1){
        cout<<m<<" "<<1<<" "<<m<<" "<<1<<'\n';
        return 0;
    }
    for (int i=1;i<=2*m;i++){
        if (a[i].u == a[i].v) continue;
        if (!Check(a[i].u,a[i].v)) 
        {
            Link(a[i].u,i+n); 
            Link(i+n,a[i].v);
            ++ num; vis[i] = true;
        }
        else
        {
            Split(a[i].u,a[i].v);
            int x=Tree[a[i].v].id; Splay(x); fa(ls(x))=fa(rs(x))=0;
            vis[x-n]=false;
            Link(a[i].u,i+n); Link(i+n,a[i].v);
            vis[i]=true;
        }
        if (Check(1,pos)){
            Split(1,pos);
            int val=Tree[pos].Min;
            change_ans(val,i);
        }
    }
    if (ans==-1) cout<<ans<<'\n';
    else if (ans==0) cout<<ans<<' '<<0<<' '<<0<<" "<<tmp<<'\n';
    else cout<<ans<<" "<<start<<" "<<start+ans-1<<" "<<tmp<<'\n';
    return 0;
}

:::

## E. 罰款金額

###### tags: math, data structure, offline algorithm

###### author: ColtenOuO, official solution: sam571128, 難度定位: Hard

### 子任務 2: $Q \le 10$

對於每個詢問，直接暴力跑過整個區間 $[l,r]$ 即可

複雜度: $\mathcal{O}(nQ)$

### 子任務 3: $k = 1$

由於 $a_i \ge 1$，因此，其實所有人只有兩種情況

1. $a_i = 1 = k$，沒有裝強也沒有裝弱
2. $a_i > 1 = k$，裝強

那我們要怎麼知道所有裝強的人的答案總和呢？

很簡單，既然 $a_i > k$，那麼 $|a_i - k| = a_i - k$！

因此，只要找到這些 $a_i$ 的總和減去數量乘以 $k$，就是答案了

可以簡單的使用兩個前綴和預處理完

複雜度：$O(n + Q)$

### 子任務 4: $n \le 1000, k \le 10$

我們可以預處理好 $k=1 \sim 10$ 的時候，每個區間 $[l,r]$ 的答案

接下來每一次詢問的時候，直接去查表即可！

複雜度：$\mathcal{O}(n^2k + Q)$

### 滿分解（一）離線 By ColtenOuO

注意到這題其實可以離線做

我們考慮將陣列中的每個數字和詢問由小到大去處理

每次遇到一個詢問，必須要去找一個區間內 $< k$ 和 $> k$ 的數字總和與數量

因此，要做到這一點，我們需要一個可以處理「單點修改」、「區間詢問」的資料結構

而這件事情，可以使用 BIT 或者線段樹來處理

細節：$a_i = k$ 的沒有裝弱也沒有裝強，必須要好好處理這部份

可能有點幫助的小觀察：對於兩個數字 $x,y$，$|x-y| + |x+y| = 2\max(x,y)$

複雜度：$\mathcal{O}(Q\log n)$

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

const int N = 2e5+5;
vector<pair<pair<int,int>,int>> ask[N];
vector<int> pos[N];
pair<int,int> bit[N];
int arr[N], cnt[N], ans[N];

pair<int,int> operator + (pair<int,int> a, pair<int,int> b){
    return {a.first + b.first, a.second + b.second};
}

void operator += (pair<int,int> &a, pair<int,int> b){
    a = a + b;
}

void update(int pos, pair<int,int> val){
    while(pos < N){
        bit[pos] += val;
        pos += pos&-pos;
    }
}

pair<int,int> query(int pos){
    pair<int,int> res = {0,0};
    while(pos){
        res += bit[pos];
        pos -= pos&-pos;
    }
    return res;
}


signed main(){
    fastio
    int n,q;
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        cnt[arr[i]]++;
        pos[arr[i]].push_back(i);
        update(i,{arr[i],1});
    }

    for(int i = 1; i <= q; i++){
        int l,r,k;
        cin >> l >> r >> k;
        ask[k].push_back({{l,r},i});
    }

    for(int i = 1; i < N; i++){
        for(auto [p,id] : ask[i]){
            auto [l,r] = p;
            auto [a,b] = query(r);
            auto [c,d] = query(l-1);
            int num = (r-l+1) - (b-d) - (upper_bound(pos[i].begin(),pos[i].end(),r) - lower_bound(pos[i].begin(),pos[i].end(),l));
            int val = a-c;

            ans[id] =  val*2 + (num)*i*2;
        }
        for(auto x : pos[i]){
            update(x,{-i,-1});
        }
    }

    for(int i = 1; i <= q; i++){
        cout << ans[i] << "\n";
    }
}  

:::

### 滿分解（二）莫隊+值域分塊 By Penguin07

對於所有的詢問，我們用莫隊的方式將他們排好

接著，我們將數字對值域進行分塊，每一塊儲存的是那塊的總和和數字數量

我們依序去處理每一個區間的答案

當我們要跑到 $k$ 的時候，暴力處理 $k$ 所在的塊，然後剩下的用塊的答案去處理

複雜度：$\mathcal{O}(Q\sqrt{n})$

::: spoiler 參考程式碼 (Penguin07)

#include <bits/stdc++.h>
using namespace std;

const int N = (int) 2e5 + 5;
const int B = 550;

struct Block {
	int L, R;
	long long all = 0;
	int all_cnt = 0;
	long long sum[B] = {};
	int cnt[B] = {};

	void add(int x) {
		all += x;
		all_cnt += 1;
		sum[x - L] += x;
		cnt[x - L] += 1;
	}

	void remove(int x) {
		all -= x;
		all_cnt -= 1;
		sum[x - L] -= x;
		cnt[x - L] -= 1;
	}

	pair<long long, int> get(int ql, int qr) {
		ql = max(ql, L);
		qr = min(qr, R);
		if(ql == L && qr == R) {
			return {all, all_cnt};
		}
		long long ans = 0;
		int ans_cnt = 0;
		for(int i = ql; i < qr; i++) {
			ans += sum[i - L];
			ans_cnt += cnt[i - L];
		}
		return {ans, ans_cnt};
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<long long> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<long long> pref(n + 1);
	for(int i = 0; i < n; i++) {
		pref[i + 1] = pref[i] + a[i];
	}
	vector<array<int, 4>> queries(q);
	for(int i = 0; i < q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		--l;
		queries[i] = {l, r, k, i};
	}
	sort(queries.begin(), queries.end(), [](const auto& a, const auto& b) {
		if(a[0] / B == b[0] / B) {
			return a[0] / B & 1 ? a[1] > b[1] : a[1] < b[1];
		}
		return a[0] < b[0];
	});
	const int BLOCK_CNT = (N + B - 1) / B;
	vector<Block> block(BLOCK_CNT);
	for(int i = 0; i < BLOCK_CNT; i++) {
		block[i].L = i * B;
		block[i].R = (i + 1) * B;
	}
	auto Add = [&](int x) {
		block[x / B].add(x);
	};
	auto Remove = [&](int x) {
		block[x / B].remove(x);
	};
	auto Get = [&](int l, int r) {
		long long sum = 0, cnt = 0;
		for(int i = 0; i < BLOCK_CNT; i++) {
			auto [x, y] = block[i].get(l, r + 1);
			sum += x;
			cnt += y;
		}
		return pair<long long, long long>{sum, cnt};
	};
	vector<long long> ans(q);
	int L = 0, R = 0;
	for(auto e : queries) {
		int ql = e[0], qr = e[1], k = e[2], id = e[3];
		while(L > ql) {
			L -= 1;
			Add(a[L]);
		}
		while(R < qr) {
			Add(a[R]);
			R += 1;
		}
		while(L < ql) {
			Remove(a[L]);
			L += 1;
		}
		while(R > qr) {
			R -= 1;
			Remove(a[R]);
		}
		auto lhs = Get(0, k - 1);
		auto rhs = Get(k + 1, N - 1);
		ans[id] = pref[R] - pref[L] - (R - L - lhs.second - rhs.second) * k + (lhs.second + rhs.second) * k;
		ans[id] += abs(lhs.first - lhs.second * k) + abs(rhs.first - rhs.second * k);
	}
	for(int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

:::

## F. 動物園

###### tags: math, number theory

###### author: sam571128, 難度定位: Easy

### 子任務 2: $x \le 10$

暴力 or 手算即可

### 子任務 3: $x \le 10^3$

從子任務 2 可以猜測其實答案並不會比 $x$ 大多少

因此，其實可以暴力跑過前 $2000$ 個數字等等的

不過，其實會發現當數字到了一定大小之後，數字的範圍會超出 long long！

在這個情況下，有兩種解決的方法
1. 使用可以做大數運算的語言，如 python 或 Java 的 BigInteger
2. 要知道一點點數論的概念
$$
\begin{align*}
(a + b) \bmod n &= ((a \bmod n) + (b \bmod n)) \bmod n \\
(a - b) \bmod n &= ((a \bmod n) - (b \bmod n)) \bmod n\\
(a \cdot b ) \bmod n &= (a \bmod n)(b \bmod n) \bmod n
\end{align*}
$$

在 $\mathcal{O}(x^2)$ 的時間建出這些數字的答案

接著直接輸出即可

### 主要想法

觀察到這題其實數字雖然是有規律的，但其實好像根本一點關係也沒有欸

或者沒想法，應該會發現其實 $NO$ 根本不可能發生！

一定都有一組解

其實如果有仔細想一下，會想到其實

$$「兩個數字相減被 \ x \ 整除」\iff 「兩個數字除以 \ x \ 的餘數相同」$$

然後，根據鴿籠原理，其實如果我們跑過 $x+1$ 個數字，由於除以 $x$ 的餘數只有 $x$ 種，因此一定會有其中一個出現 $2$ 次以上！

其實題目給的 $1,12,123$ 根本不重要，就算換成一些奇怪的數字都一樣找的到答案！

### 滿分解

對於每一次輸入的 $x$，暴力的跑過前 $x+1$ 個數字

開一個陣列或 map 存上一個出現過餘數是 $i$ 的數字

每一次要找下一個數字的時候，假設現在是 $k$，下一個數字是 $n$，那串接起來的數字會是

$$10^{\log_{10}n} k + n$$

由於這個數字到後來可能會很大，要記得每一次都要 $\text{mod } x$

複雜度：$\mathcal{O}(\sum x)$

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

int getLog(int x){
    int cnt = 0;
    while(x){
        cnt++;
        x/=10;
    }
    return cnt;
}

string getNum(int n){
    string s;
    for(int i = 1; i <= n; i++){
        s += to_string(i);
    }
    return s;
}

void solve(){
    int x;
    cin >> x;

    int has[x] = {};

    int now = 0;
    for(int i = 1; i <= x+1; i++){
        now = ((int)round(pow(10,getLog(i)))*now+i)%x;
        if(has[now]){
            cout << "YES\n";
            cout << getNum(has[now]) << " " << getNum(i) << "\n";
            break;
        }
        has[now] = i;
    }
}

signed main(){
    fastio	
    int t;
    cin >> t;
    while(t--) solve();
}

:::

### 賽中看到的另解

由於我們沒有說輸出的兩隻動物編號必須是相異的

輸出兩個相同的編號也會過 QQ

這不是預期的就是了

## G. 鬼鍵

###### tags: implementation

###### author: visitorCKW, 難度定位: Easy

模擬題，照著題目敘述模擬即可

::: spoiler 參考程式碼 (sam571128)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

signed main(){
    fastio	
    int n,m,k,q;
    cin >> n >> m >> k >> q;

    map<int, pair<int,int>> mp;
    map<pair<int,int>,int> has;

    for(int i = 1; i <= k; i++){
        int a,x,y;
        cin >> a >> x >> y;
        mp[a] = {x,y};
        has[{x,y}] = a;
    }

    while(q--){
        int x,y,z;
        cin >> x >> y >> z;
        set<int> st,st2;
        st.insert(mp[x].first);
        st.insert(mp[y].first);
        st.insert(mp[z].first);
        st2.insert(mp[x].second);
        st2.insert(mp[y].second);
        st2.insert(mp[z].second);;
        if(st.size() != 2 || st2.size() != 2){
            cout << "Not ghost key condition!\n";
            continue;
        }
   
        
        int r1 = *st.begin(), r2 = *st.rbegin();
        int c1 = *st2.begin(), c2 = *st2.rbegin();
            
        int cnt = 0;
        for(auto r : {r1,r2}){
            for(auto c : {c1,c2}){
                cnt += (has[{r,c}]==x || has[{r,c}] == y || has[{r,c}] == z);
            }
        }

        if(cnt==3){;
            for(auto r : {r1,r2}){
                for(auto c : {c1,c2}){
                    if(has[{r,c}] && has[{r,c}]!=x && has[{r,c}] != y && has[{r,c}] != z){
                        cout << "Find ghosy key: " << " " <<  has[{r,c}] << "\n";
                        goto nxt;
                    }
                }
            }
        }
        cout << "Not ghost key condition!\n";
        nxt:;
    }
}

:::

## H. 小業教授的冷泡茶

###### tags: dp, two pointers

###### author: ColtenOuO, 難度定位: Medium

### 子任務 2: 所有區塊的茶葉重量一樣

可以計算出一個機器人最多可以採收到多少區塊

假設這個數字是 $x$，那麼答案就會是 $\min(na_i, x \cdot m \cdot a_i)$

複雜度：$O(n)$

### 子任務 3: $m = 1$

只有一個機器人的話，那我們可以用「雙指針」來計算出最大的解！

固定 $l$，我們可以知道從他開始，往右最遠可以延伸到哪裡

接著就取總和最大的區間即可

複雜度：$O(n)$

### 子任務 4: $n = 1000$

考慮 $dp$，我們可以列出以下的狀態

$$令 \ dp[i][j] \ 為前 \ i \ 個區塊，總共有\ j \ 個機器人所能採收到的最大總和是多少$$

那麼，我們可以很輕易的列出這樣的轉移式

$$dp[i][j] = \max\begin{cases}
dp[i-1][j] \\
dp[l][j-1] + \text{sum}(l+1,i) &, \text{if }\text{sum}(l+1,i) \le k
\end{cases}$$

可以在 $O(n^2m)$ 的時間做完（時間卡的有點緊）

如果沒滾動的話，滿分解也只會拿到這筆

### 滿分解

將子任務 3 和 4 的作法結合！

對於每一個位置 $i$，我們往前維護他最前面從哪裡開始，機器人都可以拿完區間 $[l,i]$ 的茶葉，這個可以在 $O(n)$ 的時間做完，設這個值為 $left[i]$

接著，我們一樣考慮使用 $dp$，想法與子任務 4 差不多，不過轉移必須要變快！

發現到上一題的轉移式，第二個條件其實在我們知道最左邊可以延伸到哪之後，其實可以改成
$$dp[i][j] = \max\begin{cases}
dp[i-1][j] \\
dp[x][j-1] + \text{sum}(left[i],i) &, \text{if }\text{sum}(l+1,i) \le k, \ x \le left[i]-1
\end{cases}$$

因此，只要對 $dp$ 維護好前綴 $\max$，轉移就可以在 $\mathcal{O}(1)$ 的時間完成！（由於 $nm$ 很大，要滾動）

複雜度： $\mathcal{O}(nm)$

::: spoiler 參考程式碼 (ColtenOuO)

#include <bits/stdc++.h>

#define int long long

using namespace std;

int dp[2][200005],a[200005],tmp[200005],c[200005];

signed main(void)
{
	int n,m,k2;
	cin >> n >> m >> k2;
	
	for(int i=1;i<=n;i++) cin >> a[i] , c[i] = c[i-1] + a[i];

	int l = 1 , r = 1 , total = 0;
	
	while( r <= n )
	{
		total += a[r];
		while( total > k2 ) total -= a[l] , l++;
		if( total == 0 ) tmp[r] = -1;
		else tmp[r] = l;
		
		r++;
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int k=1;k<=n;k++)
		{
			if( tmp[k] != -1 ) dp[i%2][k] = max({dp[(i+1)%2][k],dp[i%2][k-1],dp[(i+1)%2][tmp[k]-1]+c[k]-c[tmp[k]-1]});
			else dp[i%2][k] = max(dp[i%2][k-1],dp[(i+1)%2][k]);
		}
		
		for(int k=1;k<=n;k++) dp[(i+1)%2][k] = 0;
	}
	
	cout << dp[m%2][n] << "\n";
}

:::

### Bonus

本題有使用 Aliens Trick 的 $\mathcal{O}(n \log C)$ 的作法

詳細作法可以去參考 [APCS 2021/09 D.美食博覽會](https://zerojudge.tw/ShowProblem?problemid=g278) 的相關題解