rt，使用了一个上午做了一些无用的优化，现在大概是 1 秒可以跑完。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
namespace IO{
    constexpr int bufsiz=1<<20;char stk[55];
    char ibuf[bufsiz],*is=ibuf,*it=ibuf;
    char obuf[bufsiz],*os=obuf,*ot=obuf+bufsiz;
    inline void fetch(){is=ibuf,it=ibuf+fread(ibuf,1,bufsiz,stdin);}
    inline char gc(){is==it?fetch():void();return is==it?'\0':(*is++);}
    inline void flush(){fwrite(obuf,1,os-obuf,stdout),os=obuf;}
    inline void pc(char x){os==ot?flush():void();*os++=x;}
    struct Flusher{~Flusher(){flush();}}flusher;
    template<typename T> inline void rd(T&x){
        x=0;char c=gc();bool f=0;
        while(!isdigit(c)) f|=(c=='-'),c=gc();
        while(isdigit(c)) x=x*10+(c-'0'),c=gc();
        if(f) x=-x;
    } template<typename T> inline void wt(T x){
        char*pos=stk;if(!x) pc('0');
        if(x<0) x=-x,pc('-');
        while(x) *++pos=char(x%10+'0'),x/=10;
        while(pos!=stk) pc(*pos--);
    }
} using IO::rd, IO::wt, IO::pc;
const int N = 1e5 + 10, B = 300; using ll = long long;
template <typename T> inline T max(const T&a, const T&b){return a<b?b:a;}
template <typename T> inline T min(const T&a, const T&b){return a<b?a:b;}
struct dat{ll mx, pr, sf, sm;}rs[N], f[B+5][B+5], g[B+5][B+5];
struct qu{int l, r, s, t, p;} q[N];
inline dat operator + (const dat&a, const dat&b){
    return {max(max(a.mx, b.mx), a.sf + b.pr),
        max(a.pr, a.sm + b.pr), max(b.sf, b.sm + a.sf), a.sm + b.sm};
} inline void operator += (dat&a, const dat&b){a = a + b;}
int n, m, a[N], b[N], v[N], t[N<<2], tp, at[2][N<<2]; 
void dv(int l, int r){
    if(l == r){int x = max(b[l], 0); f[l][l] = {x, x, x, b[l]}; return;}
    int md = l + r >> 1; dv(l, md), dv(md + 1, r);
    memcpy(v + l, b + l, (r - l + 1) << 2);
    std::inplace_merge(b + l, b + md + 1, b + r + 1);
    for(int i = l, sl, tl, sr, tr; i <= r; i++){ sl = tl = sr = tr = 0;
        for(int k=l; k<=md; k++) if(v[k]>=b[i]){sl=tl=k;break;}
        for(int k=md+1;k<=r;k++) if(v[k]>=b[i]){sr=tr=k;break;}
        if(sl && v[tl] > b[i]) tl--; if(sr && v[tr] > b[i]) tr--;
        for(int j = i; j <= r; j++){
            if(sl&&tl==l-1&&v[l]<=b[j])tl++; if(sr&&tr==md&&v[md+1]<=b[j]) tr++;
            while(sl&&tl!=l-1&&tl<md&&v[tl]<=b[j]) tl++; if(sl&&tl!=l-1&&v[tl]>b[j]) tl--;
            while(sr&&tr!=md&&tr<r&&v[tr]<=b[j]) tr++; if(sr&&tr!=md&&v[tr]>b[j]) tr--;
            g[i][j] = f[sl][tl] + f[sr][tr];
        }
    } for(int i = l; i <= r; i++) for(int j = i; j <= r; j++) f[i][j] = g[i][j];
}
void sl(int l, int r){ if(r > n || l > r) return;
    int n = r - l + 1; memcpy(b + 1, a + l, n << 2), dv(1, n);
    for(int i = 1; i <= tp; i++) at[0][i] = 1, at[1][i] = n;
    for(int i=1,p=1; i<=tp; i++) {while(p<=n&&b[p]<t[i])++p; at[0][i]=p;}
    for(int i=tp,p=n; i>=1; i--) {while(p>=1&&b[p]>t[i])--p; at[1][i]=p;}
    for(int k = 1; k <= m; k++){ auto[_l, _r, L, R, p] = q[k];
        if(_r < l || _l > r) continue;
        if(_l > l || _r < r) for(int i = max(l, _l), x; i <= min(r, _r); i++) 
            {if(a[i] >= t[L] && a[i] <= t[R]) x = max(0, a[i]), rs[p] += {x, x, x, a[i]};}
        else rs[p] += f[at[0][L]][at[1][R]];
    }
}
inline int fd(int x){return std::lower_bound(t + 1, t + tp + 1, x) - t;}
int main(){
    rd(n), rd(m); for(int i = 1; i <= n; i++) rd(a[i]);
    for(int i = 1, l, r, s, t; i <= m; i++)
        rd(l), rd(r), rd(s), rd(t), q[i] = {l, r, s, t, i};
    for(int i = 1; i <= m; i++) t[++tp] = q[i].s, t[++tp] = q[i].t;
    std::sort(t + 1, t + tp + 1); tp = std::unique(t + 1, t + tp + 1) - t - 1;
    for(int i = 1; i <= n; i++) q[i].s = fd(q[i].s), q[i].t = fd(q[i].t);
    for(int i = 1; i <= n; i += B) sl(i, i + B - 1);
    sl(n/B*B+1, n); for(int i = 1; i <= m; i++) wt(rs[i].mx), pc('\n');
}