SASA Programming Contest 2023 Open Contest Div. 1

구간 안의 꽃을 확인하거나 없애는 두 가지 쿼리를 처리해야 합니다.

Easy 문제는 단순히 한 칸씩 직접 꽃을 확인해 보거나 없애는 것으로 충분히 해결할 수 있습니다.

시간복잡도는 $\mathcal{O}\left({QN}\right)$입니다.

실험 결과 광합성을 **하고** 운동성이 없는 생물은 **반드시** 식물입니다. 반대로 광합성을 하지 **않거나** 운동성이 있는 생물은 **반드시** 식물이 아닙니다.

식물의 최솟값은 **반드시** 식물인 생물의 수, 최댓값은 전체 생물 수에서 **반드시** 식물이 아닌 생물의 수를 뺀 값을 구하면 됩니다.

시간복잡도는 $\mathcal{O}({N+M})$입니다.

첫 손은 모두 가위로 결정되어 있으므로 실제로 손 모양을 골라서 대결할 수 있는 수는 최대 $100$회입니다. 한 번의 대결로 하나의 손 모양을 확정할 수 있어야 합니다.

손 모양 하나를 가위에서 바위로 바꿔 대결을 진행해 봅시다. 머신의 손 모양에 따라 세 가지 결과가 나타납니다.
- 머신이 가위를 낸 경우 세종이가 이긴 횟수는 $1$ 증가합니다.
- 머신이 바위를 낸 경우 세종이가 이긴 횟수는 그대로입니다.
- 머신이 보를 낸 경우 세종이가 이긴 횟수는 $1$ 감소합니다.

따라서 첫 대결과 다른 하나의 대결의 결과를 토대로 이기는 손 모양 하나를 **반드시** 알아낼 수 있습니다.

문제를 풀기 위해 두 가지 과정을 거쳐야 합니다.

- 물이 고인 칸의 위치 확인
- 발을 디딜 수 있는 방법들 각각에 대해 물이 고인 칸이 있는지 확인

물이 고인 칸의 위치는 하수구에서부터 BFS 등을 이용해 물이 빠진 칸을 찾아주는 것으로 처리할 수 있습니다. 물이 빠진 칸의 개수로 2차원 누적 합 배열을 만들면 가능한 모든 발을 딛는 경우의 수에 대해 그중 물이 고인 칸이 있는지 빠르게 판정할 수 있습니다.

따라서 총 시간복잡도 $\mathcal{O}({NM})$에 문제를 해결할 수 있습니다.

문제를 요약하면 조건을 만족하는 $S$와 $G$를 간선으로 이은 그래프에서의 최대 매칭을 구하는 문제가 됩니다. 여기서 플로우 문제임을 관찰한 후 그냥 호프크로프트-카프를 이용해 해결하는 것도 가능합니다.

그런데 $S$와 $S$, $G$와 $G$를 직접 잇는 간선이 없기 때문에, 이 문제에서 모델링되는 그래프는 $S$와 $G$에 대한 **이분 그래프**입니다.

따라서 단순 이분 매칭을 구현하는 것으로 시간 복잡도 $\mathcal{O}({N^2 M^2})$에 문제를 해결할 수 있습니다.

고차원의 하이퍼 삼각형을 문제 지문대로 그려서 잘라보는 것은 복잡합니다. 하이퍼 삼각형을 보다 다루기 쉬운 형태로 변형시켜 봅시다.

하이퍼 삼각형의 모서리 하나를 다른 모서리에 수직하도록 만드는 선형 변환을 생각해 봅시다. 그러면 그 변환을 벡터공간 $\mathbb{R}^M$ 전체를 정의역으로 갖는 전단사 사상으로 표현할 수 있습니다. 이는 변환 전후의 두 도형이 위상 동형임을 의미합니다. 이러한 변환을 여럿 결합해도 여전히 도형은 위상 동형입니다.

따라서 하이퍼 삼각형을 적절히 *비틀어서* 어떤 한 점에서 만나는 $M$개의 모서리가 각각 서로 수직하도록 만들어도 좋습니다. 이는 한 꼭짓점을 시점으로, 나머지 $M$개의 꼭짓점을 종점으로 갖는 $M$개의 벡터를 기저로 설정한 벡터공간을 생각하는 것과 같습니다. 이때 원래의 공간에서 하이퍼 삼각형의 형태를 변환한 형태도 편의 상 하이퍼 삼각형으로 부르겠습니다.

수직하는 $M$개의 모서리가 만나는 점을 원점으로 잡고, 나머지 $M$개의 꼭짓점을 각각 하나의 축 위에 올라가도록 합시다.
이제 하이퍼 삼각형을 잘라 얻은 조각의 꼭짓점은 모두 음이 아닌 정수 좌표를 갖습니다. 각 점의 좌표를 $(x_1, x_2, \ldots, x_M)$ 으로 둡시다.
이때 한 점의 좌푯값을 모두 더한 값은 항상 $N$ 이하입니다. 이 조건을 만족하는 음이 아닌 정수 좌표는 **모두** 하나 이상의 조각의 꼭짓점입니다.

방금 전 변환에 의해 $M$개의 모서리가 서로 다른 $M$개의 축 위에 올라갑니다.
이는 즉 모든 가능한 하이퍼 삼각형 조각의 $(M-1)$차원 면은 $x_i = t$ 또는 $\sum_i x_i = t$ 꼴로 나타낼 수 있는 면에 포함됨을 의미합니다.

따라서 어떤 하이퍼 삼각형에 대해 $M$개의 모서리가 서로 수직으로 만나는 점을 지나는 모서리의 길이는 모두 같고 $(M-1)$차원 도형인 $\sum_i x_i = t$와 만나야 합니다. 또한 모든 하이퍼 삼각형은 이러한 점을 딱 하나만 꼭짓점으로 갖습니다. 즉, 수직 꼭짓점과 그 꼭짓점을 지나는 모서리의 길이 그리고 방향으로 하이퍼 삼각형 하나를 특정하는 것이 가능합니다.
이를 만족하기 위해서는 $M$개의 모서리가 한 점으로부터 **모두** 양의 방향으로 뻗거나 **모두** 음의 방향으로 뻗어야 합니다.

이제 문제를 처음 하이퍼 삼각형의 경계 또는 내부에 있는 모든 정수점들에 대해 음의 방향으로 뻗을 수 있는 거리와 양의 방향으로 뻗을 수 있는 거리의 총합을 계산하는 문제로 바꿀 수 있습니다.
한 정수점에서 음의 방향으로 뻗을 수 있는 거리는 각 점의 $M$개 축에 대한 좌표 중 최솟값과 같습니다.
즉 음의 방향으로 $K$ 만큼 뻗을 수 있으려면 모든 좌표가 $K$ 이상이어야 합니다. 이는 모든 축 방향으로 $K$만큼을 더하고 나머지 $N-MK$를 $M$개의 서로 다른 차원에 나누어 주거나 일부는 나누어 주지 않는 경우의 수와 같습니다.

한 정수점에서 양의 방향으로 뻗을 수 있는 거리는 그 점의 $M$개 축에 대한 좌푯값을 모두 더한 값을 $S$로 두면 $N-S$와 같습니다. 왜냐하면 모서리를 $1$만큼 뻗은 끝점의 좌푯값의 합은 원래의 점의 좌푯값의 합보다 반드시 딱 $1$ 증가하기 때문입니다.
따라서 $K$개의 양의 방향으로의 하이퍼 삼각형이 만들어지는 꼭짓점의 개수는 $N-K$를 $M$개의 축에 나누어주는 방법의 수와 같으므로 중복조합을 이용해 $\left(\!\middle(\genfrac{}{}{0pt}{}{M}{N-K}\middle)\!\right) = \binom{M+N-K-1}{N-K}$로 표현할 수 있습니다.
따라서 모든 양의 방향으로의 하이퍼 삼각형의 개수는
$$
\sum_{K=1}^{N} \binom{M+N-K-1}{N-K}
$$
입니다.

팩토리얼 값과 그 모듈로 곱셈 역원의 값을 전처리해 두면 각 연산은 $\mathcal{O}({1})$에 처리할 수 있습니다.
따라서 총 시간복잡도는 $\mathcal{O}({N+M})$ 입니다.

두 사람의 목표는 마지막 날의 게임에서 이기는 것입니다. 마지막 날에는 꽃이 있는 꽃집이 하나밖에 남지 않기 때문에 선공이 항상 이깁니다. 즉 마지막 게임을 이기려면 그 전 게임에서 반드시 승리해야 합니다.

이를 확장해 마지막 날부터 거꾸로 확인하면서, 마지막 게임에서 이기기 위해서 $i$번째 날에 이겨야 할지 혹은 져야 할지를 판단할 수 있습니다.

각 날의 게임은 이겨야 하는지 져야 하는지에 따라 각각 님 게임 또는 Misère 님 게임으로 볼 수 있습니다. 두 종류의 게임은 스프라그-그런디 정리를 통해 선후공 중 누가 필승인지 알아낼 수 있습니다.

꽃집의 꽃을 합치는 과정에서 각 꽃집의 꽃의 종류를 모두 고려해 주어야 합니다. 이를 빠르게 수행하기 위해 작은 집합에서 큰 집합으로 합치는 테크닉을 사용할 수 있습니다. 시간복잡도는 $\mathcal{O}({N \log^{2} N})$입니다.

### 선형 해법

각 꽃집에 있는 꽃의 종류의 수를 각 돌무더기에 있는 돌의 개수로 바꿔 생각합시다. 모든 꽃의 종류가 같은 경우 합치는 과정을 생략할 수 있습니다. 따라서 $\mathcal{O}({N})$에 문제를 풀 수 있습니다. 이제 종류가 다른 꽃이 있는 경우를 생각해 봅시다.

가장 처음 상황에서 돌무더기의 돌의 수는 모두 $1$이고 이때는 세종이와 아름이에게 가능한 선택의 수가 한 가지 뿐이므로 직접 계산을 통해 승패를 알 수 있습니다.
그러다 어느 순간 종류가 다른 꽃이 있는 꽃집끼리 합쳐지면, 돌무더기의 돌의 수는 하나의 $2$와 여러 개의 $1$로 구성됩니다.

돌이 $2$개 이상 있는 돌무더기가 존재하는 경우, 그런디 넘버가 $0$이 아니라면 님 게임과 Misère 님 게임 모두 선공이 이길 방법이 반드시 존재하고, 반대로 그런디 넘버가 $0$이면 후공이 이길 방법이 반드시 존재합니다.
그런데 처음으로 돌이 $2$개 있는 돌무더기가 만들어지는 상황에서의 그런디 넘버는 항상 $2$ 이상이므로 선공이 마지막 꽃을 가져갈 지 선택할 수 있습니다.
따라서 이후의 게임의 결과를 **이때의 선공 플레이어가 마음대로 정할 수 있습니다**.

결론적으로 처음 다른 종류의 꽃을 가진 꽃집끼리 합쳐질 때까지 승패 판정만 해주면 합치는 과정 없이 마지막 게임의 승자를 알 수 있습니다.
돌무더기에 돌이 1개씩 밖에 없는 게임은 $\mathcal{O}(1)$에 승패를 판정할 수 있으므로 총 시간복잡도는 $\mathcal{O}(N)$입니다.

문제에서 입력되는 꽃의 종류 배열을 편의상 $A$라고 하겠습니다.

$A$를 꽃의 종류에 대해 오름차순으로 정렬합니다. 이때 꽃의 종류가 같다면 꽃이 위치한 인덱스에 대해 오름차순으로 정렬합니다. 이를 통해 $A$에서 같은 종류의 꽃끼리 붙어 있게 만들 수 있습니다.

정렬된 전과 후의 꽃들의 인덱스 변화를 배열을 통해 저장합니다. 정렬 후 $A$에 대해 밟히지 않은 꽃의 갯수로 세그먼트 트리를 구축할 수 있습니다.

### 1번 쿼리

꽃의 종류에 따라 정렬 전 $A$에 그 종류를 가진 꽃들의 인덱스들을 set을 통해 관리합니다.

꽃의 종류가 $k$인 꽃들의 인덱스들을 저장한 set에서 이분 탐색을 사용할 수 있습니다. 이를 통해 정렬 전 $A$의 배열에서 $l$번 칸과 $r$번 칸 사이에 있는 종류가 $k$인 꽃의 인덱스들 중 최소와 최대를 $\mathcal{O}({\log N})$으로 구할 수 있습니다. 이를 $s$와 $e$라고 부르겠습니다.

정렬 후 $A$에서 $s$와 $e$에 대응되는 인덱스에 대해 밟히지 않은 꽃들을 세그먼트 트리로 구한다면 1번 쿼리를 $\mathcal{O}({\log N})$에 해결할 수 있습니다.

### 2번 쿼리

밟히지 않은 꽃들의 정렬 전 $A$에서의 인덱스들을 set을 통해 관리합니다.

밟히지 않은 꽃들의 인덱스들을 저장한 set에서 이분 탐색을 사용할 수 있습니다. 이를 통해 정렬 전 배열 $A$에서 $l$ 이상 $r$ 이하 인덱스를 가진 꽃들 중 밟히지 않은 꽃들을 모두 알 수 있습니다. 이때 시간복잡도는 $\mathcal{O}({\log N})$입니다.

해당하는 꽃들을 세그먼트 트리에서 값을 업데이트합니다. 이때 시간복잡도는 $\mathcal{O}({\log N})$입니다.

이후 해당하는 꽃들을 모두 set에서 삭제합니다. $N$개의 인덱스들은 모두 최대 한 번씩만 삭제 및 업데이트되므로, 전체 시간복잡도는 $\mathcal{O}({Q\log N + N\log N})$ 입니다.

이외에도 제곱근 분할법이나 g++의 policy-based 자료구조를 이용해서도 문제를 해결할 수 있습니다. 제곱근 분할법을 이용하는 경우 버킷의 크기를 최적화하는 것이 좋습니다.