题目传送门
更阅读体验的阅读体验
暴力做法一
我们发现，如果当前 \(a\) 里面没有 0，那么当询问里有 0 时，直接把所有数装进一个集合就可以了。如果询问不是 0，那么无论如何分集合都不能累加贡献，输出 -1。
有了这个情况的切入点，我们很容易联想到，如果要让一个集合的贡献是 \(x\) 的话，那么集合里必须有 0 ~ \(x-1\) 且不能有 \(x\)。
然后我们想，如果我们有很多个集合，那么 0 用到的次数就会特别多，1 也是。
于是我们又联想到了一个结论：如果 \(b_i>b_{i-1}\)，那么我们完全可以让 \(b_i=b_{i-1}\)，因为多了的 \(b_i\) 在最优情况下也只能随便放在一个集合里而不能有任何贡献。（不然你单独开一个集合，集合个数会增多但是 \(m\) 不会变大）
另外，如果 \(i\) 是第一个使得 \(a_i>a_{i-1}+1\) 的点，那么 \([i,n]\) 里的数也都可以扔掉，因为他们无法扔进集合里增加答案。
这样的话，剩下的有用的数就是一段从 0 开始的连续的，且 \(b_i\) 单调不降的二元对。
然后我们考虑，如果当前我们要将贡献从 \(m-1 \to m\)，只有两种选择：一种是用一个 0 开一个新集合，一种是在某个贡献是 \(x\) 的集合里加入 \(x\)，让贡献变成 \(x+1\)。
仔细思考后我们发现，如果能加入 \(x\) 的话，加入 \(x\) 的情况一定更优。感性理解一下都能知道的，因为第二种情况还要开一个集合。
这样的话，当我们从 \(0 \to m\) 向集合里加数时，一定是这么个加法：
1 | 0,1,2,3,...,mx1
2 | 0,1,2,3,...,mx1
3 | 0,1,2,3,...,mx2
...
??? | 0
总之大概就是形如这样，先把 \(0,1,2,\cdots,mx_1\) 塞进一个集合（\(mx_1\) 为当前还有的最大值），然后此时 \(mx_1\) 用掉了一个，我们再塞若干个集合直到 \(mx_1\) 用完，然后我们再用 \(mx_2\)（\(mx_1\) 用完后的最大值）塞集合，直到 \(mx_2\) 用完……直到我们把所有的 0 用完，那就真的开不了集合了。
这个过程中，如果贡献到达了 \(m\)，那么就停止这个过程，输出当前开的集合个数。
于是这就是我们的第一个暴力做法。
暴力做法二
我们发现，我们可以直接一次性把 \(mx_1\) 用完以后统计贡献，时间复杂度从 \(O(mq)\) 变成 \(O(nq)\)。
正解
我们如果设 \(mxx_i\) 表示刚才这个过程中，用光了第 \(i\) 个数后，\(m\) 会是多少。令用一个 \(num_i\) 记录用光第 \(i\) 个数需要多少个集合。（实际上这跟更新后的 \(b_i\) 数值上相同）
如果用一个条形图来表示的话就是这样：
画完图后，很明显，我们的 \(mxx_i\) 是单调不升的。由于单调性，我们可以考虑二分。
我们二分出来第一个 \(\le m\) 的位置，假设是 \(pos\)，那么我们肯定是把 \(a_{pos},a_{pos}+1,\cdots,mx_1\) 的数都开完集合了，在考虑 \(a_{pos-1}\) 这个数怎么开集合呢。
画成图大概这样：
那首先我们要让贡献涨到 \(mxx_{pos}\)，然后不断加入形如 \(0,1,\cdots,a_{pos-1}\) 这样的集合，直到我们的贡献到达了当前的 \(m\)。
那我们让贡献涨到 \(mxx_{pos}\) 需要 \(num_{pos}\) 个集合，再让 \(mxx_{pos}\) 涨到 \(m\) 需要的集合数是 \(\lceil \frac {(m-mxx_{pos})}{a_{pos-1}+1} \rceil\)，应该很好懂，因为每开一个集合贡献都会涨 \(a_{pos-1}+1\)。
这样的话两者相加就是当前询问的答案。
分类讨论
但是这只是最主要的一种情况。剩下的零碎情况除了上面第一个讨论，还比如，如果你的二元组里有 0，那么 \(m=0\) 的情况无解，因为你起码要扔进一个 0 去。
再比如说，如果 \(m > mxx_1\) 也是无解的，因为你最大能拼出的贡献就是 \(mxx_1\) 了，没有别的数了。
如果你的 \(m<a_n\) ，那么第一个集合没有开满就能达成条件，此时剩下的数不能扔进这个集合，需要开一个不含 0 的新集合，所以此时的答案为 2。
这样的话这个题才算讲完。放一下赛时代码：
P14507
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
const int inf=1e16;
int T,n,q,cnt=inf,num[N],mxx[N];
int fl=0;
struct sw{int val,num;
}a[N];inline void INIT(){fl=0,cnt=n;for(int i=1;i<=n;i++){num[i]=0,mxx[i]=0;}
}inline int erfen(int x){int l=1,r=n+1;while(l<r){int mid=(l+r)>>1;if(mxx[mid]<=x){r=mid;}else{l=mid+1;}}return l;
}signed main(){T=read();while(T--){n=read(),q=read();//多测记得初始化 INIT();for(int i=1;i<=n;i++){a[i].val=read(),a[i].num=read();}a[0].num=inf;//处理掉断点之后的值&&多余的没用的数 for(int i=1;i<=n;i++){if(a[i].val==0) fl=1;if(a[i].val>a[i-1].val+1){cnt=i-1;break;}a[i].num=min(a[i].num,a[i-1].num);}n=cnt;mxx[n+1]=0;a[n+1].num=0;//处理mxx和num for(int i=n;i>=1;i--){num[i]=a[i].num;//要先让贡献到达 mxx[i+1],然后i用光以后加上集合个数*贡献 mxx[i]=mxx[i+1]+(a[i].num-a[i+1].num)*(a[i].val+1);}for(int i=1;i<=q;i++){int x=read();if(x==0){if(fl){//有 0 的情况 printf("-1\n");}else{//没 0 的情况 printf("1\n");}}else{if(!fl){//没 0 的话无法拼凑 printf("-1\n");}else{if(x>mxx[1]){//超过最大能拼凑的数 printf("-1\n");continue;}else if(x<=a[n].val){//一个集合不满即可拼凑 printf("2\n");continue;}else{int pos=erfen(x);//pos:mxx里第一个<=x的位置 //ans 的柿子同题解 int ans=num[pos]+(x-mxx[pos]+a[pos-1].val)/(a[pos-1].val+1);printf("%lld\n",ans); }}}}}return 0;
}