题解：CF1997E Level Up

Aurora5090 · 2024-07-31 01:36:56 · 题解

CF 传送门

提供一个 O(q + n \sqrt n) 时间，O(n) 空间的解法。

容易想到根号分治，我们先离线询问，按询问的 k 排序。

根据套路，枚举 k \lt \sqrt n 的部分，每次扫一遍序列，
预处理出每个 a_i 是否被使用，暴力回答对应的询问。
这部分时间是 O(n \sqrt n)，离线后空间可以做到 O(n)。

随后解决 k \ge \sqrt n 的部分：
在这部分，我们的等级最多只有 \sqrt n，所以可以找出每个等级区间的范围,
第一直觉的做法可能是会带个 \log 的，我们每次从序列的最左边开始二分，
可以找到等级 1 的右端点，以此类推，重复 \sqrt n 次就可以找到所有的端点，
然后回答询问，如果这个端点在等级 L 的区间里，答案即为 [a_i \ge L]。
这样的话是 O(n \sqrt n \log n)，但是有洁癖？！

其实稍微改一下就可以做到严格 O(n \sqrt n)。
依赖一个观察：随着我们 k 的不断增大，每个等级区间的端点只会单调右移。
证明比较简单，考虑等级 1 的区间不会左移，那么等级 2 的区间也不会左移......
实际上就是 O(\sqrt n) 个区间指针在不断右移，直到满足 k 的限制，
在移动过程中，暴力维护 a_i 有没有被使用，被谁使用，每个等级区间使用了多少个 a。

每次可以 O(1) 回答，就做到 O(q + n \sqrt n) 时间，O(n) 空间了。

挪指针的时候访存比较垃圾，好像 B = 1000 跑的比较快，这样最多有 200 个指针，421 ms。

代码

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

struct node
{
    int pos, k, id;
    inline bool operator<(const node &n) const
    {
        return k < n.k;
    }
};

const int maxn = 2e5 + 5, B = 1000;
int n, q;
int a[maxn], ans[maxn];
node ask[maxn];
int col[maxn];
int ptr[205], val[205], bel[maxn];

void build(int qk)
{
    int level = 1, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += (a[i] >= level);
        col[i] = (a[i] >= level);
        if (cnt >= qk)
            level++, cnt = 0;
    }
}

void init()
{
    int level = 1, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int v = a[i] >= level;
        cnt += v;
        val[level] += v;
        col[i] = v;
        bel[i] = level;
        if (cnt >= B)
            ptr[level] = i, level++, cnt = 0;
    }
    ptr[level] = n;
}

void solve(int qk)
{
    for (int id = 1; id <= 200; id++)
    {
        if (ptr[id] == 0 || ptr[id] >= n)
            break;
        if (ptr[id] < ptr[id - 1])
            ptr[id] = ptr[id - 1], val[id] = 0;
        while (val[id] < qk && ptr[id] < n)
        {
            int i = ++ptr[id];
            if (a[i] >= id)
            {
                val[id]++;
                if (col[i] == 1)
                    val[bel[i]]--;
                bel[i] = id;
                col[i] = 1;
            }
            else
            {
                bel[i] = 0;
                col[i] = 0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= q; i++)
    {
        cin >> ask[i].pos >> ask[i].k;
        ask[i].id = i;
    }

    sort(ask + 1, ask + 1 + q);

    int pre = 0;
    int flag = true;
    for (int i = 1; i <= q; i++)
    {
        auto [qpos, qk, qid] = ask[i];

        if (qk <= B)
        {
            if (pre != qk)
                build(qk);
        }
        else
        {
            if (flag == true)
                init(), flag = false;
            if (pre != qk)
                solve(qk);
        }
        ans[qid] = col[qpos];
        pre = qk;
    }

    for (int i = 1; i <= q; i++)
        cout << (ans[i] == 0 ? "NO\n" : "YES\n");

    // cout.flush();
    // system("Pause");
    return 0;
}