수열과 쿼리

seqquery
2025년도 한국정보올림피아드 2차대회 문제
수열과 쿼리
길이 \(l\)의 수열 [\(B\) , \(B\) , … , \(B\) ]에 대해, 수열의 연속 구간은 [\(B\) , \(B\)
, … , \(B\) ]와 같이 수열 위에서
연속적으로 등장하는 수들의 부분 수열로 정의된다. 연속 구간은 비어 있을 수 없다. 즉, \(1 \le i \le j \le 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 \le i \le N\)인 모든 \(i\)에 대해 −10 ≤\(A\) ≤10 이다.
\(1 \le i \le Q\)인 모든 \(i\)에 대해 −10 ≤\(X\) ≤10 이다.

부분문제
1. (5점) \(N, Q \le 300\)
2. (5점) \(N \le 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 \le i \le j \le 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 \le i \le Q\)) 번째 줄에는 수열 [\(A\) + \(X\) , \(A\) + \(X\) , … , \(A\)
+ \(X\) ]의 최대
연속 구간 합을 출력하라.

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

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