2023 Sogang Programming Contest Open

사람들의 번호는 서로 다르다는 것에 집중해 봅시다.

$i$번 사람과 $j$번 사람이 배정받은 집을 교환할 수 있고, $j>i$라고 가정해 봅시다.이때 $A_i > A_j$를 만족한다면, 두 사람은 집을 교환하는게 이득입니다.

사람들의 번호는 서로 다르기 때문에 위의 상황에서 세금의 감면되는 양은 순증가합니다. 따라서 최적해에서는 $j>i$ 이면 $A_i \leq A_j$를 만족합니다.

결론적으로 집을 교환가능한 사람들의 부분 수열을 오름차순 정렬하는 것이 주어진 쿼리의 결과라고 할 수 있고, 유일하게 결정됩니다.

$N$이 $300$ 이하이므로 쿼리마다 나이브하게 정렬해주면 문제가 해결됩니다.

댄스타임에서는 최대 한 번까지 올바르지 않은 춤을 추더라도 해당 라운드를 통과할 수 있습니다. 따라서, 아래와 같이 두 가지 경우로 나누어서 각각의 경우의 수를 구한 후 더해 답을 구하면 됩니다.

- 모든 라운드를 통과한 경우
- 오직 한 번의 라운드에서만 동과하지 못하고, 나머지 라운드에서 통과한 경우
  - 앞을 봐서 통과 못한 경우
  - 뒤를 봐서 통과 못한 경우

모든 라운드를 통과하는 경우의 수를 구하기 앞서, 한 라운드를 통과하거나, 통과하지 못하는 경우의 수를 구해봅시다. 열은 우진이 춤을 출 때 보는 방향, 행은 라운드 통과 여부를 나타냅니다.

|   | 앞 | 뒤 |
| -- | -- | -- |
| 통과함 | $1$ | $M-1$ |
| 통과하지 못함 | $M-1$ | $1$ |

이제 모든 라운드에 대한 경우의 수를 구해봅시다. 모든 라운드 중 우진이 뒤를 보고 춤을 춘 횟수를 $C$라 하겠습니다.

- $(M-1)^{C}$개
- 아래 두 경우의 수의 합
  - $(N-C)(M-1)^{C+1}$개
  - $C \geq 1$이면 $C(M-1)^{C-1}$개, 아니면 $0$개

위에서 구한 경우의 수를 모두 합한 값이 답입니다. Integer overflow에 주의하여 모든 연산 과정에서 소수 $1\,000\,000\,007$로 나눈 나머지로 연산해야 하는 것에 주의합시다.

이 문제는 여러 개의 범위가 주어질 때 한 번 이상 범위에 포함된 센서의 개수를 구하는 문제입니다.
이는 imos법을 이용하여 해결할 수 있습니다.

- $P[i]$를 입구로부터 벽을 따라 반시계 방향으로 $i^\circ$만큼 이동한 곳에 위치한 센서의 블레이즈 감지 여부라고 합시다.
- 어느 한 번의 지시로 센서가 $s$부터 $e$까지의 범위 블레이즈를 감지할 때, $P[s]$에 $1$을, $P[e+1]$에 $-1$을 더해줍니다.
- 모든 지시에 대해 위와 같은 방식으로 처리합니다.
- $P[i]$의 모든 범위에 대해 누적합을 구했을 때, $P[i]$가 $1$보다 크거나 같으면 블레이즈를 감지함, $0$이면 블레이즈를 감지하지 못했음을 뜻하게 됩니다.
- 모든 $i$에 대하여 $P[i] \geq 1$인 $i$의 개수를 출력하면 됩니다.

어느 한 번의 지시로 인한 블레이즈의 범위는 원주각과 중심각의 관계를 이용해 구할 수 있습니다.
- 점 $P$를 점 $O$에 대해 대칭시킨 점을 점 $M$라 합시다.
- 중심각은 원주각의 2배이고 $\angle{LPR}=b^\circ$이므로 $\angle{LOM}=\angle{ROM}=b^\circ$입니다.
- 따라서, 점 $M, L, R$에 해당 하는 위치는 각각 $a+180, a+180-b, a+180+b$로 표현할 수 있습니다.

센서는 원을 이루며 위치해 있으므로 나머지 연산을 취하여 각각의 위치를 $0$보다 크거나 같고, $359$보다 작거나 같은 위치로 대응시킨 후 imos법을 적용하면 답을 구할 수 있습니다.

이 문제는 $1$번부터 $N$번까지의 숙우에서 물 별로 이동해야 하는 횟수가 주어진 것으로 보아도 됩니다. 
또한 한 숙우에서 다른 숙우로 물이 이동하는 것은 **두 물을 바꾸는 것**과 같습니다.

우선 가능한 케이스와 불가능한 케이스를 분류해야 합니다.
각 숙우에 담긴 물의 번호를 길이 $3$의 순열로 나타내면 총 $6$가지가 가능합니다. 
물을 한 번 이동할 때 이 순열이 어떻게 바뀌는지 그래프로 그려보면 다음과 같습니다.

![순환 그래프: 1, 2, 0 ↔ 0, 2, 1 ↔ 2, 0, 1 ↔ 2, 1, 0 ↔ 0, 1, 2 ↔ 1, 0, 2 ↔ 1, 2, 0](https://static.solved.ac/arena/editorial/12/three-1.png)

물을 이동하는 것은 순열의 두 원소를 바꾸는 것과 동일하므로 순열의 **홀짝성**이 바뀝니다.

시작 순열 $1, 2, 0$은 짝순열이므로 물을 짝수 번 이동하면 **짝순열**, 홀수 번 이동시 **홀순열**입니다. 
따라서 목표 순열이 짝순열인데 물을 홀수 번 이동해야 하거나 그 반대인 경우에는 목표를 달성할 수 없습니다.

그리고 물마다, 목표 순열에서의 위치가 초기 순열과 다르면서 이동해야 하는 횟수가 $0$인 경우, 혹은 목표 순열에서의 위치가 초기 순열과 같으면서 이동해야 하는 횟수가 $1$인 경우도 불가능합니다.
그 외의 경우는 모두 가능합니다.

물 $1$이 이동해야하는 횟수 $n_1$은 $(100-t_1)/5$, 물 $2$의 이동 횟수 $n_2$는 $(100-t_2)/5$로 구할 수 있습니다. 총 이동 횟수 $K$는 $n_1 + n_2$입니다.

예를 들어 목표 순열이 $2, 0, 1$이고 $n_1$이 홀수이면 다음과 같은 과정으로 목표에 도달할 수 있습니다.
- 물 $1$을 빈 숙우로 옮기고, 이어서 물 $2$를 빈 숙우로 옮깁니다.
- 그 다음 물 $1$을 빈 숙우로 $n_1-1$번 옮기고 물 $2$를 $n_2-1$번 옮깁니다.
나머지 경우에도 동일한 방법으로 과정을 구성할 수 있습니다.

이외에도 너비 우선 탐색과 같은 완전 탐색을 이용하는 풀이도 있습니다.

연결된 간선의 종류와 관계없이, 어떤 점이든 도달하고 난 후 $12$분 후에는 원래 점으로 돌아올 수 있습니다. 따라서 $x$분에 특정 정점에 도달했다면 $x + 12, x + 24, \cdots, x + 12 \times k$분 후에는 항상 해당 점에 올 수 있습니다.

도달한 시각을 $12$로 나눈 나머지를 이용해 각 정점을 $12$개로 분할해서 데이크스트라 알고리즘을 수행하면 됩니다.

두 경우로 나누어 해결하면 됩니다.
1. $M \leq N - 1$인 경우
  - $M$개의 $1$, $(N - M)$개의 $0$으로 $a$를 구성하면 됩니다.
2. $M \geq N$인 경우
  - $a_1 = 0$으로 둡니다.
  - $k = \left\lfloor \frac{N}{2} \right\rfloor$이라고 합시다.
  - $a_2 = a_3 = \cdots = a_{k + 1} = 1$으로 채웁니다.
  - $a_{k+2}$부터 $k+1$을 채우다가, $\text{sum}(a) \geq M$이 되는 순간 멈춥니다.
  - 넘치는 값은 빼주고, 나머지는 $0$으로 채우면 됩니다.

이게 왜 될까요? $M \leq N - 1$인 경우는 자명하니, $M \geq N$인 경우만 확인하겠습니다.
- $1$부터 $(k+1)$까지는 쉽게 만들 수 있습니다.
- $a_{k+2}$를 오른쪽 끝점으로 두고, 왼쪽 끝점을 움직여서 $(k+1)$부터 $(2k+1)$까지 만들 수 있습니다.
- $(2k+2)$는 $(a_{k+2}+a_{k+3})$으로 만들 수 있습니다.
- 또다시 왼쪽 끝점을 움직여서 $(2k+2)$부터 $(3k+2)$까지 만들 수 있습니다.
- 이를 반복해서 $M$까지의 모든 수를 만들 수 있습니다.
- 더 정확히, $N$이 홀수면 $\frac{N^2+2N-3}{4}$, 짝수면 $\frac{N^2+2N-4}{4}$까지 만들 수 있고, 이는 $M$ 제한에 충분히 들어옵니다.

각 쿼리는 독립적이므로, 이를 순서대로 처리할 필요는 없습니다.

$(N+M)$개의 점을 원점을 중심으로 하여, 반시계 방향으로 정렬합시다. 만약 두 점의 기울기가 같은 경우에는 검은색 점이 앞에 오도록 정렬합시다. 이제 우리는 원점을 지나며 기울기가 양수인 어떤 직선 아래의 점들을 관리할 수 있습니다.

세그먼트 트리를 이용합시다. $seg_i$는 해당 노드가 담당하는 $x$좌표 구간에 속하는 검은색 점들의 개수입니다. 이때 $x$좌표의 최댓값이 $10^9$이므로, 좌표 압축을 해야 합니다.

편의 상 쿼리에서 주어지는 점을 **흰색 점**이라고 하겠습니다.
- 만약 현재 확인 중인 점이 검은색 점이라면 해당 $x$좌표에 update하면 됩니다.
- 흰색 점이라면 구간 $[1, x]$에 속하는 검은색 점들의 개수를 구하면 됩니다.

전체 시간복잡도는 $O(N \log N)$입니다.

이 문제는 $2023$ 서강대학교 청정수컵의 [〈$K$512에서 피자 먹기〉](https://www.acmicpc.net/problem/28072) 문제의 강화판입니다.
누적합과 관련된 아이디어는 해당 문제에서 누적합을 사용하는 이유와 거의 동일하니 참고하면 좋을 것 같습니다.

이 문제의 첫번째 진입장벽인 정산 결과 실제로 각 사람이 얻거나 잃게 되는 점수만 고려하면 된다는 점은 문제에서 주어지므로 받아들이고 넘어가면 됩니다.
정산 결과 각 사람이 얻거나 잃게 되는 점수 $score[i]$는 남은 카드의 총 개수를 $total$이라고 했을 때 $total - card[i] \times n$으로 쉽게 계산할 수 있습니다.

카드를 교환할 때 $n$명의 사람들의 $score$의 합이 $0$이라고 하면 $n-1$번의 거래로 항상 정산을 마칠 수 있습니다. 간단하게, 뽑은 $n$명의 사람들에게 번호를 매기고 $1$번 사람이 각 $i$번 사람과 $score[i]$에 해당하는 교환을 하면 자연스럽게 정산이 완료되는 모습을 생각하면 됩니다.

반대로 $n$명의 사람들이 어떤 크기가 $n$보다 작은 부분집합을 이루어도 $score$의 합을 $0$으로 만들 수 없다면 $n-1$번보다 적은 횟수의 교환으로 정산하는 것이 불가능합니다.

그래프 이론을 이용하여 간단하게 증명해 보겠습니다.

- 각 사람을 정점으로 취급하고, 교환을 하나의 간선으로 취급합니다. 이렇게 그래프를 만들었을 때, 사이클이 생긴다면 항상 없애줄 수 있습니다. 따라서 사이클이 있는 그래프는 최적이 아니며, 우리는 항상 트리를 만들 수 있습니다.
- 연결된 노드들의 $score$의 합이 $0$이면 간선을 따라 한번씩 교환해서 해당 사람들끼리는 정산이 가능합니다. 만약 합이 $0$이 아니면 외부의 다른 집단과 연결할 새로운 간선이 필요하게 됩니다.
- 트리의 간선의 수는 항상 $n - 1$이므로 많아봤자 $n - 1$번의 교환으로 정산 가능하다는 것은 보여졌습니다.
- 반대로 더 적은 간선으로는 그래프의 모든 정점을 연결시킬 수 없습니다. 따라서 적어도 $n-1$번의 교환이 필요하다는 것도 보여졌습니다.


다행히 이 문제는 간선의 구조가 매우 간단합니다. $score$의 누적합이 $0$이 될때마다 배열을 끊어주면 각각의 연결된 배열들이 합이 0이 되므로 이웃한 사람들끼리만 교환했을 때의 교환의 최솟값을 쉽게 구할 수 있습니다.

임의의 한 쌍의 사람을 골라서 교환을 시키는 경우도 누적합의 관점으로 관찰하면 어렵지 않게 해결할 수 있습니다.
- $i < j$인 $i, j$를 골랐다고 가정하고 $j$번 사람이 $i$번 사람에게 $x$만큼의 점수를 줬다고 생각합시다(반대로 점수를 받았다면 $x$를 음수 취급하면 됩니다).
- 그러면 $score[i]$를 포함해 $score[j]$ 이전 까지의 누적합은 전부 $x$만큼 커졌다고 생각할 수 있습니다. 그리고 그 $j$뒤는 원래대로 돌아옵니다.
- 변화한 상태에서 다시 누적합이 $0$이 될 때마다 배열을 끊어주면 됩니다.

아래 그림은 $2$번 예제에서 $i$가 $0$, $j$가 $5$로 선택되고 $x$는 $-10$인 경우입니다. 주어진 배열인 $card[]$로 부터 $score[]$를 만들고, 다시 누적합을 한 배열임에 유의합니다.

![배열 10, 10, 0, 10, 10, 10, 0, 20, 30, 0을 0 0, -10, 0, 0, 0, 0, 20, 30, 0으로 변환](https://static.solved.ac/arena/editorial/12/lexio_solution_01.png)

이때는 $0$의 개수가 총 $7$개이므로, 실제로 이뤄지는 교환 횟수는 $10 - 7 = 3$이 됩니다. 실제 답은 $i, j$의 교환까지 추가해 $4$가 됩니다.
이때 특정 연속 구간의 값을 $x$만큼 늘리면 전체 $0$의 개수는
$$
((\text{해당 구간 내에서 }-x\text{의 등장 횟수})-(0\text{의 등장 횟수}))
$$
만큼 이득을 본다는 점을 쉽게 파악할 수 있습니다.

이제 $i$와 $j$를 먼저 선택하지 말고, $x$를 먼저 선택하는 방식으로 생각을 바꾸면, 우리는 누적합 배열에서 $-x$는 $1$로, $0$은 $-1$로, 그 외의 수는 $0$으로 바꾼 배열에서 카데인 알고리즘을 수행하여 $x$에 따른 교환 횟수 감소의 최댓값을 구할 수 있다는 걸 알 수 있습니다.

누적합 배열에 등장하는 모든 수에 대해 위와 같은 방식으로 최적값을 구하면 되는데, 그냥 진행하면 $O(n^2)$이 되므로 적당한 최적화가 필요합니다.

- 좌표 압축을 사용해 여러개의 카데인을 병렬로 수행하거나 잘 정렬해서 같은 값을 갖는 부분만 추출해서 따로따로 카데인을 해주면 $O(n \log n)$으로 최적값을 전부 구할 수 있으며, 그 값을 이용해 답을 구하면 됩니다.
- 단, `map`과 `unordered_map`을 사용하는 풀이는 다른 풀이와 실행시간 차이가 너무 커서 다른 시간복잡도의 풀이가 풀리는 이유로 사용을 제한했습니다.

다음은 정렬을 이용해 카데인을 하는 예시입니다.
아래 $2$개의 배열 중 위쪽 배열은 누적합 배열에 대해 (값, 인덱스) 형태로 저장해 정렬한 $sorted\_psum[]$ 배열로, $0$은 사전에 제외해도 되고 안해도 됩니다.
그리고 아래쪽 배열은 $0$의 개수를 누적해 놓은 배열 $zero\_psum[]$입니다.

![배열 (10, 0), (10, 1), (10, 3), (10, 4), (10, 5), (20, 7), (30, 8)과 배열 0, 0, 1, 1, 1, 1, 2, 2, 2, 3](https://static.solved.ac/arena/editorial/12/lexio_solution_02.png)

$sorted\_psum$을 차례대로 보면서 같은 값에 대해서만 카데인을 해주고, 서로 같은 값 사이의 $0$의 개수는 $zero\_psum$을 이용해 구하면 됩니다.
