题解：P4587 [FJOI2016] 神秘数

· · 题解

贡献一篇别样的的莫队题解。

考虑新加入一个数对序列神秘数的影响。如果存在一个数 x，x>\sum_{a_i<x}a_i+1，那么从 \sum_{a_i<x}a_i+1 到 x-1 的所有数都无法被表示。

这启示我们一个贪心的思路：维护一个数 cur，表示当前可以表示出小于等于 cur 的所有数。初始 cur=0，此时我们查询当前区间 \le cur+1 所有数字的和，记为 s。

如果 s=cur，代表 \le cur+1 的数最多只能凑出 cur，而其他的数个个 >cur+1，不能对答案造成影响，此时答案就是 cur+1。

如果 s>cur，代表 \le cur+1 的数还能凑出 >cur 的数，那么 s 以内的数都可以被凑出了，此时令 cur=s 并且继续查询是否能凑出更大的数。

此时可以用莫队维护答案了，普通莫队即可。首先进行离散化，值域 V 缩小到 n，此时对值域进行分块，方便查询区间 \le cur+1 数字的和。

设 S 为查询区间内离散化后的 a_i 的和，时间复杂度为 O((n+m)\sqrt n+m\sqrt V\log S)，实际上远远跑不满，总用时不到 900ms，比基于 multiset 的回滚莫队要快。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define F first
#define S second
using namespace std;
const int N=1e5+5;
int n,m,a[N],B,ans[N],ar[N],b[N],vn,cnt[N],sum[N],pos[N],lp[N],rp[N];
struct qry{
    int l,r,x;
}q[N];
bool cmp(qry a,qry b){
    if(a.l/B!=b.l/B) return a.l<b.l;
    return a.r<b.r;
}
void add(int p){
    int x=ar[p];
    cnt[x]++;
    sum[pos[x]]+=b[x];
}
void del(int p){
    int x=ar[p];
    cnt[x]--;
    sum[pos[x]]-=b[x];
}
int qsum(int k){
    int p=upper_bound(b+1,b+vn+1,k)-b-1,res=0;
    if(p<=0) return 0;
    if(pos[1]==pos[p]) for(int i=1;i<=p;i++) res+=cnt[i]*b[i];
    else{
        for(int i=1;i<=rp[pos[1]];i++) res+=cnt[i]*b[i];
        for(int i=pos[1]+1;i<=pos[p]-1;i++) res+=sum[i];
        for(int i=lp[pos[p]];i<=p;i++) res+=cnt[i]*b[i];
    }
    return res;
}
int getans(){
    int cur=0;
    while(1){
        int s=qsum(cur+1);
        if(s==cur) return cur+1;
        cur=s;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    vn=unique(b+1,b+n+1)-b-1;
    int vB=sqrt(vn)+1;
    int vbn=(vn+vB-1)/vB;
    for(int i=1;i<=vn;i++) pos[i]=(i-1)/vB+1;
    for(int i=1;i<=vbn;i++){
        lp[i]=(i-1)*vB+1;
        rp[i]=min(i*vB,vn);
    }
    for(int i=1;i<=n;i++) ar[i]=lower_bound(b+1,b+vn+1,a[i])-b;
    B=sqrt(n)+1;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].x=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>q[i].l) add(--l);
        while(r<q[i].r) add(++r);
        while(l<q[i].l) del(l++);
        while(r>q[i].r) del(r--);
        ans[q[i].x]=getans();
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}