题面

代码

#include<iostream>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int n,t;
struct node{
	int l,r,cnt,sum;
}tree[4*N];
void build(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	tree[pos].cnt=tree[pos].sum=0;
	if(lft==rgt) return;
	int mid=(lft+rgt)/2;
	build(pos*2,lft,mid);
	build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int dot,int op){
	if(dot<tree[pos].l||tree[pos].r<dot) return;
	if(tree[pos].l==tree[pos].r){
		if(op){
			tree[pos].cnt++;
			tree[pos].sum+=dot;
		}else{
			tree[pos].cnt--;
			tree[pos].sum-=dot;
		}
		return; 
	}
	upd(pos*2,dot,op);
	upd(pos*2+1,dot,op);
	tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
	tree[pos].cnt=tree[pos*2].cnt+tree[pos*2+1].cnt;
}
int ask_sum(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].sum;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0;
	return ask_sum(pos*2,lft,rgt)+ask_sum(pos*2+1,lft,rgt);
}
int ask_cnt(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].cnt;
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0;
	return ask_cnt(pos*2,lft,rgt)+ask_cnt(pos*2+1,lft,rgt);
}
int cdq(int ll,int rr){
	if(ll==rr){
		return a[ll];
	}
	int mid=(ll+rr)/2;
	int ans=cdq(ll,mid)+cdq(mid+1,rr);
	build(1,1,N);
	int tmp=n+1;
	for(int i=mid;i>=ll;i--){
		tmp=min(tmp,a[i]);
		upd(1,tmp,1);
	}
	tmp=n+1;
	for(int i=mid+1;i<=rr;i++){
		tmp=min(tmp,a[i]);
		ans+=ask_sum(1,1,tmp-1)+ask_cnt(1,tmp,N)*tmp;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<cdq(1,n);
	return 0;
}