单调队列+差分做法

#include<bits/stdc++.h>
using namespace std;
long long n,p[500005],q[500005],a[500005],l[500005],r[500005];
void f(long long L,long long R,long long x,long long y){
	if(l>r) return ;
	p[L]+=x,p[R+1]-=x,p[R+1]-=y*(R-L),q[L+1]+=y,q[R+1]-=y;
}
int main(){
	/*
	
	*/
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i+n+n]=a[i];
	}
	
	for(int i=1;i<=n;i++) r[i]=n*3+i,l[i]=0;
	stack<long long> que,sta;
	for(int i=1;i<=n*3;i++){
		while(que.size()&&a[que.top()]>=a[i]) que.pop();
		l[i]= que.size() ? que.top() : l[i],que.push(i);
	}//cout<<1;
	for(int i=n*3;i>0;i--){
		while(sta.size()&&a[sta.top()]>a[i]) sta.pop();
		r[i]= sta.size() ? sta.top() : r[i],sta.push(i);
	}//for(int i=1;i<=n*3;i++) cout<<l[i]<<r[i]<<' ';
	
	for(long long i=1;i<=n;i++){
		l[i]=max(l[i+n],i)-n;
		r[i]=min(r[i+n],i+2*n)-n;
		f(1ll,min(i-l[i],r[i]-i),a[i],a[i]);
		f(min(i-l[i],r[i]-i)+1,max(i-l[i],r[i]-i),(min(i-l[i],r[i]-i))*a[i],0);
		f(max(i-l[i],r[i]-i)+1,r[i]-l[i]-1,(min(i-l[i],r[i]-i))*a[i]-a[i],-a[i]);
	}
	for(int i=1;i<=n;i++){
		q[i]+=q[i-1],p[i]+=q[i];
	}
	for(int i=2;i<=n;i++){
		p[i]+=p[i-1];
		cout<<p[i]<<endl;
	}
	cout<<p[n];
	return 0;
}