Description：

给出一个由 $1\times1$ 的正方体搭成的物体和 $m$ 个 $1\times1$ 的小正方体，问最高能搭多高，要求新搭的每个立方体下方，左下，右下都有立方体。

$1\leqslant n \leqslant 10^5$

Solution：

首先发现最后的形态一定会是一个最高峰两边是一个一个下降的，联想到 $\text{POI-STU Well}$ ，可以二分最高的高度，然后枚举每个位置作为最终的最高峰，然后利用左右端点的单调性计算出每个位置最近需要改变的的左右端点，用等差数列求和和前缀和计算出这个位置需要补多少块，和 $m$ 比较一下就行了。

但是这里有个问题，右端点可以照常处理，左端点一次可能会移动很多个位置，因为可能有一个很靠后的位置突然满足条件了， $\text{POI-STU WELL}$ 那题之所以不用是因为相差不超过 $mid$ ，有两种处理方案，一是把整个序列倒过来像右端点一样做一遍左端点，二是设 $lef[i]=h[i]-i$ ，然后维护一个 $lef$ 的单调队列，如果队头的下一个也满足条件就弹队头。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;ll m;

#define MAXN 100010

ll h[MAXN],sum[MAXN];

ll lef[MAXN];

#define INF 0x3f3f3f3f3f3f3f3f

int q[MAXN],head,tail;

bool check(ll H)

{//cout << " : " << H << endl;

	ll ans = INF;

	head = 1,tail = 0;q[++tail] = 0;

	for(int i = 1,r = 1;i <= n;++i)

	{

		while(r <= n && (h[r] < H - (r - i) || r <= i))++r;

		if(r == n + 1)break;

		while(head < tail && lef[q[head + 1]] >= H - i)++head;

		int l = q[head];

		ll res = 0;

		if(r > i)res += (H + (H - ((r - 1) - i))) * (r - i) / 2 - H;

		if(l < i)res += (H + (H - (i - (l + 1)))) * (i - l) / 2 - H;//cout << i << " " << l << " " << r << endl;

		res = res + H - (sum[r - 1] - sum[l]);

		if(l != 0)ans = min(ans,res);

		while(head <= tail && lef[i] >= lef[q[tail]])--tail;//cout << res << endl;

		q[++tail] = i;

	}

	return (ans <= m);

}

int main()

{

	freopen("block.in","r",stdin);

	freopen("block.out","w",stdout); 

	scanf("%d%lld",&n,&m);

	sum[0] = 0;ll maxh = 0;

	for(int i = 1;i <= n;++i)

	{

		h[i] = read();

		sum[i] = sum[i - 1] + h[i];

		maxh = max(maxh,h[i]);

		lef[i] = h[i] - i;

	}

	h[0] = h[n + 1] = INF;lef[0] = 0x3f3f3f3f;

	ll l = maxh,r = m + maxh,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(check(mid))l = mid;

		else r = mid - 1;

	}

	cout << l << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}