「一本通 5.6 练习 3」特别行动队

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

连续分段 DP 展开后每个切点 j 变成一条直线 l_j(u)=S_j·u+Y_j，a<0 与 x_i≥1 使查询点与斜率双单调，单调队列维护上包络把 O(n²) 降到 O(n)。

OJ: roj

题目 ID: 1612

难度:提高+/省选-

标签:动态规划斜率优化凸包优化单调队列前缀和python一本通

创建: 2026-09-30 21:52

更新: 2026-10-07 13:50

前置题目

roj 3158任务安排1A 教的「核对决策点 x_j 与查询斜率 k_i 都单调后用下凸壳+单调队列摊还 O(1)」正是 B 主解实际走的第五步：B 把 (S_i-S_j)² 展开成直线 l_j(u)=S_j·u+Y_j 后，同样靠 x_i≥1 使斜率单调增、a<0 使查询点单调增，再用双端队列弹队头弹队尾维护包络（main.py 的 hull 两个 while），只是把最小截距下凸壳换成最大上包络并把一维序列扩到 n=10^6，难度仅升一级。roj 1610「一本通 5.6 练习 1」玩具装箱B 的斜率优化解法完整复用 A 教的这一步：同样把 dp 转移展开成 l_j(x)=m_j·x+b_j 直线族、同样利用斜率与查询双单调在双端队列上维护凸壳，队尾判死线也同样用交叉相乘（B 代码 slope_pq>=slope_qi 即 A 的 is_shadow），只是把取 min 的下凸壳镜像成取 max 的上包络，并叠加 a<0 的查询点单调与 n=10^6 的 array 存储；A 是提高级模板题，B 是提高+/省选-的加强应用，方向正确。

形式化题目

给定序列 $x_1, x_2, \ldots, x_n$ 与函数 $g(u) = a u^2 + b u + c$ ，其中 $a < 0$ 。记前缀和

S_i = x_1 + x_2 + \cdots + x_i, \qquad S_0 = 0 .

选择一组下标 $0 = p_0 < p_1 < \cdots < p_k = n$ ，把序列切成 $k$ 个连续段 $(p_{t-1}, p_t]$ ，使

\sum_{t=1}^{k} g\big(S_{p_t} - S_{p_{t-1}}\big)

最大，输出这个最大值。

约束： $1 \leqslant n \leqslant 10^6$ ， $-5 \leqslant a \leqslant -1$ ， $|b|, |c| \leqslant 10^7$ ， $1 \leqslant x_i \leqslant 100$ ，故 $S_n \leqslant 10^8$ 。

正解

思路

第一步：写出划分 DP。

"同一支特别行动队编号连续"这句话把问题完全定死了：任何编队方案就是序列的一个划分，一支队伍对应一段连续区间。于是设 $f[i]$ 为前 $i$ 个士兵的最大修正战斗力和， $f[0] = 0$ ，枚举最后一支队伍的起点 $j$ ：

f[i] = \max_{0 \leqslant j < i} \Big\{ f[j] + g(S_i - S_j) \Big\} . \tag{1}

答案就是 $f[n]$ ，且 $f[0] = 0$ 对应"一个人不编队"这个唯一合法起点。任何合法方案都能被"最后一次切在哪里"唯一描述，所以 (1) 式不重不漏。注意 $f$ 可以取到负数（例如 $a=-1,b=-3,c=0$ 时 $g(1)=-4$ ），所以不能把初值当癈断下界。

以样例 $n=4,\ a=-1,\ b=10,\ c=-20,\ x=[2,2,3,4]$ 为例，前缀和为 $S = [0,2,4,7,11]$ ，把每个候选 $j$ 的取值都算出来（✅ 是取到最大值的 $j$ ）：

$i$	$S_i$	候选 $j$ （单元格为 $f[j]+g(S_i-S_j)$ ）	$f[i]$	最优 $j$
1	2	$j=0$ : -4✅	-4	0
2	4	$j=0$ : 4✅ / $j=1$ : -8	4	0
3	7	$j=0$ : 1 / $j=1$ : 1 / $j=2$ : 5✅	5	2
4	11	$j=0$ : -31 / $j=1$ : -15 / $j=2$ : 5 / $j=3$ : 9✅	9	3

读表可以看出 $f[4] = 9$ 与样例一致，最优的切点是 $j=3$ ：把最后一名士兵单独编一队（ $g(4)=4$ ），前三人的最优值是 $f[3]=5$ ——而 $f[3]$ 又切在 $j=2$ 处，对应" $\{1,2\},\{3\},\{4\}$ "三支队伍。同时注意每行的候选值随 $j$ 先升后降，最优 $j$ 随 $i$ 单调右移（ $0 \to 0 \to 2 \to 3$ ），这正是后面优化的线索。

第二步：瓶颈在哪里。 (1) 式状态数 $O(n)$ ，每个状态要扫 $O(n)$ 个候选 $j$ ，总时间 $O(n^2)$ 。 $n = 10^6$ 时约 $5 \times 10^{11}$ 次转移，即使 C++ 也远远超时。瓶颈是"每个 $i$ 都要把所有 $j$ 扫一遍"。

第三步：把转移线性化。 展开 $g$ ：

\begin{aligned} f[i] &= \max_j \big\{ f[j] + a(S_i - S_j)^2 + b(S_i - S_j) + c \big\} \\ &= \max_j \Big\{ \underbrace{f[j] + aS_j^2 - bS_j}_{\text{只与 } j \text{ 有关}} \;-\; 2aS_i \cdot S_j \Big\} \;+\; \underbrace{aS_i^2 + bS_i + c}_{\text{只与 } i \text{ 有关}} . \end{aligned}

最后那个括号与 $j$ 无关，可以直接提到 $\max$ 外面。含 $j$ 的部分里，只有 $-2aS_i \cdot S_j$ 把 $i$ 和 $j$ 乘在一起。记

Y_j = f[j] + aS_j^2 - bS_j, \qquad u_i = -2aS_i,

得到等价的转移：

f[i] = \max_{0 \leqslant j < i} \Big\{ Y_j + u_i \cdot S_j \Big\} + aS_i^2 + bS_i + c . \tag{2}

第四步：看成"直线族的上包络"。 每个候选 $j$ 对应一条以 $u$ 为自变量的直线

l_j(u) = S_j \cdot u + Y_j \qquad (\text{斜率 } S_j,\ \text{截距 } Y_j),

(2)

第五步：双单调性让上包络退化成单调队列。 两条单调性在本数据范围内同时成立：

新直线的斜率单调增： $x_i \geqslant 1$ 使 $S_j$ 随 $j$ 严格递增。上包络上直线的斜率从左到右递增，所以新直线只会接在包络的右端；
查询点单调增： $a < 0$ 且 $S_i$ 递增 $\Rightarrow u_i = -2aS_i$ 严格递增。查询点只会向右走，最优直线在包络上也只会越来越靠右。

于是双端队列（单调队列）就能维护整条上包络：

查询：设队头为 $h_0$ 、次队头为 $h_1$ 。若在 $u_i$ 处 $h_1$ 已经不劣于 $h_0$ ，由于后续要用的查询点只会更大， $h_0$ 不可能再赢，直接弹出；反复执行直到队头严格最优；
插入：新直线 $i$ 入队前，检查队尾两条直线 $p, q$ 。设 $x_{pq}$ 是 $p,q$ 的交点横坐标（ $x_{pq} = \frac{Y_q-Y_p}{S_q-S_p}$ ）。上包络要求交点位置递增： $x_{pq} < x_{qi}$ 。若 $x_{pq} \geqslant x_{qi}$ ，说明 $q$ 还没等到超过 $p$ ，就已经被 $i$ 超过，它的领先区间为空，不再出现在包络上，弹出；反复执行后把 $i$ 接到队尾；
判定 $x_{pq} \geqslant x_{qi}$ 时用整数交叉相乘代替除法（两边分母 $S_q-S_p>0$ 、 $S_i-S_q>0$ 均正，不等号不翻转）：
$\frac{Y_q - Y_p}{S_q - S_p} \geqslant \frac{Y_i - Y_q}{S_i - S_q} \iff (Y_q - Y_p)(S_i - S_q) \geqslant (Y_i - Y_q)(S_q - S_p).$
代码里的 slope_pq >= slope_qi 正是左边这个不等式（取等号时三线共点，丢中间那条不影响答案）；整数运算在 Python 中没有精度问题。

下图把样例的单调队列执行过程逐步列出来（ $k_i = 2aS_i = -u_i$ ，即代码里取负后的写法）：

$i$	查询用 $k_i=2aS_i$	查询时弹出队头	队头（最优 $j$ ）	插入前弹出队尾	入队后上包络（各直线的 $(S_j, Y_j)$ ）
1	-4	无	$j=0$ （ $f=0$ ）	无	(0,0) → (2,-28)
2	-8	无	$j=0$ （ $f=0$ ）	$j=1$	(0,0) → (4,-52)
3	-14	$j=0$	$j=2$ （ $f=4$ ）	无	(4,-52) → (7,-114)
4	-22	$j=2$	$j=3$ （ $f=5$ ）	无	(7,-114) → (11,-222)

表中括号里的两个数是直线的参数 $(S_j, Y_j)$ ，即斜率与截距。可以看到 $i=2$ 时直线 $j=1$ 刚入队就被 $j=2$ 顶掉（队尾弹出）， $i=3$ 时队头 $j=0$ 因为查询点变大而失效（队头弹出）——两种弹出合起来保证每条直线最多进出队各一次，主循环是摊还 $O(1)$ 的。

代码

max_power() 就是上面第四、五步的实现：hull 存直线编号，第一个 while 是查询前弹队头，第二个 while 是插入前弹队尾，y[i] 就是截距 $Y_i$ ，k = 2*a*s 是 $-u_i$ （两边同乘 $-1$ 后把 $\max l_j(u)$ 写成 $\max (Y_j - k S_j)$ ）。solve() 只负责读入、算前缀和、输出；pre、f、y 用 array('q') 存放（ $n = 10^6$ 时把峰值内存压到 128 MB 以内），读入用的临时表在求完前缀和后立即释放。

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#!/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-09-30 21:53
# update_at: 2026-09-30 22:05

import sys
from array import array
from collections import deque
from itertools import accumulate


def max_power(a: int, b: int, c: int, pre: array) -> int:
    """前 n 个士兵编队的最大修正战斗力和（斜率优化，O(n)）。

    设 f[i] 为前 i 人的答案，最后一队是 (j, i]，则
        f[i] = max_j { f[j] + g(S[i] - S[j]) },  g(u) = a·u² + b·u + c。
    展开 g，把只与 j 有关的项收成 Y[j] = f[j] + a·S[j]² - b·S[j]：
        f[i] = max_j { Y[j] + u[i]·S[j] } + a·S[i]² + b·S[i] + c,  u[i] = -2a·S[i]。
    每个候选切点 j 于是是一条直线 l_j(u) = S[j]·u + Y[j]（斜率 S[j]、截距 Y[j]），
    转移变成"在直线族的上包络上查询 u = u[i] 处的最大值"。
    a < 0 ⇒ 查询点 u[i] 随 i 递增；x[i] ≥ 1 ⇒ 直线斜率 S[j] 随 j 递增。
    新直线只接在包络右端、查询点又只向右走，两条单调 ⇒ 单调队列：
    队头弹出已被超过的直线，队尾弹出被新直线压得不再可能是最优的直线；
    每条直线进出队各一次，摊还 O(1)。
    """
    n = len(pre) - 1
    f = array('q', [0]) * (n + 1)  # f[i]：前 i 人的最优值，f[0] = 0
    y = array('q', [0]) * (n + 1)  # 直线截距 Y[i] = f[i] + a·S[i]² - b·S[i]
    hull = deque([0])              # 上包络上的直线编号，斜率 S[j] 随入队递增

    for i in range(1, n + 1):
        s = pre[i]
        k = 2 * a * s  # k = -u[i]：两边同乘 -1，把 max l_j(u) 写成 max(Y[j] - k·S[j])
        while len(hull) >= 2:
            head, second = hull[0], hull[1]
            if y[head] - k * pre[head] <= y[second] - k * pre[second]:
                hull.popleft()  # 次队头已不比队头差，u[i] 只会更大，队头此后再也用不到
            else:
                break
        j = hull[0]  # 最优直线：最后一段的左边界
        f[i] = f[j] + a * (s - pre[j]) ** 2 + b * (s - pre[j]) + c
        y[i] = f[i] + a * s * s - b * s
        while len(hull) >= 2:
            p, q = hull[-2], hull[-1]
            # 判据即交点位置 x[p][q] ≥ x[q][i]：直线 q 的领先区间为空，可丢；交叉相乘免去除法
            slope_pq = (y[q] - y[p]) * (s - pre[q])
            slope_qi = (y[i] - y[q]) * (pre[q] - pre[p])
            if slope_pq <= slope_qi:
                hull.pop()  # q 被直线 p 与 i 夹在包络之下，不再出现在上包络上
            else:
                break
        hull.append(i)
    return f[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 士兵数
    a, b, c = next(data), next(data), next(data)  # 经验公式系数
    pre = array('q', accumulate((next(data) for _ in range(n)), initial=0))  # S[0..n]
    print(max_power(a, b, c, pre))


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
126
127
128
129
130
131/**
 * 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-05 12:53
 * update_at: 2026-10-05 12:53
 */

// main.cpp：一本通 5.6 练习 3「特别行动队」（APIO 2010 特别行动队）。
// 编号必须连续，所以任何编队方案就是把序列切成若干连续段的划分，
// 设 f[i] 为前 i 名士兵的最大修正战斗力和，枚举最后一支队伍的起点 j：
//     f[i] = max_{j<i} { f[j] + g(S_i - S_j) }，g(u) = a*u^2 + b*u + c。
// 展开 g 后，只与 j 有关的项收成截距 Y_j = f[j] + a*S_j^2 - b*S_j，
// 与 i 有关的项提到 max 外面，转移变成「在直线族 l_j(u) = S_j*u + Y_j 的
// 上包络上查询 u_i = -2*a*S_i」：
//     f[i] = max_j { S_j*u_i + Y_j } + a*S_i^2 + b*S_i + c。
// x_i >= 1 使直线斜率 S_j 随 j 递增，a < 0 使查询点 u_i 随 i 递增，
// 两条单调同向，于是用单调队列维护上包络即可：队头弹出已被超过的直线，
// 队尾弹出被新直线压得不再可能最优的直线，摊还 O(1)，总时间 O(n)。

#include <cstdio>

typedef long long ll;
typedef __int128 lll;

const int MAXN = 1000005; // n 的上限

ll n;           // 士兵总数
ll a, b, c;     // 经验公式系数，满足 a < 0
ll pre[MAXN];   // pre[i] = 前 i 名士兵的初始战斗力之和 S_i，S_0 = 0
ll f[MAXN];     // f[i] = 前 i 名士兵编队后能得到的最大修正战斗力和
ll y[MAXN];     // y[i] = 直线 l_i 的截距 Y_i = f[i] + a*S_i^2 - b*S_i
int hull[MAXN]; // 上包络上的直线编号队列，斜率 S_j 随入队递增
int head;       // 队列头下标，head 指向当前最优直线
int tail;       // 队列尾下标

// 快速读入，n 最大 10^6，避免 cin / scanf 的额外开销
ll read_ll() {
    int ch = getchar();
    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = getchar();
    }
    ll sign = 1;
    if (ch == '-') {
        sign = -1;
        ch = getchar();
    }
    ll value = 0;
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = getchar();
    }
    return sign * value;
}

// 两个数相乘，用 __int128 承接结果：叉积可达 10^25，超出 long long
lll product(lll x, lll y) {
    return x * y;
}

// 直线 l_j 在查询点 u 处的取值 l_j(u) = S_j * u + Y_j
lll value_at(int j, ll u) {
    return y[j] + product(u, pre[j]);
}

// 直线 q 是否被直线 p 与 i 夹在上包络之下（q 的领先区间为空，可以丢掉）。
// 等价于两交点位置比较 x[p][q] >= x[q][i]，即
//     (Y_q - Y_p) * (S_i - S_q) <= (Y_i - Y_q) * (S_q - S_p)，
// 交叉相乘代替除法，既避免浮点误差也不需要判分母符号。
// 取等号时三线共点，丢掉中间那条不影响答案。
bool is_hidden(int p, int q, int i) {
    return product(y[q] - y[p], pre[i] - pre[q])
           <= product(y[i] - y[q], pre[q] - pre[p]);
}

void solve() {
    n = read_ll();
    a = read_ll();
    b = read_ll();
    c = read_ll();
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + read_ll(); // 前缀和
    }

    head = 0;
    tail = 0;
    hull[0] = 0; // 只有 j = 0 可选，f[0] = 0、S_0 = 0、Y_0 = 0

    for (int i = 1; i <= n; i++) {
        ll s = pre[i];
        ll u = -2 * a * s; // 查询点 u_i = -2*a*S_i，随 i 严格递增

        // 插入前先查询：次队头在 u_i 处已不劣于队头，说明队头的领先区间已经过去，
        // 而后续查询点只会更大，队头此后永远用不到，直接弹出
        while (tail > head) {
            int first = hull[head];
            int second = hull[head + 1];
            if (value_at(first, u) <= value_at(second, u)) {
                head++;
            } else {
                break;
            }
        }
        int j = hull[head]; // 最优切点：最后一支队伍的起点是 j+1

        ll len = s - pre[j]; // 最后一支队伍的初始战斗力
        f[i] = f[j] + a * len * len + b * len + c;
        y[i] = f[i] + a * s * s - b * s; // 新直线的截距

        // 新直线斜率 S_i 最大，只会接在包络右端；入队前检查队尾两条直线，
        // 若 q 还没超过 p 就被 i 超过，q 的领先区间为空，弹出
        while (tail > head) {
            int p = hull[tail - 1];
            int q = hull[tail];
            if (is_hidden(p, q, i)) {
                tail--;
            } else {
                break;
            }
        }
        tail++;
        hull[tail] = i;
    }

    printf("%lld\n", f[n]);
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度：读入、前缀和、主循环都是 $O(n)$ ，主循环的两次 while 摊还 $O(1)$ （每条直线最多入队一次、出队一次），总计 $O(n)$ ，与标准 C++ 斜率优化解法同阶。
空间复杂度： $O(n)$ ，即前缀和、 $f$ 、 $Y$ 三张表和队列； $n = 10^6$ 时实测峰值约 74 MB。
数值范围： $f$ 可达 $10^{13}$ 量级，叉积比较约 $10^{24}$ ，Python int 任意精度不会溢出（C++ 需要 __int128）。
Python 侧风险：本地 10 组真实数据 $n = 10^6$ 用时约 0.9 s，若 OJ 解释器更慢存在 TLE 风险（按任务约定允许）。

总结

建模：编号连续 ⇒ 问题就是"把序列切成若干连续段、段费用由段和决定"的划分 DP， $f[i] = \max_j \{ f[j] + g(S_i - S_j) \}$ 。
线性化：展开 $g$ 后，只与 $j$ 有关的项收成截距 $Y_j = f[j] + aS_j^2 - bS_j$ ，与 $i$ 有关的项提到 $\max$ 外，转移变成"在直线族 $l_j(u) = S_j u + Y_j$ 的上包络上查询 $u_i = -2aS_i$ "。
上包络：只有上包络上的直线可能成为最大值，被压在下方的直线可以永久丢弃。
双单调： $a < 0$ 使查询点 $u_i$ 单调增， $x_i \geqslant 1$ 使直线斜率 $S_j$ 单调增，两者同向 ⇒ 双端队列摊还 $O(1)$ 维护上包络，总复杂度 $O(n)$ 。
易错点：交点判据必须用交叉相乘（浮点除法会在大数下失准）；插入用 <= 弹出可顺带处理三线共点； $S$ 严格递增是"分母恒正、不等号不翻转"的前提，若 $x_i$ 可能为 0 需要改写。

图示解析

从输入到答案的完整推导链路，每一步只做一件事：

flowchart LR
  A["输入 n, a, b, c, x"] --> B["前缀和 S_i"]
  B --> C["划分 DP<br/>f[i] = max_j f[j]+g(S_i-S_j)"]
  C --> D["展开 g<br/>切点 j 变成直线 l_j(u)=S_j·u+Y_j"]
  D --> E["在 u_i = -2aS_i 处查询<br/>直线族的上包络"]
  E --> F["双单调性<br/>u_i 递增、直线斜率 S_j 递增"]
  F --> G["单调队列维护上包络<br/>队头弹出 + 队尾弹出"]
  G --> H["f[n] 即答案"]

观察重点：C→D 是分水岭，它把"枚举切点"换成"在直线族的上包络上查询"；D→E→F 说明为什么可以只用双端队列而不是三分查找或李超树——查询点与直线斜率同向单调，最优直线只向右移，队头可以直接弹掉；G 的两个 while 分别对应"旧直线过期"与"新直线让旧直线失去包络地位"。

【题目描述】

原题来自：APIO 2010

你有一支由 $n$ 名预备役士兵组成的部队，士兵分别编号为 $1…n$ ，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 $(i, i + 1, \\dots , i + k)$ 的序列。编号为 $i$ 的士兵的初始战斗力为 $x\_i$ ，一支特别行动队的初始战斗力 $x$ 为队内士兵初始战斗力之和，即 $x = x\_i + x\_{i+1} + ⋯ +x\_{i+k}$ 。

通过长期的观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下经验公式修正为 $x’:x’= ax^2+bx+c$ ，其中 $a, b, c$ 是已知的系数( $a < 0$ )。作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。

例如，你有 $4$ 名士兵， $x\_1 = 2,x\_2 = 2,x\_3 = 3,x\_4 = 4$ 。经验公式中的参数为 $a = –1,b = 10, c = –20$ 。此时，最佳方案是将士兵组成 $3$ 个特别行动队：第一队包含士兵 $1$ 和士兵 $2$ ，第二队包含士兵 $3$ ，第三队包含士兵 $4$ 。特别行动队的初始战斗力分别为 $4,3,4$ ，修正后的战斗力分别为 $4,1,4$ 。修正后的战斗力和为 $9$ ，没有其它方案能使修正后的战斗力和更大。

【输入】

输入由三行组成。

第一行包含一个整数 $n$ ，表示士兵的总数。

第二行包含三个整数 $a, b, c$ ，经验公式中各项的系数。

第三行包含 $n$ 个用空格分隔的整数 $x\_1,x\_2,…, x\_n$ ，分别表示编号为 $1,2,…, n$ 的士兵的初始战斗力。

【输出】

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

【输入样例】

text

【输出样例】

text

【提示】

数据范围与提示：

20% 的数据中， $n≤1000$ ；

50% 的数据中， $n≤10^4$ ；

100% 的数据中， $1≤n≤10^6 , –5≤a≤–1, ∣b∣,∣c∣≤10^7 , 1≤x\_i ≤100$ 。

【来源】

一本通在线评测