题解：AT_arc098_c [ARC098E] Range Minimum Queries

· · 题解

枚举被删除数的最小值 Y，那么值比 Y 要小的数全都不能选。

此时得到若干个连续段，那么一个连续段可以继续被选的充要条件是该连续段内元素数量 \ge K，因此判断是否合法是容易的。而因为希望让 X 的值尽量的小，所以只需要让每个连续段中删除的元素的值尽量小即可。

直接模拟上述流程可做到时间复杂度 O(n^2\log n)，还可以改成桶排做到严格 O(n^2)。

namespace Loyalty
{
    int 追忆[N], 我常常[N], 我该在哪里[N], 带着回忆向前[N], 瞭望过去的自己[N];
    inline void init() {}
    inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
    {
        int box, sale, recall;
        cin >> box >> sale >> recall;
        for (int 停留 = 1; 停留 <= box; ++停留)
            cin >> 追忆[停留], 我常常[停留] = 追忆[停留];
        sort(我常常 + 1, 我常常 + box + 1);
        int 恰到好处的朦胧 = infll;
        for (int 停留 = 1; 停留 <= box; ++停留)
        {
            int 过去 = 追忆[停留];
            for (int 我问我自己 = 1; 我问我自己 <= box; ++我问我自己)
                我该在哪里[我问我自己] = 0;
            for (int 我问我自己 = 1; 我问我自己 <= box; ++我问我自己)
                if (追忆[我问我自己] < 过去)
                    我该在哪里[我问我自己] = 1;
            vector<pair<int, int>> 曾经的日子;
            int 过客 = 1;
            for (int 我问我自己 = 1; 我问我自己 <= box; ++我问我自己)
                if (我该在哪里[我问我自己])
                {
                    if (过客 != 我问我自己)
                        曾经的日子.emplace_back(过客, 我问我自己 - 1);
                    过客 = 我问我自己 + 1;
                }
            if (过客 <= box)
                曾经的日子.emplace_back(过客, box);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 宛如入梦;
            for (auto &[积云厚重, 卷云缥缈] : 曾经的日子)
            {
                int 定格在脑海 = 卷云缥缈 - 积云厚重 + 1;
                for (int 我问我自己 = 积云厚重; 我问我自己 <= 卷云缥缈; ++我问我自己)
                    带着回忆向前[我问我自己] = 追忆[我问我自己], 
                    瞭望过去的自己[我问我自己] = 卷云缥缈;
                sort(带着回忆向前 + 积云厚重, 带着回忆向前 + 卷云缥缈 + 1);
                if (定格在脑海 >= sale)
                    宛如入梦.emplace(带着回忆向前[积云厚重], 积云厚重);
            }
            int 曲终人散 = 1, 岁月的朦胧 = -infll;
            for (int 我问我自己 = 0; 我问我自己 < recall; ++我问我自己)
            {
                if (宛如入梦.empty())
                {
                    曲终人散 = 0;
                    break;
                }
                auto [薄雾间的山水, 面纱下的女子] = 宛如入梦.top();
                宛如入梦.pop();
                岁月的朦胧 = max(岁月的朦胧, 薄雾间的山水);
                if (瞭望过去的自己[面纱下的女子] - 面纱下的女子 >= sale)
                    宛如入梦.emplace(带着回忆向前[面纱下的女子 + 1], 面纱下的女子 + 1);
            }
            if (曲终人散)
                恰到好处的朦胧 = min(恰到好处的朦胧, 岁月的朦胧 - 过去);
        }
        cout << 恰到好处的朦胧 << '\n';
    }
}