단층 풀이

시간을 두고 생각해 보았지만 아무 생각이 안 나서 (이러면 안 되는데.. ㅠㅠ) 풀이를 보려고 JOI 사이트에 들어갔는데... 풀이 pdf가 일본어 + 글씨가 그림 형태로 저장되어 있어서 읽을 수가 없었다. 다행히도 풀이 예시 코드가 같이 올라와 있어서 그것을 읽고 나름대로 풀이를 재구성해 볼 수 있었다.

모든 쿼리가 수행된 이후 땅의 모양을 보면 여러 갈래로 잘린 대각선들이 마구 놓여 있는 형태가 될 텐데, 임의의 쿼리가 자르고 지나간 "선의 모양"은 그 이후에 수행된 쿼리에만 영향을 받는다는 관찰을 할 수 있다. 여기서 쿼리를 거꾸로 처리하면 편하다는 생각을 할 수 있다. 한편, 각 쿼리는 최종적으로 봤을 때 자신이 자르고 지나간 선 위쪽의 땅의 값을 특정 값만큼 더해주는 역할을 하므로 각 선이 최종 상태의 표면을 가로지를 때의 x좌표를 빠르게 계산할 수 있다면 구간갱신 - 점쿼리 segment tree로 간단하게 해결 가능한 문제가 된다.

대각선의 방향이 두 가지가 있고, 한쪽 대각선이 자르고 지나간 선의 모양은 다른 쪽 대각선에 해당하는 쿼리에만 영향을 받으므로 2개의 segment tree를 관리하자. 편의 상 기울기 1인 대각선에 해당하는 것을 S1, 나머지를 S2라 하자. 세그먼트 트리는 "최종 표면에서의 x좌표가 i일 때, 원래 쿼리에 해당하는 x좌표"를 관리한다. 초기값은 S1, S2 모두 i 자리에 i를 넣어 주면 될 것이다. 쿼리를 맨 뒤의 것부터 거꾸로 처리해 나간다고 하면, 각 쿼리에 대해 처리할 때는 반대쪽 대각선에 해당하는 세그먼트 트리에서 이진 탐색을 통해 최종 표면에서의 x좌표를 구한 뒤 그 x좌표에 해당하는 부분을 기준으로 이번 쿼리가 영향을 미치는 구간에 2 * L_i (또는 -2 * L_i)를 더해 주면 된다. 이진 탐색 과정에서 O(logn)이 걸리는 쿼리를 O(logn)번 물어 보게 되니 시간 복잡도는 O(Qlog^2n)이다. 최종 표면에서 각 땅에 적힌 값은 (S2.query(i) - S1.query(i)) / 2로 구해진다.