좌표 압축과 쿼리

배열 $A$를 그대로 유지하면서 각 쿼리를 처리한다.

1번 쿼리는 $A_l,\ldots,A_r$을 복사한 뒤 정렬하고 중복을 제거한다. 정렬된 배열 $B$에서 각 $A_i$의 lower_bound 위치가 새 좌표이다. 구간 밖은 변경하지 않는다.

2번 쿼리는 구간을 한 번 순회하여 최솟값 $m$과 최댓값 $M$을 찾는다. 소수점을 사용하지 않기 위해 각 후보 $x$의 거리 대신 $|2x-(m+M)|$를 비교한다. 이를 최소화하는 값 중 가장 작은 값을 고른다. 정수의 범위를 고려해 모든 배열 값과 계산을 long long으로 처리한다.

3번 쿼리는 구간의 모든 원소에 $d$를 직접 더한다.

정당성: 좌표 압축의 중복 제거된 정렬 순서는 각 값보다 작은 서로 다른 값의 개수를 정확히 나타낸다. 2번 쿼리는 구간에 등장하는 모든 후보를 검사하므로 가장 가까운 값과 동률 규칙을 정확히 적용한다. 3번 쿼리는 정의된 원소만 갱신한다. 따라서 모든 쿼리가 올바르게 처리된다.

1번 쿼리는 각각 $O(N\log N)$, 나머지 쿼리는 각각 $O(N)$ 시간이 걸린다. 1번 쿼리는 최대 $100$개이므로 총 시간복잡도는 $O(NQ+100N\log N)$, 추가 공간복잡도는 이다.