10650 Marathon
다음과 같은 두 배열을 관리하자.
- $\text{next}[i]$ : $i$번째 좌표에서 $i+1$번째 좌표로 이동하는 거리
- $\text{save}[i]$ : $i$번째 좌표를 달리기 중 생략하기로 결정했을 때 절약하는 거리
그러면 쿼리 $Q$는 다음과 같이 해결할 수 있다. $s$에서 $e$까지 이동해야 하면, $\displaystyle \sum_{i=s}^{e-1} \text{next}[i] - \max_{s + 1 \le i \le e - 1} \text{save}[i] $ 가 답이 된다. 따라서 $\text{next}$는 부분 합 세그먼트 트리, $\text{save}$는 부분 최대 세그먼트 트리를 이용해서 관리해주면 $O(\log N)$에 찾을 수 있다.
쿼리 $U$는 Naive하게 처리해 주어도 세그먼트 트리 위에서 $O(\log N)$에 처리 가능하다.
Trivial한 세그먼트 트리 문제.
6150 Summing Sums
이런 문제가 나오면 흔히 하던 대로 각 소가 들고 있는 수를 초기값의 선형 결합으로 대신 나타낼 수 있다. 규칙을 잘 찾아보자. 연산을 $t$번 시행했을 때 각 소의 수를 생각해보자. 어떤 $i$번째 소가 들고 있는 수를 $a_1c_1 + a_2c_2 + \cdots a_Nc_N$이라고 나타내면, $t=1$일 때 $x \neq i$인 $a_x =1$이다. 이런 $a_x$는 항상 값이 모두 같으므로, 이를 그냥 $t$번째 시행에서 $a_t$라고 하자. 그러면 $a$는 $t$의 기우성에 따라 $a_{t+1} = a_t (n-1) + 1$이던지, $a_{t+1} = a_t(n-1) - 1$이다. 그리고 자기 자신이 더해지는 횟수도 역시 $t$의 기우성에 따라 $a_t -1 $혹은 $a_t +1$이 되게 된다.
$a$가 $t$의 기우성에 따라 일차 점화식의 합성으로 나타나므로, 홀수일 때의 점화식을 짝수일 때의 점화식에 넣어 식을 적당히 정리하면 $(n-1)$에 대한 거듭제곱과 공비가 $-1$인 등비수열의 합으로 나타나게 된다. 뒤쪽 등비수열을 등비수열 공식에 넣어 계산하면 $a$를 거듭제곱이 지배하는 복잡도인 $O(\log T)$에 계산할 수 있게 된다(나눗셈이 있어서 모듈러 인버스를 써야 한다). 그 후 실제로 곱해서 계산해주면 된다.
저 일차 점화식의 합성이 굉장히 쉬운 부분인 것 같은데, 나는 저런 부분을 평소에 잘 못봐서(수올러가 아니라...) 많이 애먹었다. 그것만 빼면 무난무난한 문제인 것 같다.
5951 The Continental Cowngress
$N$이 작다. 각 변수에 대해서 $Y$와 $N$ 각각 고정시켜보고 투샛 한번씩 돌리면 된다.
21815 Portals
문제가 상당히 이해하기 어렵다. 정말 정말 어렵다...
각 포탈을 정점으로 바꾸고 각 정점의 permutation 관계를 간선으로 생각하자. 그러면 포탈이 $2N$개 있고, 기존 그래프에서 $p_1$ $p_2$ $p_3$ $p_4$가 있을 때 $p_1$과 $p_2$, 그리고 $p_3$와 $p_4$를 각각 간선으로 이어줄 수 있다. 핵심적인 관찰은 이렇게 간선을 이으면 바뀐 그래프에서 모든 정점의 차수가 2이므로 disjoint cycle을 형성한다는 것이다.
만약 내가 돈을 내고 permute해서 간선을 바꿔먹는다면, 네 점이 만드는 사각형의 변이 토글되는 느낌으로 생각할 수 있다. 중요한 부분은 만약 그 네 사각형이 서로 다른 cycle에 걸쳐 있다면, 변을 토글했을 때 두 cycle이 합쳐지면서 하나의 cycle로 바뀐다는 것이다. 따라서 각 사이클을 컴포넌트라고 생각하고 permute하는 것을 간선을 추가하는 것으로 생각하면 MST 문제가 된다.
따라서 모든 permutation을 비용 순서대로 정렬하고 MST 문제를 해결하면 된다.