[BOJ] 14180번: 배열의 특징

https://www.acmicpc.net/problem/14180

수를 하나 이동했을 때 값이 얼마나 달라지는지를 생각해봅시다.

우선 $S_i = A_1+A_2+..+A_i$라고 두고, a번째 위치에 있던 원소를 b번째로 옮길 때, a가 b보다 큰 경우(=왼쪽으로 옮기는 경우)에는 $S_{a-1}-S_{b-1}-(a-b)A_a$만큼 변화하고 a가 b보다 작은 경우(=오른쪽으로 옮기는 경우)에는 $S_a-S_b+(b-a)A_a$만큼 변화합니다. 왼쪽으로 옮기는 경우와 오른쪽으로 옮기는 경우의 식이 다르기 때문에 각각에 대해 정리를 해보면 기울기가 $b$이고 y절편이 $S_{b-1} or S_b$인 식을 얻을 수 있게 되고 이를 이용해 Convex Hull Trick을 적용하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/14180.cpp