C++ 解法, 执行用时: 263ms, 内存消耗: 10072K, 提交时间: 2021-11-17 23:48:46

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 410000
using namespace std;
struct node{int l,r,h,id;}a[N];
struct node1{int l,r,lc,rc,lz,a,b,lza,lzb;}lt[2*N];
int s[N],tl,n,m,h[N],pos[N];
bool cmp(node x,node y)
{
    if(x.l<y.l) return 1;
    return 0;
}
void down(int now)
{
    int lc=lt[now].lc,rc=lt[now].rc;
    if(lt[now].lza)
    {
        lt[now].a+=lt[now].lza;
        if(lc) lt[lc].lza+=lt[now].lza;
        if(rc) lt[rc].lza+=lt[now].lza;
        lt[now].lza=0;
    }
    if(lt[now].lzb)
    {
        lt[now].b+=lt[now].lzb;
        if(lc) lt[lc].lzb+=lt[now].lzb;
        if(rc) lt[rc].lzb+=lt[now].lzb;
        lt[now].lzb=0;
    }
}
void upd(int now)
{
    int lc=lt[now].lc,rc=lt[now].rc;
    if(lc) down(lc);
    if(rc) down(rc);
    lt[now].a=min(lt[lc].a,lt[rc].a);
    lt[now].b=max(lt[lc].b,lt[rc].b);
}
void bt(int l,int r)
{
    int now=++tl;
    lt[now].l=l;lt[now].r=r;
    if(l<r)
    {
        int mid=(l+r)/2;
        lt[now].lc=tl+1;bt(l,mid);
        lt[now].rc=tl+1;bt(mid+1,r);
        upd(now);
    }
    else lt[now].a=s[a[l].r],lt[now].b=s[a[l].l-1];
}
int finda(int now,int l,int r)
{
    int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2;
    down(now);
    if(lt[now].l==l && lt[now].r==r) return lt[now].a;
    if(mid>=r) return finda(lc,l,r);
    else if(l>mid) return finda(rc,l,r);
    else return min(finda(lc,l,mid),finda(rc,mid+1,r));
}
int findb(int now,int l,int r)
{
    int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2;
    down(now);
    if(lt[now].l==l && lt[now].r==r) return lt[now].b;
    if(mid>=r) return findb(lc,l,r);
    else if(l>mid) return findb(rc,l,r);
    else return max(findb(lc,l,mid),findb(rc,mid+1,r));
}
void changea(int now,int l,int r,int d)
{
    int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2;
    down(now);
    if(lt[now].l==l && lt[now].r==r) {lt[now].lza+=d;return;}
    if(mid>=r) changea(lc,l,r,d);
    else if(l>mid) changea(rc,l,r,d);
    else changea(lc,l,mid,d),changea(rc,mid+1,r,d);
    upd(now);
}
void changeb(int now,int l,int r,int d)
{
    if(l>r) return;
    int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2;
    down(now);
    if(lt[now].l==l && lt[now].r==r) {lt[now].lzb+=d;return;}
    if(mid>=r) changeb(lc,l,r,d);
    else if(l>mid) changeb(rc,l,r,d);
    else changeb(lc,l,mid,d),changeb(rc,mid+1,r,d);
    upd(now);
}
void init()
{
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &s[i]);
        s[i]+=s[i-1];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h),a[i].id=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++) pos[a[i].id]=i;
    bt(1,m);
}
void solve()
{
    for(int i=1;i<=m;i++)
    {
        int p=pos[i],A=finda(1,p,m),B=findb(1,1,p);
        int k=min(A-B,a[p].h);
        printf("%d\n",k);
        changea(1,p,m,-k);
        changeb(1,p+1,m,-k);
    }
}
int main()
{
    init();
    solve();
    return 0;
}