缺零分治 mexdnc

· · 题解

前言

赛时被卡常了?

题目分析

考虑 b，如果超过比它少的没有贡献，所以可以做前缀最小值。

注意到答案具有单调性，考虑二分。

我们可以对 b 中超过答案的部分和答案取最小值，求和可以前缀和。找第一个超过答案的可以再二分一次。

时间复杂度 O(T(n+q\log^2 V))，稍微卡上下界即可通过。

代码

#include<bits/stdc++.h>
#define int long long
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
using namespace std;
__inline void read(int&x){
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return;
}
__inline void write(int val){
    if(val>=10)
        write(val/10);
    putchar((val%10)^48);
    return;
}
__inline void writeln(int x){
    write(x);
    putchar('\n');
    return;
}
constexpr int N=1e5+2,Inf=0x3f3f3f3f3f3f3f3fll;
int T,n,q,a[N],cnt[N],maxv,pre[N],sum;
bool check(int ans,int val){
    if(ans==1)
        return maxv==val;
    int l=0,r=maxv;
    if(ans>1000000000)
        l=0;
    else{
        while(l<r){
            int mid=(l+r+1)>>1;
            if(cnt[mid]>ans)
                l=mid;
            else
                r=mid-1;
        }
    }
    return(pre[maxv]-pre[l])+ans*l>=val;
}
void Main(){
    read(n),read(q);
    cnt[0]=Inf,maxv=0;
    for(int i=1,fl=1;i<=n;i++){
        read(a[i]),read(cnt[i]);
        if(fl&&maxv==i-1&&((i==1&&a[i]==0)||(i!=1&&a[i-1]==a[i]-1)))
            maxv=i,cnt[i]=min(cnt[i],cnt[i-1]);
        else
            cnt[i]=0,fl=0;
        sum+=cnt[i];
    }
    pre[0]=0;
    for(int i=1;i<=maxv;i++)
        pre[i]=pre[i-1]+cnt[i];
    for(int m;q;--q){
        read(m);
        if(maxv==m){
            putchar('1'),putchar('\n');
            continue;
        }
        if(m==0){
            putchar('-'),putchar('1'),putchar('\n');
            continue;
        }
        int l=1,r=sum+1;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid,m))
                r=mid;
            else
                l=mid+1;
        }
        if(r<=sum)
            writeln(r);
        else
            putchar('-'),putchar('1'),putchar('\n');
    }
    return;
}
signed main(){
    for(read(T);T;--T)
        Main();
    return 0;
}