题目描述
LXL进入到了一片丛林,结果他发现有n只怪物排成一排站在他面前。LXL有一杆火枪能对付这些怪物。他知道从左至右数第i只怪物的血量是mi。现在LXL可以将一些子弹射向某个怪物。LXL可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第i个怪物，如果这个子弹的威力值为p，除了这个怪物会掉p点血以外，它左边的第j个怪物(j<i)，也会遭到Max(0, p - (i - j) * (i - j))的溅射伤害（好神奇的子弹）。当某只怪物的血量小于0时，它就死了，但它的尸体还在，即怪物的位置永远不会改变。LXL希望只用k发子弹，请你求出一个最小的正整数p，使LXL用k发子弹且每发子弹的威力值为p就可以消灭所有怪物。
SOL
我们显然可以发现这道题的二分性质。再细心观摩一波数据，50W，只能用O（nlogn）及以下的算法。二分需要一个log，这便要求我们O(n)处理check函数。
比较显然，我们可以差分。我们发现只有右边对左边有贡献，不妨从右到左做，我们发现这是一个二次多项式，那么可以二阶差分，对于单一的子弹来说，他的
伤害的差分是一个等差数列，K=2n-1，那对差分数组进行差分，我们统计对当前怪物有贡献的子弹，那么这个伤害的二阶差分就是两倍的子弹数。那么我们还
有一个问题，那就是子弹的伤害不可能是负数。我们有这样一个方法，我们在一颗子弹的伤害区域的最左侧打标记 -1，标示该位置之后出子弹范围，那么我们同
时在一阶差分数组中把多余的伤害减掉，那么这颗子弹之后就没有贡献了。
#include<bits/stdc++.h>
#define sight(c) ('0'<=c&&c<='9')
#define LL long long
inline void read(int &x) {
static char c;
for (;!sight(c);c=getchar());
for (x=;sight(c);c=getchar())x=x*+c-;
}
inline void read(long long &x) {
static char c;static int b;
for (b=;!sight(c);c=getchar())if (c=='-') b=-;
for (x=;sight(c);c=getchar())x=x*+c-;
x*=b;
}
#define N 501007
#define min(a,b) (a)<(b)?(a):(b)
#define HP a
LL len,ans2,ans,Ans,cm,n,dle,a[N],k,r,c1[N],c2[N],c3[N],c4[N],hp[N];
bool check(LL P)
{
int sss=sqrt(P); int tot=;
LL t1=,t2=,t3=,t0=;
memset(c1,,sizeof(c1)); memset(c2,,sizeof(c2));
memset(c3,,sizeof(c3)); memset(c4,,sizeof(c4));
for(int i=;i<=n;++i)hp[n-i+]=HP[i]+;//记得+1，因为怪物0血还没有死
for(int i=;i<=n;++i)
{
t3+=c3[i]; t2+=c2[i];
t1+=c1[i]+t2; t0+=t1+c4[i];
hp[i]-=1ll*P*t3-t0;
if(hp[i]<=)continue; int gg=((hp[i]+P-)/P);
tot+=gg; if(tot>k)return false;
c3[i+]+=gg;c3[min(n+,i+sss+)]-=gg;
c2[i+]+=1ll**gg;c2[min(n+,i+sss+)]-=*gg;
c1[i+]-=gg;c1[min(n+,i+sss+)]-=1ll*(1ll**sss-)*gg;
c4[min(n+,i+sss+)]-=1ll*sss*sss*gg;
}
return tot<=k;
}
int main () {
read(n); read(k);
for (int i=;i<=n;i++) read(a[i]);
r=1ll<<;
while (r) {
if (!check(ans+r)) ans+=r;
r>>=;
}
printf("%lld\n",ans+); return ;
}