题解：P14507 缺零分治 mexdnc

· · 题解

贪心地想，我们每次都拿出来能拿出来的最大 \operatorname{mex}，如果发现现在加起来和大于询问了，我们把最后一个 \operatorname{mex} 调小就好了，因为假如你能取出来一个较大的值，较小的值就一定能够取出来，因为把这两个值之间的那些数丢掉就可以。

我们维护 k 次操作能拿出来的价值的前缀和，即出现次数小于等于 k 的值的前缀和。

之后二分一下来看我们取了多少次，因为一个数出现次数可以很大，我们离散化一下就好了。

注意到有巨量边界情况，如果只需要取一次，但我们的询问并不是取一次取出来的最大值，我们需要再取一次把这两个值之间的数丢掉。为什么之前不需要丢掉这些数呢，其他情况在取第一次的时候全给取出来顺带丢掉就可以了。

考虑什么时候是无解，如果每次取最大取出来所有的数都到不了询问就无解，如果询问是零并且零的个数不为零无解。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110000],f[110000],s[110000],hn[110000],hcnt;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--){
        int n,q;cin>>n>>q;hcnt=0;hn[++hcnt]=0;hn[++hcnt]=n+1;
        for(int i=0;i<=n;i++) f[i]=n+1,a[i]=0,s[i]=0;
        for(int i=1;i<=n;i++){
            int x,y;cin>>x>>y;
            if(x<=n) a[x]=y,hn[++hcnt]=y;
        }
        sort(hn+1,hn+hcnt+1);
        int m=unique(hn+1,hn+hcnt+1)-hn-1;
        for(int i=0;i<=n;i++) a[i]=lower_bound(hn+1,hn+m+1,a[i])-hn;
        for(int i=0;i<=n;i++){
            if(a[i]<m) f[a[i]]=min(f[a[i]],i);
        }
        for(int i=1;i<=m;i++) f[i]=min(f[i],f[i-1]);
        s[1]=f[1]*(hn[2]-hn[1]);
        for(int i=2;i<=m-1;i++) s[i]=s[i-1]+f[i]*(hn[i+1]-hn[i]);
        while(q--){
            int x;cin>>x;
            if(x==0 and hn[a[0]]==0) cout<<"1\n";
            else if(x==0 or x>s[m-1]) cout<<"-1\n";
            else{
                int ans=lower_bound(s+1,s+m,x)-s;
                int t=(s[ans]-x)/f[ans];
                if((hn[ans+1]-t==1) and (x!=f[ans])) t--;
                cout<<hn[ans+1]-t<<'\n';
            }
        }
    }
    return 0;
}