算法

又是 Monocarp

较复杂算法(学习思路)

暴力

观察到对于每一个 \(k\) , 其最大升级次数为 \(\left\lfloor{\frac{n}{k}}\right\rfloor\)
对于所有的 \(k \in [1, n]\), 我们可以知道其升级次数为 \(\displaystyle\sum_{i = 1}^{n} {\left\lfloor{\frac{n}{k}}\right\rfloor} = n \ln n\)

考虑对 \(\text{each } k = x\), 我们求出其每一个每次升级后, 保持这个等级的升级段 \([L, R]\) , 其中 \(R\) 显然二分可求, 考虑 \([L, R]\) 中等级为 \(level\) , 那么这个升级段必须满足

使用主席树等数据结构可求 \(L\)

于是求右端点为 \(\mathcal{O}(\log n)\) 左端点也为 \(\mathcal{O}(\log n)\) 一共有 \(\mathcal{O}(n \ln n)\) 个升级段
总时间复杂度约为 \(\mathcal{O}(n \log^3 n)\)

总结 \(1\)

对于这种典型的调和级数类问题, 考虑每一级单独运算, 这属于一个典型套路

暴力优化

三 \(\log\) 算法无法通过, 考虑优化掉找 \(L\) 的 \(\log\)
容易想到前缀和优化, 令 \(sum_{i, j}\) 表示前 \(i\) 个数, 怪物等级 \(\leq j\) 的怪物个数, 那么可以预处理 \(a_i\) 值域较小的情况 (即 \(k\) 偏大)
对于 \(a_i\) 值域较大的情况, 显然此时 \(k\) 偏小, 于是可以直接枚举数列进行一个模拟

这个有点像根号分治
假设

• \(k \geq B\) 时, 使用 \(\mathcal{O}(\frac{n ^ 2}{B})\) 的预处理, \(\mathcal{O}(n \log^2 n)\) 的回答询问

• \(k < B\) 是, 使用 \(\mathcal{O}(nB)\) 的暴力

均值不等式求得 \(B = \sqrt{n}\), 于是总时间复杂度为 \(\mathcal{O}(n \sqrt{n} + n \log^2 n)\)

代码

总结 \(2\)

对于一种优化技巧, 可以使用根号分治使其达到最优

较简单算法

感性发现, \(k\) 增大时, 显然有升级更困难
于是考虑对于每一个怪物 \(i\), 找到其阈值 \(T_i\) (当 \(k \geq T_i\) 时迎战, \(k < T_i\) 时跑路)
这个 \(T_i\) 显然可以使用二分求得, 总时间复杂度是 \(\mathcal{O} (n ^ 2 \log n)\), 而 \(check\) 函数的时间复杂度是 \(\mathcal{O}(n)\)

观察 \(check\) 函数, 发现其本质为找前面下标, 有多少已经满足条件
于是可以开一个 树状数组 , 记录当前 \(k\) 值对应满足条件的下标数, 那么每次计算之后, 从 \(T_i \rightarrow n\) 整体 \(+ 1\) (后面的显然满足阈值)
时间复杂度优化到 \(\mathcal{O}(n \log^2 n)\)

代码

#include <iostream>
#include <tuple>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid, req[N];
inline void update(int x, int v)
{
    while (x < N)
    {
        tr[x] += v;
        x += (x & -x);
    }
}
inline int query(int x)
{
    int res = 0;
    while (x)
        res += tr[x], x -= (x & -x);
    return res;
}
inline bool check(int x, int v) // xth monster will fl, x=v
{
    return 1ll * a[x] * v <= query(v);
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++)
    {
        l = 1, r = n;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (check(i, mid))
                l = mid + 1;
            else
                r = mid;
        }
        update(l, 1);
        req[i] = l;
    }
    for (int i = 1, x, k; i <= q; i++)
    {
        scanf("%d%d", &x, &k);
        puts(k < req[x] ? "NO" : "YES");
    }
}

总结

当一个操作涉及到其之前的区间, 考虑用区间类数据结构 \(n \rightarrow \log n\)