题解：CF2101C 23 Kingdom

Claire0918 · 2025-09-06 16:02:52 · 题解

我们注意到对于一种数，仅有最左侧的和最右侧的有贡献，故考虑选择 k 对位置 \{l_i, r_i\} 分别填入 k 种数。因为填的数越小一定不劣，所以显然填 [1, k]。

答案为 \sum(r_i - l_i) = \sum r_i - \sum l_i，也就是选取尽量小的 k 个位置作为 l_i，尽量大的 k 个位置作为 r_i。选取时从某一侧枚举 i，填入当前最大的未填入的 x \leq a_i 填入 i 直到 [1, k] 都已经填入，小于等于 a_i 的最大未填入数字可以使用并查集维护，填入 x 时将其合并到 x - 1 上。

如何选取 k 答案最大呢？令 L = \max\{l_i\}, R = \min\{r_i\}，我们注意到如果 L > R，那么我们调整 k \gets k - 1 时，L 和 R 的贡献消失，答案将会减少 R - L < 0，所以调整更优；若 L \leq R，调整就不优。于是最优的 k 是能使得 L \leq R 的最大值，二分得到这个 k 并计算 k 时的下标和即可。

时间复杂度 \mathcal{O}(n\log n\alpha (n))。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int t, n;
int a[maxn];

namespace DSU{
    int fa[maxn];
    inline int getf(int x){
        return fa[x] == x ? x : fa[x] = getf(fa[x]);
    }
}

using namespace DSU;

inline pair<int, long long> calc(int x, bool op){
    iota(fa, fa + x + 1, 0);
    long long sum = 0;
    for (int i = op ? 1 : n; op ? i <= n : i; op ? i++ : i--){
        const int v = min(a[i], x), p = getf(v);
        p && (fa[p] = p - 1, sum += i);
        if (!getf(x)){
            return make_pair(i, sum);
        }
    }
    return make_pair(-1, -1);
}

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        int l = 0, r = n;
        while (l < r){
            const int mid = l + r + 1 >> 1, v1 = calc(mid, true).first, v2 = calc(mid, false).first;
            if (~v1 && ~v2 && v1 < v2){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        printf("%lld\n", calc(l, false).second - calc(l, true).second);
    }

return 0;
}