题解

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=(1<<18)+5,M=N*4+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=2e9+7;const db eps=1e-5;
int n,A[N],L[N],R[N],st[N],H,Rt,lg[N*2],Si[N],Ph;ll Ans;
struct Node{int x,w,id;Node operator +(const Node &B)const{return (Node){max(x,B.x)+1,w+B.w,id};};}Cl,P[N];
#define CL(A) A.clear(),A.shrink_to_fit()
struct Ques{
	vector<Node> Ts;int H;Node find(int x){return x+H>=Ts.size()?Cl:Ts[x+H];}
	void CG(int w){
		while(Ts.size()-H>1&&max(Ts[H].x,Ts[H+1].x)<w) {Ph=-1;for(int i=H;i<Ts.size();i++) (i-H)&1?(P[Ph]=P[Ph]+Ts[i]):(P[++Ph]=Ts[i]);
			CL(Ts);for(int i=0;i<=Ph;i++) Ts.PB(Cl);for(int i=0;i<=Ph;i++) Ts.PB(P[i]);H=Ph+1;
		}
	}
	void Mg(Ques &B){ 
		if(Ts.size()-H>B.Ts.size()-B.H) {for(int i=B.H;i<B.Ts.size();i++) Ts.PB(B.Ts[i]);CL(B.Ts);return;}
		if(Ts.size()-H<=B.H){for(int i=Ts.size()-1;i>=H;i--) B.Ts[--B.H]=Ts[i];swap(B.Ts,Ts);H=B.H;CL(B.Ts);return;}
		int i;Ph=-1;for(i=H;i<Ts.size();i++) P[++Ph]=Ts[i];for(i=B.H;i<B.Ts.size();i++) P[++Ph]=B.Ts[i];CL(Ts);for(i=0;i<=Ph;i++) Ts.PB(Cl);for(i=0;i<=Ph;i++) Ts.PB(P[i]);CL(B.Ts);H=Ph+1;
	}
}S1[N],S2[N];
void dfs(int x){if(!x) return;dfs(L[x]);dfs(R[x]);int i,j;Si[x]=Si[L[x]]+Si[R[x]]****1[L[x]].CG(A[x]);S1[R[x]].CG(A[x]);S2[L[x]].CG(A[x]);S2[R[x]].CG(A[x]);
	S1[x].Ts.PB((Node){A[x],1,x});S2[x].Ts.PB((Node){A[x],1,x});
	S1[x].Mg(S1[R[x]]);S1[R[x]]=S1[0];S2[x].Mg(S2[L[x]]);S2[L[x]]=S2[0];
	Ans+=1ll*(Si[L[x]]+1)*(Si[R[x]]+1)*A[x];
	for(i=0;i<=lg[S1[x].Ts.size()+S2[x].Ts.size()-S1[x].H-S2[x].H];/*cerr<<Ans<<'\n',*/i++) {
		if(S1[x].Ts.size()-S1[x].H<S2[x].Ts.size()-S2[x].H)for(j=0;j<S1[x].Ts.size()-S1[x].H;j++) Ans+=1ll*S1[x].find(j).w*(max((1<<i)-j,0)+S2[x].H>=S2[x].Ts.size()?0:S2[x].find(max(0,(1<<i)-j)).id-(x-Si[L[x]])+1)/*,cerr<<S2[x].find(max(0,(1<<i)-j)).id<<' '<<x-Si[L[x]]<<' '<<Ans<<'\n'*/;
		else for(j=0;j<S2[x].Ts.size()-S2[x].H;j++) Ans+=1ll*S2[x].find(j).w*(max((1<<i)-j,0)+S1[x].H>=S1[x].Ts.size()?0:x+Si[R[x]]****1[x].find(max(0,(1<<i)-j)).id);
	}
	S1[L[x]].Mg(S1[x]);swap(S1[L[x]],S1[x]);S1[L[x]]=S1[n+1];S2[R[x]].Mg(S2[x]);swap(S2[R[x]],S2[x]);S2[R[x]]=S2[n+1];if(x%100==0) cerr<<x<<'\n';
}
int main(){
	int i;cin>>n;A[0]=1e9;for(i=1;i<=n;i++){cin>>A[i];while(A[st[H]]<A[i]) H--;L[i]=R[st[H]];R[st[H]]=i;st[++H]=i;}Rt=R[0];
	for(i=2;i<=2*n+1;i++) lg[i]=((1<<lg[i-1])==i-1?lg[i-1]+1:lg[i-1]);dfs(Rt);cout<<Ans;; 
}

极限压缩！