线段树乱搞过了。

具体思路是：枚举每一个位置，执行很多次操作直到这个数为 0，执行的操作是二分到最远端的非 0 点（从当前位置到那个位置至少可以减 1），然后将这个区间减去最小值。

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

int a[100010];

int tree[400010],tag[400010];

void build(int now,int l,int r)
{
	if(l==r)
	{
		tree[now]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	tree[now]=min(tree[now<<1],tree[now<<1|1]);
}

// 区间 min，区间加

void push_down(int now)
{
	tree[now<<1]+=tag[now],tag[now<<1]+=tag[now];
	tree[now<<1|1]+=tag[now],tag[now<<1|1]+=tag[now];
	tag[now]=0;
}

void upd(int now,int ql,int qr,int qz,int l,int r)
{
	if(ql<=l && r<=qr)
	{
		tree[now]+=qz,tag[now]+=qz;
		return;
	}
	push_down(now);
	int mid=(l+r)>>1;
	if(ql<=mid) upd(now<<1,ql,qr,qz,l,mid);
	if(qr>mid) upd(now<<1|1,ql,qr,qz,mid+1,r);
	tree[now]=min(tree[now<<1],tree[now<<1|1]);
}

int query(int now,int ql,int qr,int l,int r)
{
	if(ql<=l && r<=qr)
	{
		return tree[now];
	}
	push_down(now);
	int mid=(l+r)>>1,ans=1e9;
	if(ql<=mid) ans=min(ans,query(now<<1,ql,qr,l,mid));
	if(qr>mid) ans=min(ans,query(now<<1|1,ql,qr,mid+1,r));
	return ans;
}

int main()
{
	int n;
	long long cnt=0;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1; i<=n; ++i)
	{
		while(query(1,i,i,1,n))
		{
			int l=i,r=n,mid,ans;
			while(l<=r)
			{
				mid=(l+r)>>1;
				if(query(1,i,mid,1,n))
				{
					l=mid+1;
					ans=mid;
				}
				else r=mid-1;
			}
			int q=query(1,i,ans,1,n);
			cnt+=q;
			upd(1,i,ans,-q,1,n);
		}
	}
	printf("%lld",cnt);
	return 0;
}

过了，但过得很险

所以这种做法是不是带根号啊（盲猜 $\mathcal O(n\sqrt{n} \log n)$）