[NOIP2025] 序列询问

GitHub 跳转原题关系图返回列表

把包含位置且长度受限的区间转成前缀和坐标中的梯形区域，用 ST 表和单调队列线性求每个询问。

OJ: luogu

题目 ID: P14638

难度:省选/NOI-

标签:数据结构ST表单调队列前缀和

日期: 2026-06-22 20:34

题意

给定长度为 n 的序列 a。每次询问给出长度范围 [L,R]。

对每个位置 i，令 k_i 表示所有包含 i、且长度在 [L,R] 内的子区间中，区间和的最大值。

样例输出对应的聚合方式是：

text

1(1*k_1) xor (2*k_2) xor ... xor (n*k_n)

使用 unsigned 64 位输出。

思路

先看一个可以直接验证想法的朴素解：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, q;
long long a[MAXN], prefix_sum[MAXN];

long long range_sum(int l, int r) {
    return prefix_sum[r] - prefix_sum[l - 1];
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;

        unsigned long long result = 0;
        for (int i = 1; i <= n; i++) {
            long long best = -(1LL << 60);
            for (int l = 1; l <= i; l++) {
                for (int r = i; r <= n; r++) {
                    int len = r - l + 1;
                    if (L <= len && len <= R) {
                        best = max(best, range_sum(l, r));
                    }
                }
            }
            long long product = best * (long long)i;
            result ^= (unsigned long long)product;
        }

        cout << result << '\n';
    }

    return 0;
}

暴力会对每个位置枚举所有包含它的区间，检查长度并取最大区间和。这个做法清楚，但单个询问就可能达到二次复杂度。

设前缀和为：

text

1
2s[0] = 0
s[i] = a[1] + ... + a[i]

区间 [l,r] 可以写成前缀坐标：

text

1
2x = l - 1, y = r
sum(l,r) = s[y] - s[x]

它包含位置 i，并且长度在 [L,R] 内，等价于：

text

1
2x < i <= y
L <= y - x <= R

所以对固定 i，问题是在一个梯形区域里最大化 s[y] - s[x]。

代码把这个梯形拆成几个可以快速处理的块：

固定 x 后，y 的范围是一段区间，用 ST 表查询 max s[y]，再用单调队列维护当前位置可用的 x；
固定 y 的块类似，用 ST 表查询 min s[x]；
中间块中，x 和 y 的范围可以分开，答案就是 max s[y] - min s[x]。

这样每个询问只需要线性扫描若干遍数组。

代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
const int LOG = 17;
const long long INF = (1LL << 62);

int n, q;
long long prefix_sum[MAXN];
long long max_st[LOG][MAXN], min_st[LOG][MAXN];
int lg2_value[MAXN];

long long best_left[MAXN], best_right[MAXN], best_start[MAXN], answer_pos[MAXN];
int que[MAXN];

void build_st() {
    lg2_value[1] = 0;
    for (int i = 2; i <= n + 1; i++) {
        lg2_value[i] = lg2_value[i >> 1] + 1;
    }

    for (int i = 0; i <= n; i++) {
        max_st[0][i] = prefix_sum[i];
        min_st[0][i] = prefix_sum[i];
    }

    for (int j = 1; j < LOG; j++) {
        int len = 1 << j;
        for (int i = 0; i + len - 1 <= n; i++) {
            max_st[j][i] = max(max_st[j - 1][i], max_st[j - 1][i + (len >> 1)]);
            min_st[j][i] = min(min_st[j - 1][i], min_st[j - 1][i + (len >> 1)]);
        }
    }
}

long long range_max_prefix(int l, int r) {
    l = max(l, 0);
    r = min(r, n);
    if (l > r) {
        return -INF;
    }
    int len = r - l + 1;
    int lg = lg2_value[len];
    return max(max_st[lg][l], max_st[lg][r - (1 << lg) + 1]);
}

long long range_min_prefix(int l, int r) {
    l = max(l, 0);
    r = min(r, n);
    if (l > r) {
        return INF;
    }
    int len = r - l + 1;
    int lg = lg2_value[len];
    return min(min_st[lg][l], min_st[lg][r - (1 << lg) + 1]);
}

void push_max_queue(int &head, int &tail, long long value_array[], int pos) {
    while (head <= tail && value_array[que[tail]] <= value_array[pos]) {
        tail--;
    }
    que[++tail] = pos;
}

unsigned long long solve_query(int L, int R) {
    for (int i = 0; i <= n + 2; i++) {
        best_left[i] = -INF;
        best_right[i] = -INF;
        best_start[i] = -INF;
        answer_pos[i] = -INF;
    }

    // 右侧平行四边形：固定左前缀位置 x，右端点在 [x+L, x+R]。
    for (int x = 0; x + L <= n; x++) {
        best_start[x] = range_max_prefix(x + L, x + R) - prefix_sum[x];
    }

    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && que[head] < i - L) {
            head++;
        }
        push_max_queue(head, tail, best_start, i - 1);
        answer_pos[i] = best_start[que[head]];
    }

    int half = R - L + 1;
    if (half & 1) {
        half++;
    }
    half >>= 1;

    // 左侧三角形拆出来的第一块。
    for (int x = 0; x + L + half <= n; x++) {
        best_left[x] = range_max_prefix(x + L + half, x + R) - prefix_sum[x];
    }

    head = 1;
    tail = 0;
    for (int i = L; i <= n; i++) {
        int expired = i - L - half;
        int add_pos = i - L;
        while (head <= tail && que[head] <= expired) {
            head++;
        }
        push_max_queue(head, tail, best_left, add_pos);
        if (head <= tail) {
            answer_pos[i] = max(answer_pos[i], best_left[que[head]]);
        }
    }

    // 左侧三角形拆出来的第二块。
    for (int y = L + half; y <= n; y++) {
        best_right[y] = prefix_sum[y] - range_min_prefix(y - R, y - L - half);
    }

    head = 1;
    tail = 0;
    for (int i = L + 1; i <= n; i++) {
        int add_pos = i + half - 1;
        while (head <= tail && que[head] < i) {
            head++;
        }
        if (add_pos <= n) {
            push_max_queue(head, tail, best_right, add_pos);
        }
        if (head <= tail) {
            answer_pos[i] = max(answer_pos[i], best_right[que[head]]);
        }
    }

    // 中间正方形：左右端点可以分开取最优前缀最大值和最小值。
    for (int i = L; i <= n; i++) {
        long long value = range_max_prefix(i, i + half - 1)
                        - range_min_prefix(i - L - half + 1, i - L);
        answer_pos[i] = max(answer_pos[i], value);
    }

    unsigned long long result = 0;
    for (int i = 1; i <= n; i++) {
        long long product = answer_pos[i] * (long long)i;
        result ^= (unsigned long long)product;
    }
    return result;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix_sum[i] = prefix_sum[i - 1] + x;
    }

    build_st();

    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        cout << solve_query(L, R) << '\n';
    }

    return 0;
}

复杂度

预处理前缀和的最大/最小 ST 表需要：

text

1O(n log n)

每个询问 $O(n)$ ，所以总时间复杂度为：

text

1O(n log n + nq)

空间复杂度为 $O(n log n)$ 。

总结

本题的关键不是直接枚举区间，而是把区间转成前缀和坐标中的点 (x,y)。

包含位置和长度限制共同形成一个梯形区域。把这个区域拆成几块后，每块都能用 ST 表和单调队列在线性时间内更新所有 k_i。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P14638 [NOIP2025] 序列询问

题目背景

额外提供了 1 秒的时限。

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$ 。

有 $q$ 次询问，其中第 $j$ ( $1 \le j \le q$ ) 次询问将会给出 $L_j, R_j$ ( $1 \le L_j \le R_j \le n$ )。定义区间 $[l, r]$ ( $1 \le l \le r \le n$ ) 是极好的，当且仅当区间 $[l, r]$ 的长度在 $[L_j, R_j]$ 内，即 $L_j \le r - l + 1 \le R_j$ 。定义区间 $[l, r]$ ( $1 \le l \le r \le n$ ) 的权值为 $\sum_{i=l}^{r} a_i$ 。对于所有 $i = 1, 2, \ldots, n$ ，求出所有包含 $i$ 的极好区间的最大权值，即 $\max_{1 \le l \le i \le r \le n} \{ \sum_{i=l}^{r} a_i \mid L_j \le r - l + 1 \le R_j \}$ 。

输入格式

输入的第一行包含一个正整数 $n$ ，表示序列长度。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 。

输入的第三行包含一个正整数 $q$ ，表示询问次数。

输入的第 $j + 3$ ( $1 \le j \le q$ ) 行包含两个正整数 $L_j, R_j$ ，表示第 $j$ 次询问。

输出格式

对于每次询问，设包含 $i$ ( $1 \le i \le n$ ) 的极好区间的最大权值为 $k_i$ ，输出一行一个非负整数，表示 $\bigoplus_{i=1}^{n} \left( (i \times k_i) \bmod 2^{64} \right)$ ，其中 $\oplus$ 表示二进制按位异或。注意：对于任意整数 $x$ ，存在唯一的非负整数 $x'$ 满足 $x' \equiv x \pmod{2^{64}}$ 且 $0 \le x' \le 2^{64} - 1$ ，则记 $x \bmod 2^{64} = x'$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
318446744073709551603
8
4

说明/提示

【样例 1 解释】

对于第 $1$ 次询问：

包含 $1$ 的极好区间为 $[1,1]$ 和 $[1,2]$ ，权值分别为 $2,6$ ；
包含 $2$ 的极好区间为 $[1,2]$ ， $[2,2]$ 和 $[2,3]$ ，权值分别为 $6,4,-1$ ；
包含 $3$ 的极好区间为 $[2,3]$ ， $[3,3]$ 和 $[3,4]$ ，权值分别为 $-1,-5,-4$ ；
包含 $4$ 的极好区间为 $[3,4]$ 和 $[4,4]$ ，权值分别为 $-4,1$ 。

因此 $k_1 = 6$ ， $k_2 = 6$ ， $k_3 = -1$ ， $k_4 = 1$ 。

对于第 2 次询问， $k_1 = 2$ ， $k_2 = 2$ ， $k_3 = 2$ ， $k_4 = 2$ 。

对于第 3 次询问， $k_1 = 6$ ， $k_2 = 6$ ， $k_3 = 2$ ， $k_4 = 2$ 。

【样例 2】

见选手目录下的 query/query2.in 与 query/query2.ans。

该样例满足测试点 $2,3$ 的约束条件。

【样例 3】

见选手目录下的 query/query3.in 与 query/query3.ans。

该样例满足测试点 $4$ 的约束条件。

【样例 4】

见选手目录下的 query/query4.in 与 query/query4.ans。

该样例满足测试点 $6,7$ 的约束条件。

【样例 5】

见选手目录下的 query/query5.in 与 query/query5.ans。

该样例满足测试点 $8 \sim 10$ 的约束条件。

【样例 6】

见选手目录下的 query/query6.in 与 query/query6.ans。

该样例满足测试点 $11,12$ 的约束条件。

【样例 7】

见选手目录下的 query/query7.in 与 query/query7.ans。

该样例满足测试点 $13$ 的约束条件。

【样例 8】

见选手目录下的 query/query8.in 与 query/query8.ans。

该样例满足测试点 $16 \sim 20$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

$1 \le n \le 5 \times 10^4$ ， $1 \le q \le 1,024$ ；
对于所有 $1 \le i \le n$ ，均有 $|a_i| \le 10^5$ ；
对于所有 $1 \le j \le q$ ，均有 $1 \le L_j \le R_j \le n$ 。

::cute-table{tuack}

测试点编号	$n \le$	$q \le$	特殊性质
$1$	$10^3$	$1$	无
$2,3$	$3{,}000$	$50$	^
$4$	$10^4$	$128$	^
$5$	$3 \times 10^4$	$512$	^
$6,7$	$5 \times 10^4$	$1{,}024$	A
$8 \sim 10$	^	$512$	B
$11,12$	^	^	C
$13$	^	$1{,}024$	D
$14,15$	^	^	E
$16 \sim 20$	^	^	无

特殊性质 A：对于所有 $1 \le j \le q$ ，均有 $L_j = R_j$ 。

特殊性质 B：对于所有 $1 \le j \le q$ ，均有 $R_j \le 32$ 。

特殊性质 C：对于所有 $1 \le j \le q$ ，均有 $L_j \le 16$ 且 $R_j \ge n - 1000$ 。

特殊性质 D：对于所有 $1 \le j \le q$ ，均有 $L_j > n/2$ 。

特殊性质 E：对于所有 $1 \le j \le q$ ，均有 $L_j > n/4$ 。