1795E - Explosions - CodeForces Solution

#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
constexpr int N=3e5+5;
int n,a[N],w[N],q[N],hd,tl,cnt[N];ll pre[N],suf[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;while(T--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		ll ans=0;hd=1;tl=0;
		for(int i=1,l=0;i<=n;i++){
			w[i]=a[i]-i;cnt[i]=1;l=max(l,-w[i]);
			for(;hd<=tl&&q[hd]-cnt[q[hd]]<l;hd++){
				ans+=1ll*w[q[hd]]*(l-q[hd]+cnt[q[hd]]);
				ans+=1ll*(l+q[hd]-cnt[q[hd]]+1)*(l-q[hd]+cnt[q[hd]])/2;
				cnt[q[hd]]=q[hd]-l;
				if(cnt[q[hd]])break;
			}
			for(;hd<=tl&&w[q[tl]]>=w[i];tl--){
				ans+=(w[q[tl]]-w[i])*cnt[q[tl]];
				cnt[i]+=cnt[q[tl]];
			}
			pre[i]=ans;
			q[++tl]=i;
		}
		reverse(a+1,a+n+1);
		ans=0;hd=1;tl=0;
		for(int i=1,l=0;i<=n;i++){
			w[i]=a[i]-i;cnt[i]=1;l=max(l,-w[i]);
			for(;hd<=tl&&q[hd]-cnt[q[hd]]<l;hd++){
				ans+=1ll*w[q[hd]]*(l-q[hd]+cnt[q[hd]]);
				ans+=1ll*(l+q[hd]-cnt[q[hd]]+1)*(l-q[hd]+cnt[q[hd]])/2;
				cnt[q[hd]]=q[hd]-l;
				if(cnt[q[hd]])break;
			}
			for(;hd<=tl&&w[q[tl]]>=w[i];tl--){
				ans+=(w[q[tl]]-w[i])*cnt[q[tl]];
				cnt[i]+=cnt[q[tl]];
			}
			suf[n-i+1]=ans;
			q[++tl]=i;
		}
		reverse(a+1,a+n+1);
		ans=0;
		for(int i=1;i<=n;i++){
			ans+=a[i];
		}
		for(int i=1;i<=n;i++){
			//printf("%d: a=%d,pre=%lld,suf=%lld\n",i,a[i],pre[i],suf[i]);
			ans=min(ans,a[i]+pre[i]+suf[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}