快速排序

形式化题目

按题面（快速排序的比较次数/划分计数模型）给定序列与询问，求相应计数（对 $10^9+7$ 取模）。核心操作是「区间加、区间求和」的在线维护。

正解

思路

1. 双树状数组区间加区间和

维护差分数组 $d$ 的两个 BIT：

$b_1$ 存 $d_i$ ；
$b_2$ 存 $d_i\cdot(i-1)$ 。

前 $i$ 项原数组和 $= i\cdot\sum_{k\le i} b_1(k) - \sum_{k\le i} b_2(k)$ 。区间 $[l,r]$ 加 $\delta$ 时在 $b_1$ 的 $l$ 、 $r+1$ 处打 $\pm\delta$ ， $b_2$ 对应 $\pm\delta\cdot(l-1)$ 、 $\mp\delta\cdot r$ 。

2. 计数流程

按题面把快速排序的递归/比较过程转成对序列区间的增量操作与查询，用上述结构在线维护，单次 $O(\log n)$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 18:44
# update_at: 2026-10-02 19:40

import sys
from array import array

MOD = 10**9 + 7  # 题面要求的模数


def range_add(b1: array, b2: array, l: int, r: int, delta: int) -> None:
    """区间 [l, r] 加 delta：差分树打两处标记，前缀和处再还原成区间和。

    b1 存差分量本身，b2 存差分量乘 (下标-1)，于是前 i 项和 = i·Σb1 − Σb2。
    """
    size = len(b1) - 1
    lo, hi = delta * (l - 1), delta * r  # b2 的两处增量：l 处 +delta*(l-1)，r+1 处 -delta*r
    i = l
    while i <= size:
        b1[i] += delta
        b2[i] += lo
        i += i & -i
    i = r + 1
    while i <= size:
        b1[i] -= delta
        b2[i] -= hi
        i += i & -i


def prefix_sum(b1: array, b2: array, i: int) -> int:
    """下标 1..i 的元素和（含全部区间加修正）：i·Σb1 − Σb2。"""
    s1 = s2 = 0
    j = i
    while j:
        s1 += b1[j]
        s2 += b2[j]
        j &= j - 1  # 清掉最低位 1，等价于 j -= j & -j
    return s1 * i - s2


def catalan_table(n: int) -> array:
    """方案数表 cnt[t] = C(2t, t)/(t+1)：递推 C_t = C_{t-1}·(4t-2)/(t+1)，顺带线性求逆元。"""
    inv = array("q", [0]) * (n + 2)
    inv[1] = 1
    for i in range(2, n + 2):
        inv[i] = MOD - MOD // i * inv[MOD % i] % MOD
    cnt = array("q", [0]) * (n + 1)
    cnt[1] = 1  # 区间长度最短为 2，t 最小为 1
    for t in range(2, n + 1):
        cnt[t] = cnt[t - 1] * (4 * t - 2) % MOD * inv[t + 1] % MOD
    return cnt


def solve() -> None:
    data = sys.stdin.buffer
    n, m = map(int, data.readline().split())
    size = n + n  # 序列长度 2n，下标 1..2n

    # 静态前缀和：s0 覆盖全序列；se0 把偶数位 i=2j 压成槽 j 后的前缀和。
    # 奇数位的和不必再建一棵树：奇数位 = 全序列 - 偶数位。
    s0 = array("q", [0])
    se0 = array("q", [0])
    total = even_total = 0
    for i, x in enumerate(map(int, data.readline().split()), 1):
        total += x
        s0.append(total)
        if i % 2 == 0:
            even_total += x  # 只累计偶数位，不能直接抄全序列前缀和
            se0.append(even_total)

    u = array("q", [0]) * (size + 1)  # 全序列区间加：差分量
    v = array("q", [0]) * (size + 1)  # 全序列区间加：差分量 * (下标-1)
    ue = array("q", [0]) * (n + 1)  # 偶数位（按槽压缩）区间加：差分量
    ve = array("q", [0]) * (n + 1)  # 偶数位（按槽压缩）区间加：差分量 * (槽-1)

    cnt = catalan_table(n)  # 方案数只取决于区间长度，与数值无关
    out: list[str] = []

    for _ in range(m):
        op = data.readline().split()
        l, r = int(op[1]), int(op[2])
        if op[0] == b"0":  # 0 l r val：区间加（保证不破坏有序性）
            val = int(op[3])
            range_add(u, v, l, r, val)
            even_first = l + (l & 1)  # [l, r] 内第一个偶数位
            even_last = r - (r & 1)  # [l, r] 内最后一个偶数位
            if even_first <= even_last:
                range_add(ue, ve, even_first // 2, even_last // 2, val)
        else:  # 1 l r：求区间分离后的最大差距、最小差距和方案数
            t = (r - l + 1) >> 1  # 区间长度的一半 = 每个子序列的长度
            mid = r - t  # 后 t 个的起点 - 1 = 前 t 个的终点，两端各取一半正好错开
            high = s0[r] + prefix_sum(u, v, r)
            near_mid = s0[mid] + prefix_sum(u, v, mid)
            low = s0[l - 1] + prefix_sum(u, v, l - 1)
            gap = high - 2 * near_mid + low  # 最大差距 = 后 t 个之和 - 前 t 个之和
            even = (
                se0[r >> 1] + prefix_sum(ue, ve, r >> 1)
                - se0[(l - 1) >> 1] - prefix_sum(ue, ve, (l - 1) >> 1)
            )
            full = high - low  # 区间总和 = 奇数位之和 + 偶数位之和
            # 最小差距 = 相邻配对之差和；l 为奇数时偶数位在每对后面，l 为偶数时相反
            near = even + even - full if l & 1 else full - even - even
            out.append(f"{gap % MOD} {near % MOD} {cnt[t]}")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 18:35
 * update_at: 2026-10-04 23:14
 */
// main.cpp：序列长度 2n 且始终有序，询问把区间 [l,r]（长度 2t）分离成两个长度为 t 的子序列，
// 求所有分离方式中「差距」的最大值、最小值与方案数，区间还会整体加 val。
//
// 三条结论（序列有序是关键）：
// 1. 最大差距：让前 t 个整体当小的那半、后 t 个当大的那半，差距 = sum(后 t 个) - sum(前 t 个)。
// 2. 最小差距：相邻两两配对 (l,l+1),(l+2,l+3),... 的差之和；只需知道区间内偶数下标元素之和，
//    就能由区间总和推出它（l 为奇数时 = 2*偶数和 - 总和，否则 = 总和 - 2*偶数和）。
// 3. 方案数只与 t 有关，等于第 t 个卡特兰数 C_t。
//
// 区间加 + 区间求和用双树状数组维护差分：b1 存 d_i，b2 存 d_i*(i-1)，
// 则前 i 项和 = i*sum(b1) - sum(b2)。偶数下标元素之和再按 2j -> j 压缩到一棵同样结构的树里。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1100005; // 2n 最大 1e6（n <= 5e5）
const int MAXH = 550005;  // n 最大 5e5
const ll MOD = 1000000007;

int n, m;
int len; // 序列长度 2n

ll s0[MAXN];   // s0[i]：原序列 1..i 的初始前缀和
ll se0[MAXH];  // se0[j]：偶数下标元素 2,4,...,2j 的初始前缀和
ll bit1[MAXN]; // 全序列区间加：差分量 d_i
ll bit2[MAXN]; // 全序列区间加：d_i*(i-1)，用来还原区间和
ll bite1[MAXH]; // 偶数下标（按 2j -> j 压缩）区间加：差分量
ll bite2[MAXH]; // 偶数下标压缩后区间加：差分量*(j-1)
ll inv[MAXH];   // inv[i]：i 在模 MOD 下的逆元
ll cnt[MAXH];   // cnt[t]：长度为 2t 的区间的分离方案数，即卡特兰数 C_t

// 在双树状数组上把区间 [l,r] 整体加上 delta，size 为这棵树对应的下标上限
void range_add(ll *b1, ll *b2, int size, int l, int r, ll delta) {
    ll add_l = delta * (l - 1); // b2 在 l 处的增量
    ll add_r = delta * r;       // b2 在 r+1 处的增量
    for (int i = l; i <= size; i += i & -i) {
        b1[i] += delta;
        b2[i] += add_l;
    }
    for (int i = r + 1; i <= size; i += i & -i) {
        b1[i] -= delta;
        b2[i] -= add_r;
    }
}

// 区间加之后，下标 1..i 的元素和 = i*sum(b1) - sum(b2)
ll prefix_sum(ll *b1, ll *b2, int i) {
    ll sum1 = 0, sum2 = 0;
    for (int j = i; j > 0; j -= j & -j) {
        sum1 += b1[j];
        sum2 += b2[j];
    }
    return sum1 * i - sum2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    len = 2 * n;

    ll total = 0;      // 全序列前缀和
    ll even_total = 0; // 偶数下标元素前缀和
    for (int i = 1; i <= len; i++) {
        ll x;
        cin >> x;
        total += x;
        s0[i] = total;
        if (i % 2 == 0) {
            even_total += x;
            se0[i / 2] = even_total;
        }
    }

    // 线性求逆元后递推卡特兰数：C_t = C_{t-1} * (4t-2) / (t+1)
    inv[1] = 1;
    for (int i = 2; i <= n + 1; i++) {
        inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
    }
    cnt[1] = 1; // 区间最短为 2，t 从 1 开始
    for (int t = 2; t <= n; t++) {
        cnt[t] = cnt[t - 1] * (4 * t - 2) % MOD * inv[t + 1] % MOD;
    }

    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) {
            ll val;
            cin >> val;
            range_add(bit1, bit2, len, l, r, val);
            int even_first = l + (l & 1);  // [l,r] 内第一个偶数下标
            int even_last = r - (r & 1);   // [l,r] 内最后一个偶数下标
            if (even_first <= even_last) {
                range_add(bite1, bite2, n, even_first / 2, even_last / 2, val);
            }
        } else {
            int t = (r - l + 1) / 2; // 每个子序列的长度
            int mid = r - t;         // 前后各取一半的分界点
            ll high = s0[r] + prefix_sum(bit1, bit2, r);
            ll near_mid = s0[mid] + prefix_sum(bit1, bit2, mid);
            ll low = s0[l - 1] + prefix_sum(bit1, bit2, l - 1);
            ll gap = high - 2 * near_mid + low; // 最大差距
            ll even = se0[r / 2] + prefix_sum(bite1, bite2, r / 2)
                    - se0[(l - 1) / 2] - prefix_sum(bite1, bite2, (l - 1) / 2);
            ll full = high - low; // 区间总和
            ll near = (l & 1) ? even + even - full : full - even - even; // 最小差距
            cout << (gap % MOD + MOD) % MOD << ' '
                 << (near % MOD + MOD) % MOD << ' '
                 << cnt[t] << '\n';
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(m\log n)$ 。
空间复杂度： $O(n)$ 。

总结

区间加 + 区间和的标准做法：双 BIT 差分（ $b_1$ , $b_2 = d_i(i-1)$ ）。
任何「批量加值、批量求和」的计数问题都能套用此结构。

目录

形式化题目

正解

思路

1. 双树状数组区间加区间和

2. 计数流程

代码

复杂度

总结