Level Up 题解

Lavaloon · 2024-08-01 18:14:36 · 题解

这里是单 \log 做法，并且不需要任何高级数据结构。

\text{Analysis}

从感性理解出发来感受本题可能具有的性质：

• 每打 k 个怪升一级，那这可能说明：k 越大，升级越难。

用数学语言来表述并推广这个结论：

• 对于固定的一个怪物 i，玩家遇到它的时候，玩家的等级一定随着 k 的增大而单调不增。

• 又因为这个怪的等级是恒定的，那么这就说明一种单调性：随着 k 的减小，”这个怪物是否应战“是单调的——只会从应战到不应战。这是因为在 k 比较小的时候，此时玩家可能已经具有高于这个怪的等级，这个怪此时会选择逃跑。

上面加粗的结论终究是感性理解的产物，接下来给出严谨证明：

• 我们定义“所需经验值”是玩家升到下一级，还需击败的怪物的数量。

• 假设 k_1<k_2，考虑两个玩家，第一个玩家 k=k_1，第二个玩家 k=k_2。

• 采用数学归纳法，我们归纳证明一个结论：要么第一个玩家的等级高于第二个玩家，要么第一个玩家的等级等于第二个玩家，且第一个玩家的“所需经验值”少于第二个玩家的“所需经验值”：

  • 一开始两人等级相等，k=k_1 时玩家的“所需经验值”少于 k=k_2 时玩家的“所需经验值”。这是归纳的前提。
  • 假设归纳的结论对一段前缀的怪都成立，对于下一个与第二个玩家战斗的怪：
  • 假如第一个玩家与之战斗，分为两种情况：若刚刚打完这个怪后两人等级相等（当然这说明第一个玩家此时没有升级），那么无论第二个玩家是否升级，第一个玩家的“所需经验值”少于第二个玩家的“所需经验值”仍然是正确的；否则，第一个玩家的等级高于第二个玩家的等级。
  • 假如面对第一个玩家时怪物逃离，那这说明：在将要打这个怪物时，第一个玩家的等级高于第二个时玩家的等级。即使在刚刚打完这个怪物之后第二个玩家获得升级，第二个玩家的“所需经验值”也要大于第一个玩家的“所需经验值”，因为第二个玩家的“所需经验值”现在又是 k_2 了。
  • 证毕。

因此，随着 k 的减小，”一个固定的怪物是否应战“是单调的——只会从应战到不应战。

一些读者此时可能已经有解决这道题的思路了。

\text{Solution}

有了上面的单调性，我们可以对于每个怪物，求出来最小的那个 k，使得在“每打 k 个怪升一级”的情况下，这个怪物会和玩家对战。这样即可对于每一组询问 \mathcal{O}(1) 回答。

对于固定的一个怪物，如何求出这个 k 呢？单调性启示我们使用二分答案。这样，求解的复杂度是 \mathcal{O}(n\log n) 的。

问题是我们要对于所有怪物求解这个玩意，这启示我们使用整体二分。

整体二分的过程中，我们考虑答案 k\in[L,R] 的所有怪物，二分一个 \mathrm{mid}，对这些怪物怪物决策它是否在此情况下应战。

假如它应战，那么这个怪物对应的 k\le \mathrm{mid} ；否则 k>\mathrm{mid}。

我们想要求的是 k=\mathrm{mid} 时，这个怪物前面已经有多少个怪物选择应战了。

为了保证复杂度只与当前参与二分的怪物集合的大小有关，我们对于每一个怪物，记录答案 k<L，且在这个怪物前面的怪物数量——这些怪物在此时二分的 \mathrm{mid} 时一定应战。这样只剩下了 L\le k\le \mathrm{mid}，且在这个怪物前面的情况。

在此情况下，可能应战的怪物一定存在于当前参与二分的怪物集合里面——这是我们复杂度的保障。

在这个集合里面，我们按下标递增的顺序，一个个处理该怪物是否应战。因为下标是递增的，我们直接使用一个计数器 cnt 表示这个集合里面且在这个位置前面已经选择应战的怪物数量即可。不需要任何高级数据结构。

综上，总复杂度 \mathcal{O}(n\log n+q)。

对于不熟练整体二分的读者，代码附带的注释或许会对您有帮助。

\text{Code}

附有部分注释，这样良心的题解哪里找！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<unordered_map>
#include<vector>
#include<bitset>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<numeric>
#include<assert.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define lc (x<<1)
#define rc (x<<1|1)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int Mx=300005,p=998244353;
int read(){
    char ch=getchar();
    int Alice=0,Aya=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') Aya=-Aya;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        Alice=(Alice<<3)+(Alice<<1)+(ch^48),ch=getchar();
    return (Aya==1?Alice:-Alice);
}
int n,m;
int a[Mx];
int inter[Mx];
struct Info{
    int id,pre;
    //id: 怪物编号
    //pre: 答案 k<L ，且在这个怪物前面的怪物数量，——这些怪物在此时二分的 mid 时一定应战 
};
void Solve(int L,int R,vector<Info>vec){//答案 k\in[L,R] 的所有怪物
    if(vec.empty()) return;
    if(L==R){
        for(Info _:vec) inter[_.id]=L;
        return;
    }
    int mid=((L+R)>>1);
    vector<Info>acc,ref;//应战；不应战 
    for(Info &_:vec){
        int i=_.id;
        int lv=1+(_.pre+acc.size())/mid;//题解中的 cnt 就是应战的怪物数量，就是 acc.size()  
        if(lv>a[i]) _.pre+=acc.size(),ref.push_back(_);//注意更新 pre  
        else acc.push_back(_);
    }
    Solve(L,mid,acc);
    Solve(mid+1,R,ref);
}
signed main(){
    n=read(),m=read();
    vector<Info>vec(n);
    for(int i=1;i<=n;i++) a[i]=read(),vec[i-1]={i,0};
    Solve(1,n,vec);
    for(int i=1,id,k;i<=m;i++){
        id=read(),k=read();
        printf((inter[id]>k?"NO\n":"YES\n"));
    }
    return 0;
}