CF1997E 单log题解

Redshift_Shine · 2024-08-02 00:01:24 · 题解

闲话

笑点解析：砍一个 \log 省下十几毫秒，上基础版快读省下 250 毫秒。

题解

在讲解优化方法前请确保自己已经理解了这篇题解。

根据上述的题解，我们需要以更快的方法找到使得每个怪兽 i 坚持应战的阈值 c_i。

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

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

代码

最终运行时间 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");
    }
}