题目翻译
打怪操作是指，顺次对于 $[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$，那么两种算法的复杂度分别是：
-
$k\leq B$
暴力 $\mathcal O(n\sqrt n)$。
-
$k\gt B$
预处理 $\mathcal O(n\sqrt n)$。
做查询 $\mathcal O(n\log^2 n)$。
这样我们就在 $\mathcal O(n\sqrt n+n\log^2 n)$ 的时间中做完了这个问题。
因此，简单说一下过程，就是预处理 $sum_{i,j}$ 表示前 $i$ 个等级 $\leq j$ 的怪兽个数，离线询问，对于 $k\leq B$ 的暴力扫一遍序列模拟，对于 $k\gt B$ 的二分区间端点，通过预处理的 $sum$ 数组判断是否合法。
完整代码
#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;
}