思路：这里有一个结论，对于随机数据，一个单调栈里的元素个数为\(log2(n)\)个。
那么对于这道题，我们对于每个点维护一个单调递减的单调栈，栈里维护两个信息，一个是权值，另一个是时间。
这样我们在开一个\(vector\)数组记录每个时刻要在线段树更新的值，然后计算答案即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=2e5+10;
struct CUN
{
int id,t,l,r;
}cun[N];
struct node
{
int val,timi;
friend bool operator < (node x,node y){return x.timi<y.timi;}
};
int cnt,sta[N];
vector<pair<int,int> >v[N];
int n,q;
int a[N];
long long ans[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
inline bool com(CUN x,CUN y) {return x.t<y.t;}
struct Segment_Tree
{
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
ll sum[N<<2];
//iv pp(int rt) {sum[rt]=sum[lc]+sum[rc];}
iv build(int rt,int l,int r)
{
if(l==r)
{
sum[rt]=a[l];
return;
}
build(lc,l,mid),build(rc,mid+1,r);
sum[rt]=sum[lc]+sum[rc];
}
iv change(int rt,int l,int r,int p,int z)
{
if(l==r)
{
sum[rt]=z;
return;
}
if(mid>=p) change(lc,l,mid,p,z);
else change(rc,mid+1,r,p,z);
sum[rt]=sum[lc]+sum[rc];
}
ll query(int rt,int l,int r,int L,int R)
{
if(L<=l and r<=R) return sum[rt];
if(mid>=R) return query(lc,l,mid,L,R);
if(mid<L) return query(rc,mid+1,r,L,R);
return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R);
}
#undef lc
#undef rc
#undef mid
}T;
signed main()
{
freopen("o.in","r",stdin),freopen("o.out","w",stdout);
n=read(),q=read();
for (re i=1;i<=n;++i)
{
a[i] = read ();
while (cnt && a[i] >= a[sta[cnt]]) cnt -- ;
for (re j=1;j <= cnt; ++ j) v[i - sta[j]].push_back (make_pair(i,a[sta[j]]));
sta[++cnt] = i;
}
T.build (1,1,n);
for(re i=1;i<=q;i++) cun[i]=(CUN){i,read(),read(),read()};
sort(cun+1,cun+q+1,com);
int now=1;
for(re i=0;i<=n;i++)
{
for(re j=0;j<v[i].size();j++) T.change(1,1,n,v[i][j].first,v[i][j].second);
while(cun[now].t==i) {ans[cun[now].id]=T.query(1,1,n,cun[now].l,cun[now].r);++now;}
}
for(re i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
