思路与算法

记正数前缀和为S_i，令pre_i是前缀i的最后一段之前的断点，末段长度L_i=S_i-S_(pre_i)。取pre_0=0、S_0=0。若把前缀j的最优分拆后面接到i，则可接条件是S_i-S_j≥L_j，即S_i≥2S_j-S_(pre_j)。取所有可接j中最大的一个作为pre_i，便得到最小末段。 把候选j的阈值记为H_j=2S_j-S_(pre_j)。索引按时间递增；若新候选i的阈值不大于队尾j，则i至少同样早可接且索引更大，j永久被支配，可以弹掉。队首所有H≤当前S_i的候选依次成为可接断点，保留最大的断点；它们不再留在待接队列。每点入队一次并从前或后弹出一次。 算法不必为每点保存大整数最优代价。确定全部pre后，从n沿pre链回溯各段，累加(S_i-S_(pre_i))²即可。n可达四千万，参考程序按以下方式精确压缩存储：前缀只保存低32位，每次进位记一位，每64位保存累计进位数；用一次位计数恢复完整64位前缀。pre单调，令第i个one的位置是pre_i+i-1，整个父序列最多2n位。每8个one保存采样位置；跨度小于128的块在至多两个64位窗口选位，跨度较大的块直接存8个位置。队列索引集合也用64叉层次位图，支持前后找活索引，避免额外的四千万整数队列。

正确性说明

先同时证明贪心可行且末段最小。对任意前缀i的可行分拆，设最后断点为j。由归纳假设，贪心前缀j的末段不大于该分拆的前一段；因此j满足S_i-S_j≥L_j，属于可接候选。贪心取最大的可接pre_i，所以其末段不大于任意可行分拆的末段，且与自身前缀分拆可合法相接。由于S_i严格递增，旧的可接索引不会变回不可接，故pre_i随i单调。 末段最小还需推出平方和最优。把任意可行分拆从后往前的断点记为a_1,a_2,…，贪心断点记为g_1,g_2,…。已有g_1≥a_1；若g_t≥a_t，则由pre单调及“最大可接断点”性质，g_(t+1)=pre_(g_t)≥pre_(a_t)≥a_(t+1)。于是对每个t，贪心最大的后t段之和不超过任意可行分拆最大的后t段之和。两者各段从后往前均非增，补零后总和相同。记任意方案段长为A_t、贪心为G_t，D_t=Σ_(r≤t)(A_r-G_r)≥0且最终D=0。分部求和得Σ(A_t²-G_t²)=ΣD_t[(A_t+G_t)-(A_(t+1)+G_(t+1))]≥0，因为A、G均非增。因此贪心确为平方和最优。 队尾淘汰只删除阈值更大而索引更小的候选，它永远无法击败支配它的新候选。队首按递增阈值释放恰好所有可接候选，故队列实现与贪心定义一致。压缩结构只改变整数的表示：前缀高位等于进位数；第i个one的位置减去i-1恰为pre_i。采样块查询恢复的整数完全相同，不改变任何比较和计分。

复杂度

初始化低位前缀、进位位图、采样父序列和层次活位图均为O(n)，读生成参数O(m)。每个候选最多入队、前弹或尾弹各一次，查父下标与64位前缀都是有界常数；活位图操作O(log_64 n)，本题最多5层。总时间O(n log_64 n+m)，回溯不超过n段。所有数组严格线性空间。 满n=40000000时，低位前缀约160MB、前缀进位及rank约7.5MB、父unary位图约10MB、每8个one采样20MB。一个长采样块跨度至少128，8个one本身贡献7间隔，因此该块父增量至少121；这些增量互不重叠、合计≤n，长块位置存储至多32(n/121+1)字节。加上约5.08MB层次活位图和最多100000个生成区间，所有数组上界214357944字节，约204.43MiB，低于256MiB并留有分配器和I/O余量。

易错点

段和是非严格递增，判定用≥，阈值相等时保留索引更大的候选。a_i全为正才有严格前缀单调性。type=1的LCG乘法先用64位，取模2^30；先生成b_i再按对应(p,l,r)区间变成a_i。总前缀≤4×10^16，阈值≤8×10^16，64位可存；平方和上界小于2^111，必须在乘法前转为无符号128位。只有至多4项的段和确定小于2^32，才可直接用低32位之差；更长段必须恢复前缀高位。短采样块和未满8项的末块需分别处理。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
struct Prefix {
    vector<u32> low, rank;
    vector<u64> carry;
    u64 total = 0;
    u32 high = 0;
    explicit Prefix(int n) : low(n + 1), rank((n + 64) / 64), carry((n + 64) / 64) {
    }
    void append(int i, u32 value) {
        if ((i & 63) == 0)
            rank[i >> 6] = high;
        u32 old = (u32)total;
        total += value;
        low[i] = (u32)total;
        if (low[i] < old) {
            carry[i >> 6] |= 1ULL << (i & 63);
            ++high;
        }
    }
    u64 get(int i) const {
        unsigned bit = i & 63;
        u64 word = carry[i >> 6];
        if (bit != 63)
            word &= (1ULL << (bit + 1)) - 1;
        u64 h = rank[i >> 6];
        if (word)
            h += __builtin_popcountll(word);
        return (h << 32) | low[i];
    }
};
struct Parents {
    vector<u64> bits;
    vector<u32> sample, large;
    u32 last[8]{};
    int count = 0;
    explicit Parents(int n) : bits((2ULL * n + 63) / 64 + 1), sample((n + 7) / 8) {
        large.reserve((n / 121 + 1) * 8ULL);
    }
    void append(int parent) {
        u32 position = parent + count;
        bits[position >> 6] |= 1ULL << (position & 63);
        last[count & 7] = position;
        ++count;
        if ((count & 7) == 0) {
            int block = (count - 1) >> 3;
            if (last[7] - last[0] < 128)
                sample[block] = last[0];
            else {
                sample[block] = 0x80000000U | (u32)large.size();
                for (u32 p : last)
                    large.push_back(p);
            }
        }
    }
    u64 window(u32 p) const {
        unsigned shift = p & 63;
        u64 z = bits[p >> 6] >> shift;
        if (shift)
            z |= bits[(p >> 6) + 1] << (64 - shift);
        return z;
    }
    int get(int i) const {
        int index = i - 1, block = index >> 3, k = index & 7;
        u32 position;
        if (block == (count >> 3))
            position = last[k];
        else {
            u32 s = sample[block];
            if (s & 0x80000000U)
                position = large[(s & 0x7fffffffU) + k];
            else {
                position = s;
                u64 word = window(position);
                while (k--) {
                    word &= word - 1;
                    if (!word) {
                        position += 64;
                        word = window(position);
                    }
                }
                position += __builtin_ctzll(word);
            }
        }
        return position - index;
    }
};
struct Alive {
    vector<vector<u64>> level;
    explicit Alive(int n) {
        u64 size = n + 1;
        while (true) {
            size = (size + 63) / 64;
            level.emplace_back(size);
            if (size == 1)
                break;
        }
    }
    void set(int i) {
        for (auto &a : level) {
            int word = i >> 6;
            u64 old = a[word];
            a[word] |= 1ULL << (i & 63);
            if (old)
                break;
            i = word;
        }
    }
    void erase(int i) {
        for (auto &a : level) {
            int word = i >> 6;
            a[word] &= ~(1ULL << (i & 63));
            if (a[word])
                break;
            i = word;
        }
    }
    int previous(int l, int i) const {
        if (i < 0)
            return -1;
        int w = i >> 6;
        unsigned b = i & 63;
        u64 z = level[l][w];
        if (b != 63)
            z &= (1ULL << (b + 1)) - 1;
        if (z)
            return w * 64 + 63 - __builtin_clzll(z);
        if (l + 1 == (int)level.size())
            return -1;
        int p = previous(l + 1, w - 1);
        return p < 0 ? -1 : p * 64 + 63 - __builtin_clzll(level[l][p]);
    }
    int next(int l, int i) const {
        int w = i >> 6;
        if (w >= (int)level[l].size())
            return -1;
        unsigned b = i & 63;
        u64 z = level[l][w] & (~0ULL << b);
        if (z)
            return w * 64 + __builtin_ctzll(z);
        if (l + 1 == (int)level.size())
            return -1;
        int p = next(l + 1, w + 1);
        return p < 0 ? -1 : p * 64 + __builtin_ctzll(level[l][p]);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, type;
    cin >> n >> type;
    struct Range {
        int end;
        u32 left, right;
    };
    vector<Range> ranges;
    u64 x = 0, y = 0, z = 0, b1 = 0, b2 = 0;
    if (type == 1) {
        int m;
        cin >> x >> y >> z >> b1 >> b2 >> m;
        ranges.resize(m);
        for (auto &r : ranges)
            cin >> r.end >> r.left >> r.right;
    }
    Prefix prefix(n);
    Parents parent(n);
    Alive alive(n);
    int front = 0, back = 0, bestParent = 0, range = 0;
    u64 frontThreshold = 0, backThreshold = 0, parentSum = 0;
    auto threshold = [&](int i) {
        return 2 * prefix.get(i) - prefix.get(parent.get(i));
    };
    for (int i = 1; i <= n; i++) {
        u32 value;
        if (type == 0)
            cin >> value;
        else {
            u64 b;
            if (i == 1)
                b = b1;
            else if (i == 2)
                b = b2;
            else {
                b = (x * b2 + y * b1 + z) & ((1ULL << 30) - 1);
                b1 = b2;
                b2 = b;
            }
            while (i > ranges[range].end)
                ++range;
            u32 width = ranges[range].right - ranges[range].left + 1;
            value = (width == 1 ? 0 : b % width) + ranges[range].left;
        }
        prefix.append(i, value);
        u64 sum = prefix.total;
        while (front && frontThreshold <= sum) {
            bestParent = front;
            parentSum = prefix.get(front);
            alive.erase(front);
            if (front == back) {
                front = back = 0;
                break;
            }
            front = alive.next(0, front + 1);
            frontThreshold = threshold(front);
        }
        parent.append(bestParent);
        u64 currentThreshold = 2 * sum - parentSum;
        while (back && backThreshold >= currentThreshold) {
            int old = back;
            alive.erase(old);
            if (old == front) {
                front = back = 0;
                break;
            }
            back = alive.previous(0, old - 1);
            backThreshold = threshold(back);
        }
        alive.set(i);
        if (!front) {
            front = i;
            frontThreshold = currentThreshold;
        }
        back = i;
        backThreshold = currentThreshold;
    }
    u128 answer = 0;
    for (int i = n; i;) {
        int j = parent.get(i);
        u64 length =
            i - j <= 4 ? (u32)(prefix.low[i] - prefix.low[j]) : prefix.get(i) - prefix.get(j);
        answer += (u128)length * length;
        i = j;
    }
    string text;
    do {
        text.push_back('0' + answer % 10);
        answer /= 10;
    } while (answer);
    reverse(text.begin(), text.end());
    cout << text << '\n';
}