적분

각 위치 $i$에 대해

$$D_i=X_i-Y_i$$

라고 하자. 여기서 문자를 정수로 보아 0은 $0$, 1은 $1$로 생각한다. 그러면 $D_i$는 $-1,0,1$ 중 하나이다.

먼저 목적식을 $D_i$로 바꾸자. $S$의 앞 $i$글자에 포함된 1의 개수를 $one_S(i)$라고 하면,

$$f_S(i)=one_S(i)-(i-one_S(i))=2one_S(i)-i$$

이다. 따라서

$$f_X(i)-f_Y(i)=2(one_X(i)-one_Y(i))=2\sum_{j=1}^{i}D_j$$

이다. 그러므로 전체 목적식은

$$2\sum_{i=1}^{N}\sum_{j=1}^{i}D_j = 2\sum_{j=1}^{N}D_j(N-j+1)$$

이다.

이제 연산이 $D$에 어떤 영향을 주는지 보자. 구간 $[l,r]$에서 $X$와 $Y$의 1 개수가 같다는 것은

$$\sum_{i=l}^{r}D_i=0$$

이라는 뜻이다. 이 구간을 서로 바꾸면, 해당 구간의 모든 $D_i$는 부호가 바뀐다. 즉 $D_i$가 $1$이면 $-1$이 되고, 이면 이 되며, 은 그대로 이다.

따라서 문제는 다음과 같이 바뀐다.

$D_i \in \{-1,0,1\}$인 수열이 있다. 합이 $0$인 연속구간의 부호를 원하는 만큼 뒤집을 수 있다. 이때

$$\sum _{i=1}^N{D}_i(N$$

$D_i=0$인 위치는 어떤 연산을 해도 계속 $0$이다. 이제 $D_i \ne 0$인 위치들만 보자. 만약 어떤 두 비영 위치 사이에 이 먼저 나오고, 그 뒤에 이 나오며 그 사이가 모두 이라면, 그 전체 구간의 합은 이다. 이 구간을 뒤집으면