题意简述

有 $n$ 只怪兽按顺序排列，第 $i$ 只怪兽的等级为 $a_i$。
Monocarp 初始等级为 $0$，他需要依次面对这些怪兽。
存在一个参数 $k$，Monocarp 每击败一只怪兽，等级就会增加 $1$。
对于第 $i$ 只怪兽，如果在他到达之前 Monocarp 的等级已经 $\ge a_i$，则怪兽会逃跑（不计算击败，也不增加等级）；否则 Monocarp 必须击败它，等级 $+1$。
给定 $q$ 个询问，每个询问给出 $x$ 和 $k$，问当参数为 $k$ 时，第 $x$ 只怪兽是否会逃跑。

思路分析

关键观察

• $k$ 越小，Monocarp 升级越慢，越容易在遇到某只怪兽时等级不够，从而必须战斗，导致后续等级增长更慢。
• 反过来，$k$ 越大，升级越快，怪兽更容易逃跑。
• 因此，对于每只怪兽 $i$，存在一个阈值 $c_i$：
  当 $k \ge c_i$ 时，怪兽 $i$ 会逃跑；当 $k < c_i$ 时，怪兽 $i$ 会战斗。

问题转化
我们需要对每个 $i$ 求出 $c_i$。
怪兽 $i$ 逃跑的充要条件是：在遇到它之前，Monocarp 已经击败了至少 $a_i \cdot k$ 只怪兽。
因为每击败一只怪兽等级 +1，当等级 $\ge a_i$ 时怪兽逃跑，而等级 = 已击败数量 / $k$（向下取整？需要仔细分析）

准确条件推导
设 $p$ 为 $i$ 之前实际击败的怪兽数。
Monocarp 的等级 = $\lfloor p/k \rfloor$。
怪兽 $i$ 逃跑 $\iff \lfloor p/k \rfloor \ge a_i \iff p \ge a_i \cdot k$。
所以条件是：$i$ 之前至少有 $a_i \cdot k$ 只怪兽被打败。

二分 + 树状数组求 $c_i$

• 对每个 $i$，二分 $k$ 的值，判断在 $k$ 下怪兽 $i$ 是否会逃跑。
• 判断时，需要知道在 $i$ 之前有多少怪兽被打败。这取决于之前的怪兽是否逃跑，而之前的逃跑又依赖于 $k$。
• 因此我们按顺序处理 $i=1..n$，维护一个树状数组，下标为 $k$，值为逃跑的怪兽数量对应的某种前缀信息。
  具体地：我们二分 $c_i$，并用树状数组快速查询当 $k$ 取某个值时，前 $i-1$ 只怪兽中逃跑的数量，从而得到被打败的数量 $p = (i-1) - \text{逃跑数}$。
  然后判断 $p \ge a_i \cdot k$。

算法步骤

1. 初始化树状数组为空。
2. 对 $i=1$ 到 $n$：
   • 二分最小的 $k$ 使得怪兽 $i$ 逃跑（即找到 $c_i$）。
   • 将 $c_i$ 插入树状数组（表示对于这个 $k$ 值，有一只怪兽会逃跑）。
   • 存储 $c_i$。
3. 回答询问：如果 $k \ge c_x$ 输出 "YES"，否则 "NO"。

时间复杂度

• 预处理：$O(n \log n \log \max(a))$
• 每个询问：$O(\log n)$（直接比较阈值）
• 优化后可达 $O(n \log \max(a) + q)$

AC 代码（优化版）

#include <iostream>
#include <tuple>
using namespace std;
const int N = 4e5 + 10;
int a[N], n, q, tr[N], req[N], cur;

template <typename _Tp>
inline void read(_Tp &x) {
    char ch;
    while (ch = getchar(), !isdigit(ch));
    x = ch - '0';
    while (ch = getchar(), isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ '0');
}
template <typename _Tp, typename... _Args>
inline void read(_Tp &x, _Args &...args) {
    read(x);
    read(args...);
}

inline void update(int x, int v) {
    while (x < N) {
        tr[x] += v;
        x += (x & -x);
    }
}

int main() {
    read(n, q);
    for (int i = 1; i <= n; i++) read(a[i]);

    for (int i = 1; i <= n; i++) {
        int l = 0, cur = 0;
        for (int j = 17; ~j; j--) {
            int nxt = l | (1 << j);
            if (1ll * a[i] * nxt <= cur + tr[nxt]) {
                l = nxt;
                cur += tr[nxt];
            }
        }
        l++;
        update(l, 1);
        req[i] = l;
    }

    for (int i = 1, x, k; i <= q; i++) {
        read(x, k);
        puts(k < req[x] ? "NO" : "YES");
    }
    return 0;
}