P14507 缺零分治 题解

· · 题解

一个不用二分的写法

题意

要将一堆数划分为尽量少个可重集合，使得每个集合内部的 mex 加起来恰好为 m 。求最少集合个数。多个询问。

性质分析

我们如果要求一个集合的 mex 为 x ，那么就要求集合中包含 [0,x-1] 的所有数。

解法

题目给出了每个数字出现的次数，于是我们可以结合这个信息，处理出 f[i] ，表示最多能选多少次区间 [0,i] 中的每个数一次，也就是组成一个 mex 为 i+1 的集合。

处理的时候有一个类似于递归的过程，为了方便接下来的处理（避免写一堆 map 的处理），我们把它存进栈中：

  for(int i=1;i<=n;i++){
    int x,y;
    scanf("%lld%lld",&x,&y);
    cnt[x]=y;
    if(!s.empty()){
      auto pr=s.top();
      int u=pr.first,v=pr.second;
      if(u==x-1){
        s.pop();
        if(cnt[x]>=v) s.push(make_pair(x,v));
        else{
          s.push(make_pair(u,v-cnt[x]));
          s.push(make_pair(x,y));
        }
      } 
    }
    else if(x==0) s.push(make_pair(x,y));
  }

接下来我们处理询问，可以这样想，如果我们按照 f[i] 选择出了若干个集合，并且是尽量选 mex 大的集合，他们的 mex 恰好等于 m ，太好了，只需要看看没被选的数合不合法就行：不合法的情况，当且仅当选出的所有集合的 mex 都等于一个 c ，且 cnt[c]>0 。不合法就调整，合法的话直接输出答案就好。

如果按照前面的选法，选出来 mex 大于 m ，可以直接不管他，就是不管选出来区间末端的一些元素，对答案无影响。不合法的情况同上。

直接写，特判 m=0 的情况，如下：

    while(Q--){
            scanf("%lld",&m);
            stack <pair<int,int> > tmp;
            int ret=0,ans=0,is_all_same=1;
            int how_many_time_we_cal=0,is_output_ans=0;
            if(m==0){
                if(cnt[0]) printf("-1\n");
                else printf("1\n");
                continue;
            }
            while(!query.empty()){
                if(how_many_time_we_cal) is_all_same=0;
                how_many_time_we_cal++;
                auto pr=query.top();
                int u=pr.first,v=pr.second;
                int t=min((m-ret)/(u+1ll)+((m-ret)%(u+1ll)>0),v);//这一步全选/选最少并达到m
                ans+=t;
                ret+=(u+1)*t;
                if(ret==m){
                    if(!is_all_same){
                        is_output_ans=1;
                        printf("%lld\n",ans);
                        break;  
                    }
                    else {
                        if(cnt[u+1]){//选法不可行 
                            ret-=u+1;
                            ans--;
                        }
                        else {
                            is_output_ans=1;
                            printf("%lld\n",ans);
                            break;
                        }
                    }
                }
                else if(ret>m){
                    is_output_ans=1;
                    if(cnt[m]>0&&(ans==1||is_all_same)) ans++;
                    printf("%lld\n",ans);
                    break;
                }
                tmp.push(pr);
                query.pop();
            } 
            while(!tmp.empty()){//还原栈 
                query.push(tmp.top());
                tmp.pop();
            }
            if(!is_output_ans) printf("-1\n");
        }

由于栈长度差不多是 O(n) 的，所以整份代码复杂度为 O(Tnq) 。

考虑优化，我们发现一次一次跳这个栈有点太慢了，于是可以把询问离线下来，从小到大排好序，这样就只用跑一遍栈，每次统计答案的时候要退回一位，防止询问之间互相影响。复杂度优化为线性。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10; 

int n,m,Q,T;
map <int,int> cnt;

struct node{
    int num,id,res;
}ask[N];

bool cmp1(node A,node B){
    if(A.num!=B.num) return A.num<B.num;
    else return A.id<B.id; 
}
bool cmp2(node A,node B){
    return A.id<B.id; 
}

signed main(){
    scanf("%lld",&T);
    for(int test=1;test<=T;test++){
        scanf("%lld%lld",&n,&Q);
        stack <pair<int,int>> s;

        for(int i=1;i<=n;i++){
            int x,y;
            scanf("%lld%lld",&x,&y);
            cnt[x]=y;
            if(!s.empty()){
                auto pr=s.top();
                int u=pr.first,v=pr.second;
                if(u==x-1){
                    s.pop();
                    if(cnt[x]>=v) s.push(make_pair(x,v));
                    else{
                        s.push(make_pair(u,v-cnt[x]));
                        s.push(make_pair(x,y));
                    }
                }   
            }
            else if(x==0) s.push(make_pair(x,y));
        }

        for(int i=1;i<=Q;i++){
            scanf("%lld",&ask[i].num);
            ask[i].id=i;
            ask[i].res=0;
        }
        sort(ask+1,ask+Q+1,cmp1);
        int ret=0,ans=0,is_all_same=1,how_many_time_we_cal=0;
        for(int i=1;i<=Q;i++){
            m=ask[i].num;
            if(m==0){
                if(cnt[0]) ask[i].res=-1ll; 
                else ask[i].res=1ll;
                continue;
            }
            while(!s.empty()){
                if(how_many_time_we_cal) is_all_same=0;
                how_many_time_we_cal++;
                auto pr=s.top();
                int u=pr.first,v=pr.second;
                int t=min((m-ret)/(u+1ll)+((m-ret)%(u+1ll)>0),v);
                int lst_ans=ans,lst_ret=ret;
                ans+=t;
                ret+=(u+1ll)*t;
                if(ret==m){
                    if(!is_all_same){
                        ask[i].res=ans;
                        ans=lst_ans,ret=lst_ret;
                        break;  
                    }
                    else {
                        if(cnt[u+1]) ret-=u+1ll,ans--;
                        else {
                            ask[i].res=ans;
                            ans=lst_ans,ret=lst_ret;
                            break;
                        }
                    }
                }
                else if(ret>m){
                    if(cnt[m]&&(ans==1||is_all_same)) ans++;
                    ask[i].res=ans;
                    ans=lst_ans,ret=lst_ret;
                    break;
                }
                s.pop();
            } 
            if(!ask[i].res) ask[i].res=-1ll;
        } 
        sort(ask+1,ask+Q+1,cmp2);
        for(int i=1;i<=Q;i++) printf("%lld\n",ask[i].res);
        cnt.clear();
    }
    return 0;
}