https://codeforces.com/contest/1736/problem/C2
Problem - C2 - Codeforces
codeforces.com
2400짜리 문제...너무 어렵다.
C1에서 dp[i] = min(arr[i], dp[i - 1] + 1) 인 것은 쉽게 알 수 있다.
먼저 모든 i에 대해 track[i](dp[i] = arr[i]라고 가정했을 때 [i, N] 구간 dp 합) 를 전처리 해 둔다.
dp에 대한 psum도 전처리를 해 준다.
이제 쿼리를 구해보자.
dp'를 arr[p] = x 가 됐을 때 p부터의 dp라고 했을 때 dp'[q] = arr[q]인 가장 작은 q를 찾는다.(p < q <= N + 1)
q가 없을 수도 있으므로 N + 1 범위까지 찾는다.
q는 가장 먼저 dp'[p] + i - p >= arr[i] 를 만족하는 i 이므로
[1, p)는 psum, [p, q)는 등차수열 합, [q, N)은 track으로 구하면 된다.
1. 세그로 구현
track을 N부터 내림차순으로 구할건데 arr[i](= track[i]) + j - i >= arr[j]인 (i, N]에서 가장 작은 j를 구한다.
식을 정리하면 arr[i] - i >= arr[j] - j 이므로 세그에 미리 arr[i] - i를 저장해두고 이분탐색으로 구하면 된다.
2. 오프라인 쿼리로 구현
(arr[i] - i, i, 0)과 (dp'[p] - p, p, q_i)를 배열에 저장하고 오름차순으로 정렬한다.
track[i]가 구해지면 i가 순서대로 저장되게 set을 사용한다.
1) q_i == 0 track을 구하는 쿼리이므로 arr[i] - i >= arr[j] - j를 구할 때 set에서 찾고 set에 i를 집어넣는다.
set에 저장된 인덱스는 모두 arr[i] - i 보다 작거나 같기 때문이다.
2) q_i != 0 찐쿼리이므로 1) 과 같은 방법으로 답을 구하면 된다. track과 set은 업데이트 되지 않는다.
