思路是求出每个点转向次数，然后从外向内操作，注意到对最外层的操作同时能影响内层，设 $sum$ 记录已操作次数，$Judgement$ 记录是否已被影响，ml 记录从左到右到当前第 $i$ 为的最小值，$mr$ 记录从右到左。

不知道是不是思路假了，但是看提交记录过的点挺多的啊。

https://www.luogu.com.cn/record/162381374

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005],ml[200005],mr[200005],f[200005],sum,ans;
bool Judgement[200005];
signed main(){
    int n,m;
    cin>>n>>m;
    ml[0]=mr[n+1]=1e9;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)ml[i]=min(ml[i-1],a[i]);
    for(int i=n;i>=1;i--)mr[i]=min(mr[i+1],a[i]);
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>r>>l>>k;
        f[l]=max(f[l],k-1),f[r]=max(f[r],k);
    }
    list<int> l;
    for(int i=1;i<=n;i++)
    if(f[i])l.push_back(i);
/*
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<f[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<ml[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<mr[i]<<' ';
    cout<<endl;
    for(int i=1;i<=l.size();i++)cout<<l.front()<<' ',l.push_back(l.front()),l.pop_front();
    cout<<endl<<endl;
*/
    while(!l.empty()){
        while(!l.empty()&&sum>=f[l.front()]&&!Judgement[l.front()])l.pop_front();
        while(!l.empty()&&sum>=f[l.back()]&&!Judgement[l.back()])l.pop_back();
        if(l.empty())break;
/*
        cout<<sum<<endl;
        cout<<l.front()<<' '<<l.back()<<endl;
        cout<<f[l.front()]<<' '<<f[l.back()]<<endl;
*/
        if(l.size()>1){
            if(!Judgement[l.front()])f[l.front()]-=sum,Judgement[l.front()]=1;
            if(!Judgement[l.back()])f[l.back()]-=sum,Judgement[l.back()]=1;
            ans+=(ml[l.front()]*min(f[l.front()],f[l.back()])+mr[l.back()]*min(f[l.front()],f[l.back()]));
            sum+=min(f[l.front()],f[l.back()]);
            if(f[l.front()]>f[l.back()])f[l.front()]-=f[l.back()],l.pop_back();
            else if(f[l.front()]<f[l.back()])f[l.back()]-=f[l.front()],l.pop_front();
            else l.pop_front(),l.pop_back();
        }else{
            if(!Judgement[l.back()])f[l.back()]-=sum,Judgement[l.back()]=1;
            ans+=(mr[l.back()]*f[l.back()]);
            break;
        }
    }
    cout/*<<endl*/<<ans;
    return 0;
}