OI XXXI - cia (Persistent_seg_tree)

// https://szkopul.edu.pl/problemset/problem/q6f5K7O79TpYR7yuZVrQpy_d/site/?key=statement

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

#pragma GCC optimize("O3")

constexpr int BUF_SZ = 1 << 18;
struct FastIO {
    char in_buf[BUF_SZ], out_buf[BUF_SZ];
    int in_ptr, in_len, out_ptr;
    FastIO() : in_ptr(0), in_len(0), out_ptr(0) {}

    inline char get_char() {
        if (in_ptr >= in_len) {
            in_ptr = 0;
            in_len = fread(in_buf, 1, BUF_SZ, stdin);
            if (in_len == 0) return 0;
        }
        return in_buf[in_ptr++];
    }

    template<typename T>
    inline void read(T& x) {
        x = 0;
        char c = get_char();
        while (c < '0' || c > '9')
            c = get_char();
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = get_char();
        }
    }

    inline void put_char(char c) {
        if (out_ptr >= BUF_SZ) flush();
        out_buf[out_ptr++] = c;
    }

    template<typename T>
    inline void write(T x) {
        if (x == 0) {
            put_char('0');
            return;
        }
        static char temp[25];
        int idx = 0;
        while (x > 0) {
            temp[idx++] = (x % 10) + '0';
            x /= 10;
        }
        while (idx > 0)
            put_char(temp[--idx]);
    }

    inline void flush() {
        fwrite(out_buf, 1, out_ptr, stdout);
        out_ptr = 0;
    }
    ~FastIO() { flush(); }
} io;

constexpr int MAXN = 1001000;
constexpr int MAX_NODES = 12000000;

struct Node {
    int l, r;
    int cnt;
    long long sum;
} tree[MAX_NODES];

int roots[MAXN / 2 + 5];
int node_cnt = 0;

int update(int prev, int l, int r, int val_idx, int real_val) {
    int id = ++node_cnt;
    tree[id] = tree[prev];
    tree[id].cnt++;
    tree[id].sum += real_val;

    if (l == r) return id;

    int mid = (l + r) >> 1;
    if (val_idx <= mid)
        tree[id].l = update(tree[prev].l, l, mid, val_idx, real_val);
    else
        tree[id].r = update(tree[prev].r, mid + 1, r, val_idx, real_val);

    return id;
}

long long query(int nodeL, int nodeR, int l, int r, int k) {
    int available = tree[nodeR].cnt - tree[nodeL].cnt;
    if (available <= k) {
        return tree[nodeR].sum - tree[nodeL].sum;
    }

    if (l == r) {
        long long val = (tree[nodeR].sum - tree[nodeL].sum) / (available ? available : 1);
        return val * k;
    }

    int mid = (l + r) >> 1;
    int right_count = tree[tree[nodeR].r].cnt - tree[tree[nodeL].r].cnt;

    if (k <= right_count) {
        return query(tree[nodeL].r, tree[nodeR].r, mid + 1, r, k);
    } else {
        long long right_sum = tree[tree[nodeR].r].sum - tree[tree[nodeL].r].sum;
        return right_sum + query(tree[nodeL].l, tree[nodeR].l, l, mid, k - right_count);
    }
}

int d[MAXN];
long long pref[MAXN];

int main() {
    int n, q;
    io.read(n);
    io.read(q);

    std::vector<int> distinct_vals;
    distinct_vals.reserve(n / 2 + 1);

    std::vector<int> compacted_vals;
    compacted_vals.reserve(n / 2 + 1);

    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        io.read(d[i]);
        pref[i] = pref[i - 1] + d[i];
        if (i & 1) {
            distinct_vals.push_back(d[i]);
            compacted_vals.push_back(d[i]);
        }
    }

    std::sort(distinct_vals.begin(), distinct_vals.end());
    distinct_vals.erase(std::unique(distinct_vals.begin(), distinct_vals.end()), distinct_vals.end());
    int m = distinct_vals.size();

    roots[0] = 0;
    for (size_t i = 0; i < compacted_vals.size(); i++) {
        int val = compacted_vals[i];
        int rank = std::lower_bound(distinct_vals.begin(), distinct_vals.end(), val) - distinct_vals.begin();
        roots[i + 1] = update(roots[i], 0, m - 1, rank, val);
    }

    for (int i = 0; i < q; i++) {
        long long l, r;
        int k;
        io.read(l);
        io.read(r);
        io.read(k);

        int s_start = std::lower_bound(pref, pref + n + 1, l) - pref;
        int s_end = std::lower_bound(pref, pref + n + 1, r) - pref;

        if (s_start == s_end) {
            if (s_start & 1) {
                io.write(r - l + 1);
            } else {
                io.write(0);
            }
            io.put_char('\n');
            continue;
        }

        long long len_L = 0;
        if (s_start & 1) len_L = std::max(0LL, pref[s_start] - l + 1);

        long long len_R = 0;
        if (s_end & 1) len_R = std::max(0LL, r - pref[s_end - 1]);

        int q_l = s_start + 1;
        int q_r = s_end - 1;

        auto get_k_sum = [&](int k_cuts) -> long long {
            if (k_cuts <= 0 || q_l > q_r) return 0;

            int odd_start = (q_l & 1) ? q_l : q_l + 1;
            int odd_end = (q_r & 1) ? q_r : q_r - 1;

            if (odd_start > odd_end) return 0;

            int c_l = (odd_start - 1) >> 1;
            int c_r = (odd_end - 1) >> 1;

            return query(roots[c_l], roots[c_r + 1], 0, m - 1, k_cuts);
        };

        long long ans = 0;

        ans = std::max(ans, get_k_sum(k / 2));

        if (k >= 1) {
            long long base = std::max(len_L, len_R);
            ans = std::max(ans, base + get_k_sum((k - 1) / 2));
        }

        if (k >= 2) {
            ans = std::max(ans, len_L + len_R + get_k_sum((k - 2) / 2));
        }

        io.write(ans);
        io.put_char('\n');
    }

    return 0;
}