seqquery
2025년도 한국정보올림피아드 2차대회 문제
수열과 쿼리
길이 l의 수열 [B , B , … , B ]에 대해, 수열의 연속 구간은 [B , B
, … , B ]와 같이 수열 위에서
연속적으로 등장하는 수들의 부분 수열로 정의된다. 연속 구간은 비어 있을 수 없다. 즉, 1 ≤i ≤j ≤l을
만족해야 한다.
길이 l의 수열 [B , B , … , B ]에 대해, 수열의 최대 연속 구간 합은 수열의 모든 연속 구간의 원소의 합의
최댓값으로 정의된다. 예를 들어, 수열 [6, −7, 3, −1, 5, 2]의 최대 연속 구간 합은 9이며, 이는 연속 구간
[3, −1, 5, 2]를 골라서 얻을 수 있다. 수열 B의 최대 연속 구간 합을 수학 기호로 표현하면
max
(
B )이다.
길이 N의 수열 [A , A , … , A ]과 Q 개의 쿼리가 주어진다. i 번째 쿼리는 하나의 정수 X 로 표현된다. X
가 주어졌을 때, 수열 [A + X , A + X , … , A
+ X ]의 최대 연속 구간 합을 계산하라.

주어지는 모든 수는 정수이다.
1 ≤N ≤1 000 000
1 ≤Q ≤1 000 000
1 ≤i ≤N인 모든 i에 대해 −10 ≤A ≤10 이다.
1 ≤i ≤Q인 모든 i에 대해 −10 ≤X ≤10 이다.

부분문제
1. (5점) N, Q ≤300
2. (5점) N ≤300
3. (28점) N ≤10 000
4. (17점) N ≤125 000
5. (16점) N ≤250 000
6. (15점) N ≤500 000
7. (14점) 추가 제약 조건 없음.

첫 번째 줄에 N, Q가 공백을 사이에 두고 주어진다.
두 번째 줄에 A , A , … , A 이 공백을 사이에 두고 주어진다.
세 번째 줄에 X , X , … , X 가 공백을 사이에 두고 주어진다.
1
2
l
i
i+1

j
1
2
l
1≤i≤j≤l

∑k=i
j
k
1
2
N
i
i
1
i
2
i
N
i
9
i
9
9
i
9
1
2
N
1
2
Q
seqquery (1 of 2)

Q개의 줄을 출력하라. 이 중 i(1 ≤i ≤Q) 번째 줄에는 수열 [A + X , A + X , … , A
+ X ]의 최대
연속 구간 합을 출력하라.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 구재현