A_

1. A. Strange Device

시간 $t = q B + r$ 이라 하자. $x = (q (B + 1) + r)$ , $y = r$ 로 정의되므로, $(x_{t_{1}}, y_{t_{1}}) = (x_{t_{2}}, y_{t_{2}})$ 이기 위해서는 $t_{1} \equiv t_{2} (m o d B)$ 이면서 $⌊ t_{1} / B ⌋ \equiv ⌊ t_{2} / B ⌋ (m o d A / g c d (A, B + 1))$ 여야 한다.

이 두 조건을 하나의 조건으로 합칠 수 있는데, $t_{1} \equiv t_{2} (m o d A B / g c d (A, B + 1))$ 로 표현할 수 있다.

따라서 구간 $l_{i}, r_{i}$ 를 $A B / g c d (A, B + 1)$ 로 나눈 나머지의 구간으로 표현한 다음 서로 다른 나머지값의 개수를 세주면 된다.

2. B. Bridges

문제

2.1. Subtask 1

단순히 앞에서부터 쿼리를 처리하면서 간선의 무게 제한을 Update 해준다.
2번 쿼리가 들어오면 DFS나 BFS 같은 그래프 탐색 알고리즘을 통해 도착할 수 있는 섬의 수를 구하면 된다.

2.2. Subtask 2

그래프가 아닌 직선에서 문제를 해결하는 서브태스크다.
각 2번 쿼리에 대해 직선에서 왼쪽, 오른쪽으로 이동하면서 처음으로 만날 수 있는 $w_{j}$ 미만의 무게 제한을 가진 간선을 찾으면 각 2번 쿼리에 답할 수 있다.
Segment Tree를 사용하여 각 구간에 포함된 간선들의 무게 제한 중 최솟값을 저장하고 있으면 Binary Search를 사용하거나 Segment Tree 내부 처리를 통해 $w_{j}$ 미만의 무게 제한을 가진 가장 가까운 간선을 찾을 수 있다.

2.3. Subtask 4

서브태스크 4가 서브태스크 3보다 쉽다...
간선 무게 제한 Update 연산이 없으므로 Query 연산(2번 쿼리)과 기존에 주어진 간선에서 주어진 무게 내림차순으로 정렬하여 오프라인으로 쿼리를 해결할 수 있다.
Union & Find를 통해 간선으로 이어진 섬을 하나의 그룹으로 묶어주고, Query 연산이 주어지면 $s_{j}$ 가 포함된 그룹에 속한 섬 개수가 해당 쿼리에 대한 답이 된다.

2.4. Full Solution

Subtask 4의 아이디어에 Sqrt Decomposition의 아이디어를 사용하여 해결할 수 있다.

앞에서부터 SZ개의 쿼리를 묶어서 처리한다고 생각하자.
SZ개의 쿼리에는 1번 쿼리와 2번 쿼리가 섞여 있지만, 1번 쿼리도 최대 SZ개, 2번 쿼리도 최대 SZ개 존재한다는 것을 생각할 수 있다.
SZ개 쿼리에 1번 쿼리에 의해 무게 제한이 바뀌는 에지들과(최대 SZ개) 무게 제한이 바뀌지 않는 에지들(최대 M개)를 구분하여 생각하자.
- 무게 제한이 바뀌지 않는 간선 $e_{a_{i}}$ (최대 M개)
- 오프라인 쿼리를 처리하듯이 2번 쿼리의 무게 제한 $w_{j}$ 와 $e_{a_{i}}$ 의 무게 제한 $r_{a_{i}}$ 을 기준으로 무게 내림차순 정렬하여 처리한다.
- $e_{a_{i}}$ 간선들을 처리할 때 간선이 잇는 두 섬을 Union & Find 알고리즘을 사용하여 한 그룹으로 묶어준다.
- 이렇게 처리하면 2번 쿼리 $(w_{j}, s_{j})$ 를 처리할 때 무게 제한이 바뀌지 않는 에지들 $e_{a_{i}}$ 들 중 무게 제한 $r_{a_{i}}$ 이 $w_{j}$ 이상인 에지들을 통해 연결되어 있는 섬들을 Union & Find로 합쳐져 있는 상태를 유지할 수 있다.
- 무게 제한이 바뀌는 간선 $e_{b_{i}}$ (최대 SZ개)
- 2번 쿼리 $(w_{j}, s_{j})$ 를 처리하기 전에 그 쿼리보다 먼저 주어진 1번 쿼리들을 처리해 줘야 한다.
- 각 2번 쿼리 $(w_{j}, s_{j})$ 를 처리할 때 무게 제한이 바뀌는 간선 $e_{b_{i}}$ 에 대해 다음 두 조건을 모두 검사한다. (최대 SZ개이기 때문에 모두 처리가 가능하다)
  - $(w_{j}, s_{j})$ 보다 먼저 주어진 쿼리
  - 다리 무게 제한 $r_{b_{i}}$ 가 $w_{j}$ 보다 크다
- 위 두가지 조건을 모두 만족하는 경우 Union & Find로 $e_{b_{i}}$ 가 잇는 두 섬을 한 그룹으로 묶어준다.
- 이때 사용하는 Union & Find는 되돌릴 수 있는 연산이여야 하기 때문에 Path Compression이 아닌 Rank/Size Compression을 사용하여야 함을 알 수 있다.
각 2번 쿼리에 대해 위와 같이 간선들을 따로 처리하면 Union & Find를 통해 같은 그룹으로 섬들을 묶고 $s_{j}$ 와 같은 그룹의 섬 개수를 구해주면 문제를 해결할 수 있다.
이때 SZ의 값은 Sqrt Decomposition에서 그룹 개수를 루트로 설정하는 것과 같이 시간복잡도를 최소화할 수 있는 값으로 SZ를 설정하면 된다.

3. C. Street Lamps

3.1. Subtask 1

각 쿼리 (a, b)에 대해 그 전까지의 가로등 반전(최대 N개)을 해보면서 매 시간 (a, b)가 연결되어 있는지 확인한다.
(a, b) 사이 $s_{i} = 0$ 인 $i$ 가 없으면 (a, b)가 연결되어 있다는 것을 알 수 있는데 이것은 구간 내 0의 개수를 저장한 Segment Tree를 쓰면 쉽게 처리할 수 있고, Set으로 구간을 관리하면서도 처리할 수 있다.

3.2. Subtask 2

각 가로등이 켜져 있던 시간을 저장하고 있으면 매번 쿼리에 바로 답할 수 잇다.
$x$ 번째 가로등이 켜져 있던 시간을 $T_{x}$ 라 하면,
- 시간 $i$ 에 $x$ 번째 가로등이 켜지면 $T_{x} = T_{x} - i$
- 시간 $i$ 에 $x$ 번째 가로등이 꺼지면 $T_{x} = T_{x} + i$
시간 $i$ 에 가로등 $x$ 에 대한 쿼리가 들어오면
- 가로등 $x$ 가 켜져 있으면 답은 $i + T_{x}$
- 가로등 $x$ 가 꺼져 있으면 답은 $T_{x}$

3.3. Subtask 3

모든 가로등이 꺼지지 않고 켜지기만 한다.
정류장 a와 정류장 b사이가 연결되기 시작한 시간은 정류장 a와 정류장 b 사이 존재하는 가로등 중 가장 늦게 켜진 가로등이 켜진 시간일 것이다.
따라서 연결되지 않은 가로등의 시간을 $\infty$ 로 초기화 하고 $i$ 번째 가로등이 켜진 시간을 Segment Tree에 Update하고, 쿼리를 Segment Tree의 Max 연산으로 처리하면 된다.

3.4. Full Solution

이어져 있는 가로등의 구간을 Pair를 관리하는 Set으로 저장하여 관리한다.
- 가로등이 토글되면 Set의 구간을 나누거나, Set의 두 구간을 합치는 등의 연산을 하면서 관리한다.
Subtask 2와 같이 가로등이 켜져 있던 시간을 저장하면서 쿼리를 처리한다.
- 가로등 구간을 Set으로 관리하면 구간이 생기거나 없어지는 것을 관리할 수 있다.
- Subtask 2와 다른 점은 구간 (a, b)가 시간 i에 생기거나 없어지면 $a \leq x \leq y \leq b$ 인 모든 구간 (x, y)에 대해 $T_{(x, y)}$ 에 특정 값을 더하거나 빼줘야 한다.
- 따라서 이를 2D Dynamic Segment Tree를 사용하여 처리하면 전체 문제를 Subtask 2와 같은 방식으로 해결할 수 있다.