교환과 행렬곱

연산 전의 값을 $S_0$이라 하자. $A_{x,k}=a$와 $B_{k,x}=b$를 교환하고 $d=b-a$라 하자. 교환 후 $A_{x,k}$는 $d$만큼 증가하고 $B_{k,x}$는 $d$만큼 감소한다.

$S$에 포함된 원소 중 $x$번째 행에서 대각선 오른쪽에 있는 원소의 변화량 합은

$$d\sum_{j=x+1}^{N}B_{k,j}$$

이고, $x$번째 열에서 대각선 위쪽에 있는 원소의 변화량 합은

$$-d\sum_{i=1}^{x-1}A_{i,k}$$

이다. 대각 원소에서는 $A_{x,k}B_{k,x}=ab$가 교환 후에도 $ba=ab$이므로 변화량이 이다. 따라서 전체 변화량은

$$\Delta_{x,k}=(B_{k,x}-A_{x,k})\left(\sum_{j=x+1}^{N}B_{k,j}-\sum_{i=1}^{x-1}A_{i,k}\right)$$

이다.

$A$의 열별 앞쪽 누적합과 $B$의 행별 뒤쪽 누적합을 다음과 같이 정의한다.

$$P_{i,k}=\sum_{r=1}^{i}A_{r,k},\qquad Q_{k,i}=\sum_{c=i}^{N}B_{k,c}$$

$P_{0,k}=0$, $Q_{k,N+1}=0$으로 두면 각 변화량은

$$\Delta_{x,k}=(B_{k,x}-A_{x,k})(Q_{k,x+1}-P_{x-1,k})$$

로 $O(1)$에 계산할 수 있다.

초기 합도 행렬곱 전체를 만들 필요 없이 합의 순서를 바꾸어 계산한다.

$$S_0=\sum_{i=1}^{N}\sum_{k=1}^{N}A_{i,k}Q_{k,i}$$

연산을 하지 않는 경우를 포함해야 하므로 정답은

$$S_0+\max\left(0,\max_{1\leq x,k\leq N}\Delta_{x,k}\right)$$

이다. 시간 복잡도와 공간 복잡도는 모두 $O(N^2)$이다.

Solution written by GPT6