题解：CF1997E Level Up

· · 题解

闲话

大家好，我非常不喜欢暴力数据结构，所以我用树状数组和二分搜索过了这道题。

思路

首先，显然 k 越小越容易升级，也就是说 k 越小，逃跑的怪兽就越多。那么对于每一个位置 i，我们可以求出一个阈值 c_i，保证只要 k 不小于 c_i，那么这个怪兽就一定不会逃跑。

解法

二分搜索。

使得等级为 a_i 的怪兽 i 在参数 k 下逃跑的充要条件是在 i 之前 Monocarp 的等级超越了 a_i，也就是说在 i 之前已经打了至少 a_ik 个怪兽。快速查询一个位置在不同的 k 下有多少个怪物被打可以使用树状数组。

时间复杂度 O(n\log n\log \max(a)+q)。

代码

#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");
    }
}

讲个笑话，赛时我把查询排序了导致多用了几十毫秒，虽然还是快的一批。大概四百多毫秒。

但，你不会认为已经结束了吧？

优化

优化 1 - 树状数组内部操作

众所周知，query 函数是这么写的：

inline int query(int x)
{
    int res = 0;
    while (x)
        res += tr[x], x -= (x & -x);
    return res;
}

换句话说，query 函数干的事就是一个一个削掉 x 的 lowbit，顺便加上对应位置上的 \text{tr}_x。

也就是说，如果我们给 x 加上一个小于它 lowbit 的数 y，那么 \text{query}(x+y)=\text{query}(x)+\text{tr}_{x+y}。

利用这个性质，我们可以从上向下枚举 c_i 的每个二进制位，若怪兽会应战，就忽略；否则，加上这个二进制位。

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

时间复杂度 O(n\log \max(a))。

优化 2 - 输入优化

scanf 比 getchar 慢是一个老生常谈的道理。

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...);
}

支持可变参数调用，代码是从之前一次洛谷月赛那里学的，但是忘了是哪一场。

最终时间复杂度 O(n\log \max(a)+q)。

优化代码

最终运行时间 187 毫秒。评测记录在这里。

#include <iostream>
#include <tuple>
using namespace std;
const int N = 4e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid, 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++)
    {
        l = cur = 0;
        for (int j = 17; ~j; j--)
        {
            if (1ll * a[i] * (l | (1 << j)) <= cur + tr[l | (1 << j)])
                l |= (1 << j), cur += tr[l];
        }
        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");
    }
}