[CF547B] Mike and Feet

[CF547B] Mike and Feet

Description

n 个值代表 n 个熊的高度，对于 size 为 x 的连续子段 group，strength 值为这个 group 中熊的最小的 height 值，对于 x (1<=x<=n) 求出最大的 strength 值。

Solution

并查集

将所有元素降序加入，第 i 个元素被加入后，我们将 i-1 和 i 所在的树合并

记录整个森林中最大的树的大小，假设为 mx，那么所有 (le mx) 的询问答案都和 mx 取 max

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

#define int long long
const int N = 1000005;

int fa[N], n, a[N], siz[N], ans[N];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int merge(int p, int q)
{
    p = find(p);
    q = find(q);
    fa[p] = q;
    siz[q] += siz[p];
    return siz[q];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
    {
        if (mp.find(-a[i]) == mp.end())
            mp[-a[i]] = vector<int>();
        mp[-a[i]].push_back(i);
    }

    for (int i = 0; i <= n; i++)
        fa[i] = i, siz[i] = 1;

    int mx = 1;
    for (auto& [val, vec] : mp)
    {
        int new_mx = mx;
        for (auto x : vec)
            new_mx = max(new_mx, merge(x - 1, x));
        if (new_mx != mx)
        {
            for (int i = mx; i < new_mx; i++)
                ans[i] = -val;
        }
        mx = new_mx;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
}