Bài toán yêu cầu xử lý các truy vấn, mỗi truy vấn cho hai số l và r, cần tính tổng giá trị nhỏ nhất trên tất cả các đoạn con của đoạn [l, r]. Với các truy vấn có thể xử lý offline, ta có thể áp dụng thuật toán Mo.

Vấn đề chính là tính đóng góp khi mở rộng đầu phải thêm một phần tử. Các đoạn con mới sinh ra đều có đầu phải là r. Ta cần tính tổng giá trị nhỏ nhất của các đoạn có đầu phải là r và đầu trái nằm trong [l, r]. Ký hiệu dp[l, r] là tổng này. Ta có công thức truy hồi:

dp[l, r] = dp[l, li[i]] + (i - li[i]) * a[i]

Trong đó li[i] là vị trí đầu tiên bên trái i có giá trị nhỏ hơn a[i], tìm được bằng stack đơn điệu. Điểm dừng của quá trình truy hồi là dp[l, p] = a[p] * (p - l + 1) với p là vị trí giá trị nhỏ nhất trong [l, r].

Vì dp phụ thuộc vào l nên không thể tiền xử lý cho mọi l. Tuy nhiên, bước nhảy và giá trị gia tăng chỉ phụ thuộc vào i. Cuối cùng ta luôn chuyển đến vị trí x rồi đến p. Công thức dp[l, r] = a[p] * (p - l + 1) + a[x] * (x - p) + ... + a[r] * (r - li[r]). Phần a[p] * (p - l + 1) phụ thuộc l, phần còn lại thì không. Đặt l = 1, phần còn lại là dp[1, r] - dp[1, p].

Ta tiền xử lý f[i] là tổng giá trị nhỏ nhất với đầu phải i và đầu trái trong [1, i]. Khi đó, với đầu phải r và đầu trái trong [l, r], kết quả là f[r] - f[p] + a[p] * (p - l + 1). Giải quyết xong trường hợp mở rộng đầu phải. Với đầu trái, chỉ cần đảo ngược dãy.

Lưu ý

• Luôn mở rộng vùng trước khi thu hẹp để tránh l > r khi tính toán.
• Bảng ST cần đủ độ chính xác và xử lý tràn chỉ số khi i + (1 << (j - 1)) vượt quá n.

#include <bits/stdc++.h>
using namespace std;
#define N 100000 + 5
#define M 20 + 5
#define rep(i, l, r) for(int i = l; i <= r; ++i)
#define dep(i, l, r) for(int i = r; i >= l; --i)
struct Query {
    int l, r, id;
} q[N];
long long cur, result[N], pref[N], suff[N];
int n, leftPtr, rightPtr, numQ, stkTop, blockSize, arr[N], leftSmall[N], rightSmall[N], stk[N], sparse[3 * N][M];
int readInt() {
    char ch; int val = 0, sign = 1;
    ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-') sign = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') val = val * 10 + ch - '0', ch = getchar();
    return val * sign;
}
bool cmpMo(Query a, Query b) {
    if (a.l / blockSize != b.l / blockSize) return a.l < b.l;
    return ((a.l / blockSize) & 1) ? (a.r < b.r) : (a.r > b.r);
}
int getMinPos(int l, int r) {
    int k = log2(r - l + 1);
    if (arr[sparse[l][k]] < arr[sparse[r - (1 << k) + 1][k]]) return sparse[l][k];
    return sparse[r - (1 << k) + 1][k];
}
void addLeft(int pos, int delta) {
    int minPos = getMinPos(pos, rightPtr);
    cur += 1ll * delta * (suff[pos] - suff[minPos] + 1ll * arr[minPos] * (rightPtr - minPos + 1));
}
void addRight(int pos, int delta) {
    int minPos = getMinPos(leftPtr, pos);
    cur += 1ll * delta * (pref[pos] - pref[minPos] + 1ll * arr[minPos] * (minPos - leftPtr + 1));
}
int main() {
    n = readInt(), numQ = readInt(), blockSize = sqrt(n);
    rep(i, 1, n) arr[i] = readInt(), sparse[i][0] = i;
    rep(j, 1, 17) rep(i, 1, n) {
        if (arr[sparse[i][j - 1]] < arr[sparse[i + (1 << (j - 1))][j - 1]]) sparse[i][j] = sparse[i][j - 1];
        else sparse[i][j] = sparse[i + (1 << (j - 1))][j - 1];
    }
    // Tìm leftSmall
    dep(i, 1, n) {
        while (stkTop && arr[stk[stkTop]] > arr[i]) {
            leftSmall[stk[stkTop]] = i;
            --stkTop;
        }
        stk[++stkTop] = i;
    }
    stkTop = 0;
    // Tìm rightSmall
    rep(i, 1, n) {
        while (stkTop && arr[stk[stkTop]] > arr[i]) {
            rightSmall[stk[stkTop]] = i;
            --stkTop;
        }
        stk[++stkTop] = i;
    }
    rep(i, 1, n) pref[i] = pref[leftSmall[i]] + 1ll * (i - leftSmall[i]) * arr[i];
    dep(i, 1, n) suff[i] = suff[rightSmall[i]] + 1ll * (rightSmall[i] - i) * arr[i];
    rep(i, 1, numQ) q[i].l = readInt(), q[i].r = readInt(), q[i].id = i;
    sort(q + 1, q + numQ + 1, cmpMo);
    leftPtr = 1, rightPtr = 0;
    rep(i, 1, numQ) {
        while (rightPtr < q[i].r) addRight(++rightPtr, 1);
        while (leftPtr > q[i].l) addLeft(--leftPtr, 1);
        while (rightPtr > q[i].r) addRight(rightPtr--, -1);
        while (leftPtr < q[i].l) addLeft(leftPtr++, -1);
        result[q[i].id] = cur;
    }
    rep(i, 1, numQ) printf("%lld\n", result[i]);
    return 0;
}

Có thể giải bài toán mà không cần Mo. Với mỗi truy vấn, ta tính tổng:

∑_{i=l}^{r} dp[l, i]

Chia làm ba phần: đoạn chứa vị trí p (giá trị nhỏ nhất trong [l, r]), đoạn bên phải p, đoạn bên trái p. Kết quả là:

a[p] * (p - l + 1) * (r - p + 1) + (pre[r] - pre[p] - f[p] * (r - p)) + (suff[l] - suff[p] - g[p] * (p - l))

Với f, g là các mảng đã tính, pre và suff là tổng tiền tố tương ứng.

#include <bits/stdc++.h>
using namespace std;
#define N 100000 + 5
#define M 20 + 5
#define rep(i, l, r) for(int i = l; i <= r; ++i)
#define dep(i, l, r) for(int i = r; i >= l; --i)
unsigned long long S, A, B, C, ans, lastAns = 0, f[N], g[N], pref[N], suff[N];
int n, leftPtr, rightPtr, numQ, stkTop, type, arr[N], leftSmall[N], rightSmall[N], stk[N], sparse[3 * N][M];
int readInt() {
    char ch; int val = 0, sign = 1;
    ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-') sign = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') val = val * 10 + ch - '0', ch = getchar();
    return val * sign;
}
unsigned long long Rand() {
    return S ^= (A + B * lastAns) % C;
}
int getMinPos(int l, int r) {
    int k = log2(r - l + 1);
    if (arr[sparse[l][k]] < arr[sparse[r - (1 << k) + 1][k]]) return sparse[l][k];
    return sparse[r - (1 << k) + 1][k];
}
int main() {
    n = readInt(), numQ = readInt(), type = readInt();
    rep(i, 1, n) arr[i] = readInt(), sparse[i][0] = i;
    rep(j, 1, 17) rep(i, 1, n) {
        if (arr[sparse[i][j - 1]] < arr[sparse[i + (1 << (j - 1))][j - 1]]) sparse[i][j] = sparse[i][j - 1];
        else sparse[i][j] = sparse[i + (1 << (j - 1))][j - 1];
    }
    dep(i, 1, n) {
        while (stkTop && arr[stk[stkTop]] > arr[i]) {
            leftSmall[stk[stkTop]] = i;
            --stkTop;
        }
        stk[++stkTop] = i;
    }
    stkTop = 0;
    rep(i, 1, n) {
        while (stkTop && arr[stk[stkTop]] > arr[i]) {
            rightSmall[stk[stkTop]] = i;
            --stkTop;
        }
        stk[++stkTop] = i;
    }
    rep(i, 1, n) f[i] = f[leftSmall[i]] + 1ull * (i - leftSmall[i]) * arr[i], pref[i] = pref[i - 1] + f[i];
    dep(i, 1, n) g[i] = g[rightSmall[i]] + 1ull * (rightSmall[i] - i) * arr[i], suff[i] = suff[i + 1] + g[i];
    if (type) S = readInt(), A = readInt(), B = readInt(), C = readInt();
    while (numQ--) {
        int l, r;
        if (!type) l = readInt(), r = readInt();
        else {
            l = Rand() % n + 1, r = Rand() % n + 1;
            if (l > r) swap(l, r);
        }
        int p = getMinPos(l, r);
        lastAns = pref[r] - pref[p - 1] - f[p] * (r - p + 1);
        lastAns += suff[l] - suff[p] - g[p] * (p - l);
        lastAns += 1ull * (r - p + 1) * (p - l + 1) * arr[p];
        ans ^= lastAns;
    }
    printf("%llu", ans);
    return 0;
}