CXXVII.[GYM102822I]Invaluable Assets
引理1.最优解法下我们会尽量选取效果为 \(\sqrt{c}\) 的肥料。
考虑每袋肥料单位效果所需费用——此为 \(\dfrac{x^2+c}{x}\)。将分数拆开并套上均值，得到最大值在 \(\sqrt{c}\) 处取到。但因为肥料只能选取整数值，所以我们找到其上取整和下取整中更优的一个作为最值，设其为 \(p\)。则，从 \(1\sim p-1\)，单位费用不增；从 \(p+1\sim\infty\)，单位费用不降。（考虑对勾函数的图像即可）
引理2.最优解法中不会使用效果大于等于 \(2p\) 的肥料。
显然，对于一个效果大于等于 \(2p\) 的肥料，从中拆出一包肥料单独以 \(p\) 的效果使用，单位费用减少了；因此最多只会使用效果小于 \(2p\) 的肥料。
引理3.至多使用两种不同肥料。
考虑假设我们有两包肥料 \(i,j\) 在最优方案中被使用，则一定可以通过把它们各自向中间移动一位使得单位费用减少（因为对勾函数是凹函数）。不断移动，最终会得到结论——我们最多只会使用两种不同肥料，且其效果相差 \(1\)。
引理4.不存在若干个和为 \(p\) 倍数的肥料。
这很显然，因为你明显可以用很多包 \(p\) 肥料来代替。
引理5.选择的非 \(p\) 肥料的费用不大于 \(3c\)。
结合引理2、3、4，我们会发现，我们最多选择 \(p-1\) 个小于 \(2p\) 的不同非 \(p\) 肥料（不然必存在和为 \(p\) 倍数的肥料组）。\((p-1)(2p-1)\leq3c\) 是一定成立的。
则我们考虑暴力背包求出需要肥料总量不大于 \(3c\) 的最优费用。依照上述结论，共有 \(2p-1\) 种不同物品，此部分复杂度 \(O(pc)=O(c\sqrt{c})\)。
现在，考虑回答询问。假设对于一次询问，有一棵树需要生长 \(k\) 单位，则若 \(k\leq3c\)，显然我们可以直接通过DP数组回答；否则，考虑找出与 \(k\) 关于 \(p\) 同余且不大于 \(3c\) 的最大数，则答案即为该数的DP值+剩余部分全部用 \(p\) 填充的费用。
考虑将所有询问按照模 \(p\) 的余数分到 \(p\) 个同余类里，并在每个同余类中通过扫描线维护答案。因为数据随机，所以此部分也可以通过。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,q,p,f[30100],h[100100],lim[100100],equ[110],cost;
ll res[100100];
vector<int>v[10100];
ll query(int now,int las){
ll ret=0;
int l1=lower_bound(h+1,h+n+1,now)-h;
int l2=lower_bound(h+1,h+n+1,las-2*m)-h;
for(int i=l2;i<l1;i++){
int tmp=now-h[i];
if(tmp<=3*m)ret+=f[tmp];
else ret+=f[equ[tmp%p]]+1ll*(tmp-equ[tmp%p])/p*cost;
if(h[i]<=las)ret-=f[las-h[i]];
}
ret+=1ll*((now-las)/p)*cost*(l2-1);
return ret;
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;tt++){
scanf("%d%d%d",&n,&m,&q),p=sqrt(m);
if((p*p+m)*(p+1)>((p+1)*(p+1)+m)*p)p++;
// printf("%d\n",p);
cost=p*p+m;
memset(f,0x3f,sizeof(f)),f[0]=0;
for(int i=1;i<=2*p;i++)for(int j=i;j<=3*m;j++)f[j]=min(f[j],f[j-i]+i*i+m);
// for(int i=0;i<=3*m;i++)printf("%d ",f[i]);puts("");
for(int i=1;i<=n;i++)scanf("%d",&h[i]);sort(h+1,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=q;i++)scanf("%d",&lim[i]),v[lim[i]%p].push_back(i);
for(int i=m-p+1;i<=m;i++)equ[i%p]=i;
for(int i=0;i<p;i++){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end(),[](int x,int y){return lim[x]<lim[y];});
res[v[i][0]]=query(lim[v[i][0]],0);
for(int j=1;j<v[i].size();j++)res[v[i][j]]=res[v[i][j-1]]+query(lim[v[i][j]],lim[v[i][j-1]]);
v[i].clear();
}
printf("Case #%d:\n",tt);
for(int i=1;i<=q;i++)printf("%lld\n",res[i]);
}
return 0;
}