루미 알고리즘

#1123다이아수열과 쿼리수열과 쿼리

KOI 2025 2차코딩중등부 4번, 고등부 3번출제 구재현이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

수열과 쿼리

원제: 수열과 쿼리

문제

길이 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]의 최대 연속 구간 합은 99이며, 이는 연속 구간 [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]의 최대 연속 구간 합을 계산하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 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점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 N,QN, Q가 공백을 사이에 두고 주어진다.

두 번째 줄에 A1,A2,…,ANA_1, A_2, \ldots, A_N이 공백을 사이에 두고 주어진다.

세 번째 줄에 X1,X2,…,XQX_1, X_2, \ldots, X_Q가 공백을 사이에 두고 주어진다.

출력 형식

QQ개의 줄을 출력하라. 이 중 ii(1≤i≤Q1 \le i \le Q) 번째 줄에는 수열 [A1+Xi,A2+Xi,…,AN+Xi][A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]의 최대 연속 구간 합을 출력하라.

예제

예제 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
0
1
2
3
4
5
9
14
20
26
32
38
44
50

예제 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
3
5
7
9
11
13
16
25
34
44
54
64
74
84

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.