题解：CF2101C 23 Kingdom

我们注意到对于一种数，仅有最左侧的和最右侧的有贡献，故考虑选择

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：

CPP

#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;
}

题解：CF2101C 23 Kingdom

文章操作

相关推荐

评论

题解：CF2101C 23 Kingdom