A47445.划分 首发原创题解

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <array>
#include <cstdio>

namespace fast_io {
    const int BUF_SIZE = 1 << 21;
    char buf[BUF_SIZE], *p1 = buf, *p2 = buf;

    inline char get_char() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUF_SIZE, stdin), p1 == p2) ? EOF : *p1++;
    }

    template<typename T>
    inline void read(T& val) {
        val = 0;
        char c = get_char();
        while (c < '0' || c > '9') {
            c = get_char();
        }
        while (c >= '0' && c <= '9') {
            val = (val << 3) + (val << 1) + (c ^ 48);
            c = get_char();
        }
    }
}

const int BIG_INT_LIMBS = 8;
const unsigned long long BASE = 1'000'000'000;
const int MOD = (1 << 30) - 1;

struct big_int {
    std::array<unsigned long long, BIG_INT_LIMBS> num;
    int len;

    big_int() : len(1) {
        num.fill(0);
    }

    explicit big_int(unsigned long long value) {
        num.fill(0);
        if (value == 0) {
            len = 1;
        } else {
            len = 0;
            while (value > 0) {
                num[len++] = value % BASE;
                value /= BASE;
            }
        }
    }

    void add(const big_int& other) {
        int max_len = std::max(this->len, other.len);
        unsigned long long carry = 0;
        for (int i = 0; i < max_len; ++i) {
            unsigned long long term1 = (i < this->len) ? this->num[i] : 0;
            unsigned long long term2 = (i < other.len) ? other.num[i] : 0;
            unsigned long long sum = term1 + term2 + carry;
            if (i < BIG_INT_LIMBS) {
                this->num[i] = sum % BASE;
            }
            carry = sum / BASE;
        }

        if (carry > 0 && max_len < BIG_INT_LIMBS) {
            this->num[max_len] = carry;
            this->len = max_len + 1;
        } else {
            this->len = max_len;
        }
    }

    void print() const {
        if (len == 0 || (len == 1 && num[0] == 0)) {
            std::cout << 0;
            return;
        }
        std::cout << num[len - 1];
        for (int i = len - 2; i >= 0; --i) {
            std::cout << std::setfill('0') << std::setw(9) << num[i];
        }
    }
};

void square(const big_int& n, big_int& result) {
    result.num.fill(0);
    if (n.len == 0 || (n.len == 1 && n.num[0] == 0)) {
        result.len = 1;
        return;
    }
    
    int new_len_upper_bound = n.len * 2;
    for (int i = 0; i < n.len; ++i) {
        for (int j = 0; j < n.len; ++j) {
            if (i + j < BIG_INT_LIMBS) {
                result.num[i + j] += n.num[i] * n.num[j];
            }
        }
    }

    unsigned long long carry = 0;
    for (int i = 0; i < new_len_upper_bound && i < BIG_INT_LIMBS; ++i) {
        result.num[i] += carry;
        carry = result.num[i] / BASE;
        result.num[i] %= BASE;
    }
    
    result.len = std::min(new_len_upper_bound, BIG_INT_LIMBS);
    while (result.len > 1 && result.num[result.len - 1] == 0) {
        result.len--;
    }
}

const int MAX_N = 40000000 + 3;
std::vector<unsigned long long> prefix_sum(MAX_N);
std::vector<int> parent(MAX_N);
std::vector<int> q_deque(MAX_N);

void solve() {
    int n, type;
    fast_io::read(n);
    fast_io::read(type);

    if (type == 1) {
        unsigned long long x, y;
        int z, m;
        fast_io::read(x);
        fast_io::read(y);
        fast_io::read(z);
        std::vector<long long> b(n + 1);
        fast_io::read(b[1]);
        fast_io::read(b[2]);
        fast_io::read(m);
        
        for (int i = 3; i <= n; ++i) {
            b[i] = ((x * b[i - 1]) & MOD) + ((y * b[i - 2]) & MOD) + z & MOD;
        }

        int current_p = 0;
        for (int j = 1; j <= m; ++j) {
            int p_j, l, r;
            fast_io::read(p_j);
            fast_io::read(l);
            fast_io::read(r);
            long long range_len = r - l + 1;
            for (int i = current_p + 1; i <= p_j; ++i) {
                long long a = b[i] % range_len + l;
                prefix_sum[i] = prefix_sum[i - 1] + a;
            }
            current_p = p_j;
        }
    } else {
        for (int i = 1; i <= n; ++i) {
            long long a;
            fast_io::read(a);
            prefix_sum[i] = prefix_sum[i - 1] + a;
        }
    }

    int head = 1, tail = 1;
    q_deque[1] = 0;

    auto get_value = [&](int index) {
        return (prefix_sum[index] << 1) - prefix_sum[parent[index]];
    };

    for (int i = 1; i <= n; ++i) {
        while (head < tail && get_value(q_deque[head + 1]) <= prefix_sum[i]) {
            head++;
        }
        parent[i] = q_deque[head];
        
        while (head <= tail && get_value(q_deque[tail]) >= get_value(i)) {
            tail--;
        }
        q_deque[++tail] = i;
    }

    big_int total_sum;
    big_int squared_val;
    for (int pos = n; pos > 0; pos = parent[pos]) {
        unsigned long long val = prefix_sum[pos] - prefix_sum[parent[pos]];
        big_int segment_val(val);
        square(segment_val, squared_val);
        total_sum.add(squared_val);
    }

    total_sum.print();
    std::cout << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}