#P13609. [KOI 2025 #2] 序列与查询

    ID: 12809 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-一维前缀和分治算法凸包Minkowski 和凸多边形边向量归并直线上包络二分查找

[KOI 2025 #2] 序列与查询

题目描述

对于一个长度为 ll 的序列 [B1,B2,…,Bl][B_1, B_2, \ldots, B_l],序列的连续子区间被定义为像 [Bi,Bi+1,…,Bj][B_i, B_{i+1}, \ldots, B_j] 这样在序列中连续出现的数的子序列。连续子区间不能为空。即,必须满足 1≤i≤j≤l1 \le i \le j \le l。

对于一个长度为 ll 的序列 [B1,B2,…,Bl][B_1, B_2, \ldots, B_l],序列的最大连续子区间和被定义为该序列所有连续子区间的元素和中的最大值。例如,序列 [6,−7,3,−1,5,2][6, -7, 3, -1, 5, 2] 的最大连续子区间和是 9,这可以通过选取子区间 [3,−1,5,2][3, -1, 5, 2] 得到。如果用数学符号表示序列 BB 的最大连续子区间和,则为 max⁡1≤i≤j≤l(∑k=ijBk)\max_{1 \le i \le j \le l}(\sum_{k=i}^{j} B_k)。

给定一个长度为 NN 的序列 [A1,A2,…,AN][A_1, A_2, \ldots, A_N] 和 QQ 个查询。第 ii 个查询由一个整数 XiX_i 表示。当给定 XiX_i 时,你需要计算序列 [A1+Xi,A2+Xi,…,AN+Xi][A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i] 的最大连续子区间和。

输入格式

第一行给定 N,QN, Q,以空格分隔。

第二行给定 A1,A2,…,ANA_1, A_2, \ldots, A_N,以空格分隔。

第三行给定 X1,X2,…,XQX_1, X_2, \ldots, X_Q,以空格分隔。

输出格式

输出 QQ 行。其中第 i(1≤i≤Q)i(1 \le i \le Q) 行输出序列 [A1+Xi,A2+Xi,…,AN+Xi][A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i] 的最大连续子区间和。

输入输出样例 #1

输入 #1

6 15
6 -7 3 -1 5 2
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

输出 #1

-1
0
1
2
3
4
5
9
14
20
26
32
38
44
50

输入输出样例 #2

输入 #2

10 15
-2 6 3 -8 1 2 0 -3 9 6
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

输出 #2

2
3
5
7
9
11
13
16
25
34
44
54
64
74
84

说明/提示

限制条件

  • 所有给定的数都是整数。
  • 1≤N≤1 000 0001 \le N \le 1\,000\,000
  • 1≤Q≤1 000 0001 \le Q \le 1\,000\,000
  • 对于所有满足 1≤i≤N1 \le i \le N 的 ii,有 −109≤Ai≤109-10^9 \le A_i \le 10^9。
  • 对于所有满足 1≤i≤Q1 \le i \le Q 的 ii,有 −109≤Xi≤109-10^9 \le X_i \le 10^9。

子任务

  1. (5 分) N,Q≤300N, Q \le 300
  2. (5 分) N≤300N \le 300
  3. (28 分) N≤10 000N \le 10\,000
  4. (17 分) N≤125 000N \le 125\,000
  5. (16 分) N≤250 000N \le 250\,000
  6. (15 分) N≤500 000N \le 500\,000
  7. (14 分) 无额外限制条件。