C++(clang++ 11.0.1) 解法, 执行用时: 161ms, 内存消耗: 8936K, 提交时间: 2023-05-18 23:30:45

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int n,m,totq;
ll a[N],ans[N];
struct Line{
	int id,l,r,x;
	friend bool operator<(Line a,Line b){
		return a.x<b.x;
	}
}ask[N];
struct Q{
	int id;
	ll val,sum;
}q[N];


ll get(int x){
	
	int l=1,r=totq;
	while(l<=r){
		int m=(l+r)>>1;
		if(q[m].id<x) l=m+1;
		else r=m-1;
	}
	
	return q[l].sum+q[l].val*(x-q[l-1].id);
} 

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		ask[i].id=i;
		scanf("%d %d %d",&ask[i].l,&ask[i].r,&ask[i].x);
	}
	sort(ask+1,ask+m+1);
	
	int pos=0;
	
	for(int i=1;i<=m;++i){
		while(pos<=ask[i].x){
			while(a[pos]<=a[pos+1]&&pos+1<=ask[i].x) pos++;
			while(totq&&q[totq].val<=a[pos]) totq--;
			
			++totq;
			if(totq==1) q[totq]=(Q){pos,a[pos],0};
			else q[totq]=(Q){pos,a[pos],q[totq-1].sum+q[totq-1].val*(q[totq-1].id-q[totq-2].id)}; 
		
			pos++;
		}

		ans[ask[i].id]=get(ask[i].r)-get(ask[i].l-1);
	}

	for(int i=1;i<=m;++i) printf("%lld ",ans[i]);
}