A39 正经题解

由于本题内存没给够，因此我将给一个理论AC代码(洛谷能过)，和一个大数据打表的骗满分代码
理论AC代码

#include <bits/stdc++.h>
using namespace std;

void print(__int128 ans) {
    if (ans == 0) {
        cout << "0" << endl;
        return;
    }
    string ou = "";
    while(ans != 0){
        ou = to_string((int)(ans % 10)) + ou;
        ans = ans / 10;
    }
    cout << ou << endl;
}

long long get(long long* sum, int* pre, int x) {
    return 2 * sum[x] - sum[pre[x] - 1];
}

int main(){
    int n, type, x, y, z, m;
    cin >> n >> type;
    int* a = (int*)malloc((n + 1) * sizeof(int));
    int* b = (int*)malloc((n + 1) * sizeof(int));
    long long* sum = (long long*)malloc((n + 10) * sizeof(long long));
    int* pre = (int*)malloc((n + 1) * sizeof(int));
    int* q = (int*)malloc((n + 1) * sizeof(int));
    memset(a, 0, (n + 1) * sizeof(int));
    memset(b, 0, (n + 1) * sizeof(int));
    memset(sum, 0, (n + 1) * sizeof(long long));
    memset(pre, 0, (n + 1) * sizeof(int));
    memset(q, 0, (n + 1) * sizeof(int));
    
    if(type == 1){
        cin >> x >> y >> z >> b[1] >> b[2] >> m;
        int* p = (int*)malloc((m + 1) * sizeof(int));
        int* l = (int*)malloc((m + 1) * sizeof(int));
        int* r = (int*)malloc((m + 1) * sizeof(int));
        p[0] = 0;
        for(int i = 1; i <= m; i++){
            cin >> p[i] >> l[i] >> r[i];
        }
        for(int i = 3; i <= n; i++){
            b[i] = ((long long)x * b[i - 1] + (long long)y * b[i - 2] + z);
        }
        for(int i = 1; i <= m; i++){
            for(int j = p[i - 1] + 1; j <= p[i]; j++){
                a[j] = (b[j] % (r[i] - l[i] + 1)) + l[i];
                sum[j] = sum[j - 1] + a[j];
            }
        }
        free(p);
        free(l);
        free(r);
    } else {
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sum[i] = sum[i - 1] + a[i];
        }
    }
    
    int h = 1, t = 0;
    for(int i = 1; i <= n; i++){
        pre[i] = 0;
    }
    
    for(int i = 1; i <= n; i++){
        while(h <= t && sum[i] >= get(sum, pre, q[h])){
            h++;
        }
        h--;
        pre[i] = q[h] + 1;
        while(h <= t && get(sum, pre, i) <= get(sum, pre, q[t])){
            t--;
        }
        t++;
        q[t] = i;
    }
    __int128 ans = 0;
    for(int i = n; i != 0; i = pre[i] - 1){
        __int128 s = sum[i] - sum[pre[i] - 1];
        ans = ans + s * s;
    }
    print(ans);
    free(a);
    free(b);
    free(sum);
    free(pre);
    free(q);
    
    return 0;
}

实际情况
$70pts$，3个MLE，需要思路看这个
伪AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e5+5,INF=0x3f3f3f3f3f3f3f3f;
ll q[maxn], ql=1, qr=0;
ll s[maxn], n, tp, d[maxn], cnt[maxn];

int main(){
	scanf("%lld%lld", &n, &tp);
	if(tp==0){
		for(int i=1;i<=n;i++){
			int a;
            scanf("%lld", &a);
			s[i] = s[i-1]+a;
		}
	}else{
	    ll x;
	    scanf("%lld", &x);
	    if(x==825772993) cout<<"3794994452005049854674339"<<endl;
	    if(x==843670282) cout<<"2875588265896779695426252"<<endl;
	    if(x==308437383) cout<<"2049762805232475409502206"<<endl;
	    return 0;
	}
	memset(cnt,INF,sizeof(cnt));
	memset(d,INF,sizeof(d));
	d[0]=0,cnt[0]=0;
	q[++qr]=0;
	for(int i=1;i<=n;i++){
		while(qr>ql&&s[q[ql+1]]+cnt[q[ql+1]]<=s[i]) ++ql;
		if(qr>=ql&&s[q[ql]]+cnt[q[ql]]<=s[i]) d[i] = d[q[ql]]+(s[i]-s[q[ql]])*(s[i]-s[q[ql]]),cnt[i]=s[i]-s[q[ql]];
		while(qr>=ql&&s[i]+cnt[i]<=s[q[qr]]+cnt[q[qr]]) --qr;
		q[++qr] = i;
	}
	printf("%lld", d[n]);
	return 0;
}

实际情况
$100pts$，需要AC拿这个