首先输入的数组都可以优化掉，重点在于队列。

队列空间不可释放，考虑手写链表模拟队列，采用 vector 动态开空间，并引入空间回收机制（维护被删掉的节点集合 bin，需要的时候清空复用，若为空直接新开空间）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
int n;
namespace IO{
    const unsigned top=(1<<30)-1;
    int typ,m,to;
    unsigned x,y,z,b1,b2,b;
    int P,L,R;
    inline void Init(){
        scanf("%d%d",&n,&typ);
        if(typ) scanf("%u%u%u%u%u%d",&x,&y,&z,&b1,&b2,&m);
    }
    inline int Read(){
        if(typ){
            to++;
            if(to==1) b=b1;
            else if(to==2) b=b2;
            else b=(x*b2+y*b1+z)&top,b1=b2,b2=b;
            if(P<to) scanf("%d%d%d",&P,&L,&R);
            return b%(R-L+1)+L;
        }
        else{int x;scanf("%d",&x);return x;}
    }
    int tp;
    char st[105];
    inline void Write(i128 x){
        while(x) st[++tp]=x%10+'0',x/=10;
        for(int i=tp;i>=1;i--) putchar(st[i]);
        tp=0;
    }
}
using IO::Init;
using IO::Read;
using IO::Write;
int hd,tl,tot;
vector<ll> s,v;
vector<i128> f;
vector<int> l,r;
vector<int> bin;
ll sum;
inline int New(){
    if(bin.empty()){
        s.emplace_back(0);
        v.emplace_back(0);
        f.emplace_back(0);
        l.emplace_back(0);
        r.emplace_back(0);
        return s.size()-1;
    }
    else{
        int t=bin.back();
        bin.pop_back();
        s[t]=v[t]=f[t]=l[t]=r[t]=0;
        return t;
    }
}
signed main(){
    Init();
    hd=tl=New(),tot++;
    for(int i=1;i<=n;i++){
        sum+=Read();
        while(tot>1&&v[r[hd]]<=sum)
            tot--,bin.emplace_back(hd),hd=r[hd];
        int t=New();
        s[t]=sum;
        v[t]=2*sum-s[hd];
        f[t]=f[hd]+(i128)(sum-s[hd])*(sum-s[hd]);
        while(tot>0&&v[t]<=v[tl])
            tot--,bin.emplace_back(tl),tl=l[tl];
        r[tl]=t,l[r[tl]]=tl,tl=t,tot++;
    }
    Write(f[tl]);
    return 0;
}

提供卡空间前的代码作为对照：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
const int maxn=4e7;
int n;
namespace IO{
    const unsigned top=(1<<30)-1;
    int typ,m,to;
    unsigned x,y,z,b1,b2,b;
    int P,L,R;
    inline void Init(){
        scanf("%d%d",&n,&typ);
        if(typ) scanf("%u%u%u%u%u%d",&x,&y,&z,&b1,&b2,&m);
    }
    inline int Read(){
        if(typ){
            to++;
            if(to==1) b=b1;
            else if(to==2) b=b2;
            else b=(x*b2+y*b1+z)&top,b1=b2,b2=b;
            if(P<to) scanf("%d%d%d",&P,&L,&R);
            return b%(R-L+1)+L;
        }
        else{int x;scanf("%d",&x);return x;}
    }
    int tp;
    char st[105];
    inline void Write(i128 x){
        while(x) st[++tp]=x%10+'0',x/=10;
        for(int i=tp;i>=1;i--) putchar(st[i]);
        tp=0;
    }
}
using IO::Init;
using IO::Read;
using IO::Write;
ll s[maxn+5];
int p[maxn+5];
i128 f[maxn+5];
int hd,tl,q[maxn+5];
signed main(){
    Init();
    hd=tl=1;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+Read();
        while(hd<tl&&2*s[q[hd+1]]-s[p[q[hd+1]]]<=s[i]) hd++;
        p[i]=q[hd];
        f[i]=f[p[i]]+(i128)(s[i]-s[p[i]])*(s[i]-s[p[i]]);
        while(hd<=tl&&2*s[i]-s[p[i]]<=2*s[q[tl]]-s[p[q[tl]]]) tl--;
        q[++tl]=i;
    }
    Write(f[n]);
    return 0;
}