분탕의 신 다다스

각 $x$ ($1 \leq x \leq n$)에 대해 길이 $m$의 이진 문자열 $A_x$를 정의하자. $A_x[i]$는 $l_i \leq x \leq r_i$이면 $1$, 아니면 $0$이다.

두 이진 문자열 $P,Q$의 서로 다른 위치의 개수를 $\operatorname{dist}(P,Q)$라고 하자. 어떤 답변 문자열 $B$가 두 후보 $x,y$와 모두 모순되지 않으려면

$$\operatorname{dist}(A_x,B) \leq k,\qquad \operatorname{dist}(A_y,B) \leq k$$

를 만족해야 한다.

삼각 부등식에 의해 이런 $B$가 존재하려면 $\operatorname{dist}(A_x,A_y) \leq 2k$여야 한다. 반대로 $A_x$와 $A_y$가 다른 위치를 두 집합으로 최대한 균등하게 나누어 한쪽에서는 $A_x$, 다른 쪽에서는 $A_y$의 비트를 택하면

$$k=\left\lceil\frac{\operatorname{dist}(A_x,A_y)}{2}\right\rceil$$

로 두 후보를 동시에 가능하게 만들 수 있다. 따라서 정답은

$$\left\lceil\frac{1}{2}\min_{1 \leq x<y \leq n}\operatorname{dist}(A_x,A_y)\right\rceil$$

이다.

이제 모든 쌍의 최소 거리를 구한다. 하나의 질문 구간 $[l,r]$은 $x<y$인 쌍 중 정확히 한쪽만 구간에 포함되는 경우에만 거리에 $1$을 더한다. 이러한 쌍은 다음 두 직사각형으로 나뉜다.

$$[1,l-1]\times[l,r],\qquad [l,r]\times[r+1,n].$$

두 번째 좌표 $y$를 $1$부터 $n$까지 증가시키며 스위핑한다. 현재 세그먼트 트리의 $x$번 값은 $x<y$인 위치에 대해 $\operatorname{dist}(A_x,A_y)$가 되도록 관리한다.

구간 $[l,r]$에 대해 필요한 이벤트는 다음과 같다.

• $y=l$일 때 구간 $[1,l-1]$에 $1$을 더한다.
• $y=r+1$일 때 구간 $[1,l-1]$에서 $1$을 빼고, 구간 $[l,r]$에 $1$을 더한다.

각 $y$에서 이벤트를 모두 적용한 뒤 세그먼트 트리의 구간 $[1,y-1]$의 최솟값을 확인한다. 모든 $y$에 대한 최솟값이 필요한 최소 해밍 거리이다.

각 질문은 상수 번의 구간 덧셈만 만들며, 세그먼트 트리는 구간 덧셈과 구간 최솟값을 $O(\log n)$에 처리한다. 전체 시간 복잡도는 $O((n+m)\log n)$이고, 공간 복잡도는 $O(n+m)$이다.

Solution written by GPT5.6