11월 3주차 ps일지

https://www.acmicpc.net/problem/17671

 

[l, r] 내에 연결된 |H[i] - H[j]| 최댓값을 구하는 문제다.

일단 i를 포함하는 답은 |mn - H[i]| or |mx - H[i]| 뿐임을 알 수 있다.

따라서 i의 입장에서 연결 가능한 j의 최댓값과 최솟값을 찾으면 된다.

 

j < i인 i, j가 연결되기 위해선

• j+A[j] <= i <= j+B[j]
• i-B[i] <= j <= i-A[i]

두 조건을 만족하여야 한다.

 

일단 구간에 대한 mn을 관리하는 세그가 있을 때

구간에 대한 쿼리를 날리는 것으로 i-B[i] <= j <= i-A[i]를 만족하는 j들의 mn을 찾을 수 있다.

하지만 저 범위에 있는 j가 j+A[j] <= i <= j+B[j]를 만족하는 지는 모른다.

 

j는  j+A[j] <= i <= j+B[j]을 만족하는 i에 대해서만 기여해야 하므로

i가 j+A[j]일때 j를 추가하고, j+B[j]+1이 되었을 때 j를 삭제하는 것으로 subtask 3을 해결할 수 있다.

 

이제 구간 쿼리를 처리해보자

일단 subtask 3 풀이에 스위핑이 존재하므로 r에 대해 정렬된 순서로 처리하자

 

그럼 이제 고정된 r에 대하여 [i, r] 형태의 쿼리를 처리해야하는데

subtask 3처럼 i-B[i] <= j <= i-A[i]를 만족하는 j에 대해 쿼리를 날리는 식으로 진행하면 왼쪽 구간이 변화했을 때

답을 구할 수 없게 된다.

 

우리는 위 형태는 유지하되, 값을 들고있는 주체를 바꿀 것이다.

이제 seg는 구간에 대하여 {ans, mn}을 관리할 것이다.

고정된 오른쪽 구간 r이 추가되었을 때 r-B[r] <= j <= r-A[r]에 대하여 H[r]을 사용해보지 않을래? 라는 쿼리를 날린다.

그러면 H[r]-mn과 ans 둘 중 하나가 새로운 ans가 될 것이다.

그리고 [i, r]에 대해 쿼리를 날리면 해당 구간의 ans를 얻을 수 있겠다.

 

i번 인덱스가 기여하는 r과 기여하지 않는 r은 어떻게 구분할까?

i번 인덱스가 등장할 때 본인의 mn을 H[i]로 설정하고, 퇴장할때는 INF로 설정하면

업데이트를 진행할 때 같이 업데이트가 되긴 하겠지만 절대로 답의 후보가 되지 않을 것이다.

따라서 해결할 수 있다.