洛谷是 0！求卡常

#include<bits/stdc++.h>
using namespace std;
namespace Mortis{
constexpr int Bl=256,Bt=391,N=Bl*Bt,M=100000;
using ll=long long;
struct rain{
    ll mxs,ls,rs,s;
    rain():mxs(0),ls(0),rs(0),s(0){}
    rain(ll x){mxs=ls=rs=max(x,0ll),s=x;}
    void operator+=(const rain&o){
        mxs=max({mxs,o.mxs,rs+o.ls}),ls=max(ls,s+o.ls),rs=max(o.rs,o.s+rs),s+=o.s;
    }
    rain operator+(const rain&o)const{
        rain tmp=*this;tmp+=o;
        return tmp;
    }
};
int A[N],B[N];
struct{
    int l,r,L,R,LL,RR;
    rain res;
}qr[M];int m;
void build(int bid){
    auto a=A+bid*Bl;
    static int b[Bl],c[Bl],d[Bl];
    static rain f[Bl][Bl],g1[Bl][Bl],g2[Bl][Bl];
    static int Ml[N],Mr[N];
    for(int i=0;i<Bl;++i)b[i]=i,f[i][0]=a[i];
    for(int l=0;(1<<l)<Bl;++l)
        for(int i=0;i<Bl;i+=(1<<(l+1))){
            for(int j=0,p=0,q=(1<<l);j<(1<<(l+1));++j)
                if(p<(1<<l)&&(q==(1<<(l+1))||a[b[p+i]]<a[b[q+i]]))c[p++]=j;
                else c[q++]=j;
            for(int j=0;j<(1<<l);++j){
                for(int k=0;k<=j;++k){
                    g1[j][k]=f[i+j][k],f[i+j][k]={};
                    g2[j][k]=f[i+j+(1<<l)][k],f[i+j+(1<<l)][k]={};
                }
                for(int k=j+1;k<=(j+(1<<l));++k)f[i+j+(1<<l)][k]={};
            }
            for(int j=0;j<(1<<l);++j){
                int jl=c[j],jr=(j+1<(1<<l)?c[j+1]:(1<<(l+1)))-1;
                for(int k=0;k<=j;++k){
                    int kl=k?c[k-1]+1:0,kr=c[k];
                    for(int jj=jl;jj<=jr;++jj)
                        for(int kk=kl;kk<=kr;++kk)
                            f[i+jj][kk]+=g1[j][k];
                }
            }
            for(int j=0;j<(1<<l);++j){
                int jl=c[j+(1<<l)],jr=(j+1<(1<<l)?c[j+(1<<l)+1]:(1<<(l+1)))-1;
                for(int k=0;k<=j;++k){
                    int kl=k?c[k+(1<<l)-1]+1:0,kr=c[k+(1<<l)];
                    for(int jj=jl;jj<=jr;++jj)
                        for(int kk=kl;kk<=kr;++kk)
                            f[i+jj][kk]+=g2[j][k];
                }
            }
            for(int j=0;j<(1<<(l+1));++j)d[c[j]]=b[i+j];
            for(int j=0;j<(1<<(l+1));++j)b[i+j]=d[j];
        }
    for(int i=0,j=0;i<N;++i){
        for(;j<Bl&&a[b[j]]<B[i];++j);
        Ml[i]=j;
    }
    for(int i=N-1,j=Bl-1;i>=0;--i){
        for(;j>=0&&a[b[j]]>B[i];--j);
        Mr[i]=j;
    }
    int l=bid*Bl,r=(bid+1)*Bl-1;
    for(int i=0;i<m;++i){
        if(qr[i].r<l)continue;
        if(qr[i].l>r)continue;
        if(qr[i].LL>qr[i].RR)continue;
        if(l<qr[i].l||qr[i].r<r){
            int ll=max(qr[i].l,l),rr=min(qr[i].r,r);
            for(int j=ll;j<=rr;++j)
                if(qr[i].L<=A[j]&&A[j]<=qr[i].R)
                    qr[i].res+=A[j];
        }else if(Ml[qr[i].LL]<=Mr[qr[i].RR])qr[i].res+=f[Mr[qr[i].RR]][Ml[qr[i].LL]];
    }
}
void main(){
    int n;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)scanf("%d",A+i),B[i]=A[i];
    sort(B,B+N);
    for(int i=0,l,r,L,R;i<m;++i){
        scanf("%d%d%d%d",&l,&r,&L,&R),--l,--r;
        int LL=lower_bound(B,B+N,L)-B,RR=upper_bound(B,B+N,R)-B-1;
        qr[i]={l,r,L,R,LL,RR,(rain){}};
    }
    for(int i=0;i<Bt;++i)build(i);
    for(int i=0;i<m;++i)printf("%lld\n",qr[i].res.mxs);
}
}
int main(){
    Mortis::main();
    return 0;
}