题解：CF1997E Level Up

· · 题解

题目翻译

打怪操作是指，顺次对于 [1,n] 的每个怪，每个怪有 a_i 的等级，如果你的等级 lv 严格大于怪的等级 a_i，它就会逃跑。反之你会和它战斗。

你每与 k 个怪战斗就会升一级，即 lv\gets lv+1。

现在有若干组查询，每次查询 i,x 表示询问 k=x 时，你是否会和第 i 个怪战斗。

1\leq n,q\leq 2\times 10^5$，$1\leq a_i\leq 2\times 10^5$，$1\leq i,x\leq n

题目思路

首先考虑一个 \log^3 的最暴力做法，然后在这上面优化。

由于每打 k 个怪就会升级，所以你最多会升 \lfloor\frac{n}{k}\rfloor 次。而 \sum\limits_{k=1}^{n} \frac nk \approx n \log n。也就是对于所有的 k=x 我们只会有 \mathcal O(n \log n ) 次升级。

对于每一组 k=x，我们可以找到若干升级段，也就是 [l,r] 满足击杀了第 l 到第 r 只怪会正好升级。

因为最多升级 \mathcal O(n\log n) 次，因此每次升级二分右端点，接下来处理怎么判定 [l,r] 是可以恰好升级的段。我们需要判断 [l,r] 是否满足 \sum\limits_{i=l}^r [a_i\geq lv] \geq k，其中的 [] 为艾弗森括号，取值为 [x]=\begin{cases}1&x\ \text{is True}\\0& \text{Otherwise}\end{cases}。

那么我们可以使用主席树等数据结构求解。详见 牛客小白月赛 9 E. 换个角度思考 或 HDU 4417 Super Mario。

这样就得到了一个没有什么思维含量的 \mathcal O(n\log^3 n) 的做法。

调和级数一共 \mathcal O(n\log n) 种区间，二分一只 \log，这两个都无法优化了，我们尝试在计算 \sum\limits_{i=l}^r [a_i\geq lv] \geq k 上做文章。

由于随着 k 的上升，那么相对升级就会变慢，等级高的怪我们不需要考虑。准确的说只有 a_i\leq \frac n k 的怪才有可能给我们升级带来影响。

然而如果我们 a_i 都很小的话，我们可以通过预处理前缀和计算 \sum\limits_{i=l}^r [a_i\geq lv] \geq k。我们设 sum_{i,j} 表示前 i 个数中，怪物等级 \leq j 的怪物个数。那么 \sum\limits_{i=l}^r [a_i\geq lv] 就等价于 (r-l+1)-(sum_{r,lv-1}-sum_{l-1,lv-1})。这样就可以把这个一个 \log 优化掉。

这个预处理是 \mathcal O(\frac{n^2}{B}) 的。这样我们就处理了 k\gt B 的情况。

如果 k\leq B，那么我们直接做 \mathcal O(Bn) 的暴力就行。

把两个做法结合一下，取 B=\sqrt n，那么两种算法的复杂度分别是：

这样我们就在 \mathcal O(n\sqrt n+n\log^2 n) 的时间中做完了这个问题。

因此，简单说一下过程，就是预处理 sum_{i,j} 表示前 i 个等级 \leq j 的怪兽个数，离线询问，对于 k\leq B 的暴力扫一遍序列模拟，对于 k\gt B 的二分区间端点，通过预处理的 sum 数组判断是否合法。

完整代码

CF submission 273823527

#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
const int B = 448;
int n, Q;
int a[200020];
vector<array<int, 2>> q[200020];
bool ans[200020];
int sum[450][200020];
bool skip[200020];
int level[200020];
int main()
{
    read(n, Q);
    for (int i = 1; i <= n; i++)
    {
        read(a[i]);
        if (a[i] <= B)
            sum[a[i]][i]++;
    }
    for (int j = 1; j <= B; j++)
    {
        for (int i = 1; i <= n; i++)
            sum[j][i] += sum[j - 1][i] + sum[j][i - 1] - sum[j - 1][i - 1];
    }
    for (int i = 1; i <= Q; i++)
    {
        int p, k;
        read(p, k);
        q[k].push_back({p, i});
    }
    for (int k = 1; k <= n; k++)
    {
        if (q[k].empty())
            continue;
        if (k <= B)
        {
            int lvl = 1;
            int cnt = 0;
            for (int i = 1; i <= n; i++)
            {
                skip[i] = 0;
                if (a[i] < lvl)
                {
                    skip[i] = 1;
                    continue;
                }
                cnt++;
                if (cnt == k)
                    cnt = 0, lvl++;
            }
            for (auto [p, i] : q[k])
            {
                if (!skip[p])
                    ans[i] = 1;
            }
        }
        else
        {
            sort(q[k].begin(), q[k].end());
            int l = 1, r = 0, lvl = 1;
            int j = 0;
            auto check = [&](int r)
            { return (r - l + 1) - (sum[lvl - 1][r] - sum[lvl - 1][l - 1]) >= k; };
            while (l <= n)
            {
                int L = l, R = n, r = n;
                while (L <= R)
                {
                    int mid = L + R >> 1;
                    if (check(mid))
                        R = (r = mid) - 1;
                    else
                        L = mid + 1;
                }
                while (j < q[k].size() && l <= q[k][j][0] && q[k][j][0] <= r)
                    level[q[k][j][0]] = lvl, j++;
                l = r + 1;
                lvl++;
            }
            for (auto [p, i] : q[k])
            {
                if (level[p] <= a[p])
                    ans[i] = 1;
            }
        }
    }
    for (int i = 1; i <= Q; i++)
        puts(ans[i] ? "YES" : "NO");
    return 0;
}