solved.ac Grand Arena #4 (mirror of Grand Arena Party)

$i$번째 수부터 $j$번째 수까지가 오름차순으로 배열되어있기 위해서는, $i \le k < j$를 만족하는 모든 정수 $k$에 대해 $A_k < A_{k+1}$을 만족해야 합니다.
조건은 인접한 두 수를 비교하는 것만으로 판단할 수 있습니다. 즉, $B_k$를 $A_k < A_{k+1}$을 만족하는지 여부에따라 `True` 혹은 `False`로 나타내면, $i$번째 수부터 $j$번째 수까지가 오름차순이라는 것은, $B_i, B_{i+1}, \cdots, B_{j-1}$ 모두가 `True`라는 것입니다. 

이런 $(i, j)$를 세는 방법은 여러가지가 있습니다. 

- $i = j$ 인 경우에는 항상 오름차순으로 나열되어 있기 때문에, 경우의 수는 기본적으로 $N$이 됩니다.
- $i \ne j$는 연속된 `True`의 블럭을 생각해봅시다. 이 블럭 내부에서 아무렇게나 시작점과 끝점을 잡는 것이 됩니다. 블럭의 길이가 $k$이라면, 서로 다른 두 시작점과 끝점을 잡는 경우의 수는 $\frac{k(k+1)}{2}$입니다. 

답은 $B$에서 연속된 `True` 블럭 길이 $k$에 대해 $\frac{k(k+1)}{2}$를 모두 더한 것에 $N$을 더한 것이 됩니다.  모든 연산은 $\mathcal O (N)$에 처리할 수 있습니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - A - Editorial

최적화 문제를 결정 문제로 바꾸어 해결하는 Parametric search 기법을 활용한 풀이입니다.

먼저 $M$개 중 $X$개의 전자기기를 연결할 수 있는지 판별해 봅시다. 다음과 같은 그리디한 성질을 이용합니다.

- 전자기기를 선택할 때에는 벽과의 거리 제한 $D_i$가 큰 것부터 $X$개를 선택하는 것이 좋습니다.
- 멀티탭을 연결할 때에는 소켓 수 $A_i$가 많은 것부터 벽면에 가까이 연결하는 것이 좋습니다.

연결이 가능한지 판별하기 위해 다음과 같이 연결을 구성해 봅시다.

맨 처음에는 벽과의 거리가 $0$인 소켓 $K$개가 열려 있습니다. 현재 열려 있는 소켓들의 벽과의 거리가 $d$라고 할 때, $X$개의 전자기기 중 거리 제한이 $d$인 전자기기들을 우선 연결합니다. 그 후, 남은 멀티탭 중 소켓 수가 많은 것부터 나머지 소켓들에 연결합니다. 이제 열린 소켓들의 거리가 $d+1$이 되었으므로 위 과정을 반복합니다.

도중에 소켓이 부족해진 경우 $X$개의 전자기기를 모두 연결하는 것이 불가능합니다. 도중에 전자기기를 모두 소진했다면 연결 성공입니다. 멀티탭을 모두 소진했다면 열린 소켓 수와 남은 전자기기 수를 비교하여 연결 가능 여부를 판별할 수 있습니다.

이제 위 알고리즘을 이용하여 연결 가능한 최대 전자기기 수를 구할 차례입니다. $X$에 대한 이분 탐색을 진행하면서, 위 방법을 이용해 $X$개의 전자기기를 연결 가능한지 확인합니다. 연결 가능하면 더 큰 개수 범위를, 불가능하면 더 작은 개수 범위를 탐색합니다. 그러면 $O(\log M)$번의 탐색만에 연결 가능한 최대 전자기기 수 $X$를 구할 수 있습니다. 총 시간복잡도는 $O((N+M) \log M)$입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - B - Editorial


다각형 위의 임의의 점 $P$에 대해서, 다각형의 둘레의 절반을 돌아간 점 $Q$를 구하는 것은 선분의 길이를 구하는 피타고라스의 공식을 사용해서 구할 수 있습니다.

이제, $P$에서 $Q$를 **향해** 선분을 그어서, 왼쪽 다각형의 넓이에서 오른쪽 다각형의 넓이를 뺀 값을 $f(P)$라고 해봅시다. 이 $f(P)$에는 중요한 성질이 있습니다.

- $f(P)$는 $P$의 위치에 따른 연속함수입니다.
  - 간단히 말해, $P$와 $Q$의 위치가 매우 작은 양만큼 변하면, 넓이도 매우 작은 양만큼 변하게 됩니다.
- $f(P) = -f(Q)$
  - $f(P)$는 $P$에서 $Q$를 향해 선분을 긋고, 왼쪽 다각형의 넓이에서 오른쪽 다각형의 넓이를 뺀 것입니다. $Q$에서 $P$를 향해 선분을 그으면 이 두 다각형의 위치가 반대가 되기 때문에, $f(P)$와 $f(Q)$는 서로 절댓값이 같고 부호가 다른 값이 됩니다.

이제 $f$가 $0$ 이상인 점과 $0$ 이하인 점을 찾았습니다. ($P$와 $Q$중 어느쪽이 양수인지는 직접 $f$를 구해보면 됩니다.) 이제, $P$와 $Q$ 사이에는 중간값 정리에 의해 $f(x) = 0$인 지점이 존재하게 됩니다. 이를 실제로 찾는 법은 다음과 같습니다.

- $P$와 $Q$의 중점인 $M$을 잡습니다.
- $f(P)$와 $f(M)$의 부호가 같으면 $P$를 $M$으로, 아니면 $Q$를 $M$으로 바꿉니다.
- 위 과정을 $P$와 $Q$가 충분히 가까워질때까지 반복합니다.

과정을 한 번 진행할 때마다, $P$와 $Q$의 거리는 절반이 됩니다. $f$가 연속함수이기 때문에, $f(P_i)$와 $f(Q_i)$의 부호가 서로 반대인 $P_1, P_2, \cdots$ 와 $Q_1, Q_2, \cdots$를 찾을 수 있고, 이 두 수열이 같은 값으로 수렴하기 때문에 해당 위치가 $f(x) = 0$이 되는 지점입니다.

실제로 프로그래밍으로 이를 구현할때는, $f$값이 오차범위 이내로 들어올 때까지, 혹은 충분히 큰 정해진 횟수만큼 위 과정을 반복해주면 됩니다. 시간복잡도는 위 과정이 $\mathcal O(N)$에 실행 될 수 있기 때문에 $\mathcal O(N \log (N/\varepsilon))$ 정도입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - C - Editorial

연료를 필요한 만큼만 주유하는 대신, 일단 각 주유소에 있는 연료를 모두 챙긴 다음 필요 없는 연료를 버린다고 생각합시다. 단, 어느 주유소의 연료인지 알기 위해서 연료를 섞이지 않게 관리해야 합니다. 실제로 주행할 때에는 연료를 버린 만큼 해당 주유소에서 덜 주유하면 됩니다.

비용을 최소화하기 위해서 두 가지 전략을 사용합니다.

- 차가 이동할 때에는 가지고 있는 연료 중 가장 싼 연료부터 사용합니다.
- 연료를 챙기고 나서 가진 연료의 총량이 $F$를 넘으면, 가진 연료 중 가장 비싼 연료부터 버립니다.

가진 연료의 (가격, 양)을 균형 이진 탐색 트리나 우선순위 큐 등으로 관리하면 위의 두 가지 연산을 amortized $\mathcal{O}(\log N)$에 수행할 수 있습니다. 총 시간복잡도는 $\mathcal{O}(N \log N)$입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - D - Editorial

로봇 청소기가 작동을 중지할지 판별하기 위해서는 이후 동작들을 시뮬레이션해 보아야 합니다. 시뮬레이션 속의 로봇 청소기는 작동을 중지하는 조건을 만족하더라도 영역을 벗어날 때까지, 혹은 영원히 계속해서 작동할 것입니다. 이때, 정답은 시뮬레이션 속의 청소기가 마지막으로 청소한 시점이 됩니다.

로봇 청소기의 좌표 $(r, c)$와 방향 $d$의 쌍을 로봇 청소기의 위치라고 표현하겠습니다. 먼지가 없는 위치에 대해서, 바로 다음 위치는 항상 유일하게 결정됩니다. 즉, 동일한 위치에 놓인 로봇 청소기는 먼지가 있는 칸에 도달하기 전까지 매번 동일한 경로를 따릅니다.

동일한 경로를 매번 계산하는 대신 Union-Find 자료구조를 관리합시다. 가능한 $4HW$개의 위치와 영역 바깥을 정점으로 나타냅시다. 먼지가 없는 위치마다 바로 다음 위치를 부모 정점으로 설정하면, find 연산을 통해 경로의 끝을 찾을 수 있습니다. 경로 압축을 이용하면 amortized $O(\log (HW))$의 시간에 find 연산을 수행할 수 있습니다.

이제 시뮬레이션을 해 봅시다.

- 현재 위치에 먼지가 없다면 find 연산을 통해 경로를 따라갑니다.
- 현재 위치에 먼지가 있다면, 먼지를 청소한 뒤 그 칸에서 가능한 $4$가지 위치에 대해 다음 위치와 union 연산을 수행합니다. 이때, 현재 위치와 다음 위치가 이미 같은 연결 컴포넌트에 속해 있다면 사이클이 생긴 것이므로 이 정보를 현재 컴포넌트에 저장해 둡니다.
- 현재 위치가 영역 바깥이거나 사이클이 있는 컴포넌트라면 작동을 중지합니다.

각 정점마다 부모 정점까지의 거리를 기록해 두고 경로 압축 시 거리를 업데이트해주면, 경로를 따라갈 때 필요한 이동 횟수도 계산할 수 있습니다. 마지막으로 먼지를 청소한 시점까지 이동 횟수의 총합이 정답이 됩니다. 시간복잡도는 $O(HW \log (HW))$입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - E - Editorial

우선, 문제에서 버섯들이 어떤 방식으로 움직이는지를 관찰해봅시다.

- 버섯의 번호를 무시하면, 두 버섯이 만났을 때 버섯이 서로 반대방향으로 돌아가는게 아니라 서로를 지나쳐간다고 생각할 수 있습니다.
- 버섯의 번호를 생각해보면, 버섯의 번호가 왼쪽부터 오른쪽까지 나열된 순서는 바뀌지 않는다는 것을 알 수 있습니다.

즉, 버섯의 위치와 버섯의 번호를 따로 관리해도 됩니다.

이제 버섯이 움직일 때는 방향에따라 항상 모든 버섯이 같이 앞쪽 혹은 뒤쪽으로 움직이게 됩니다. 그리고 머쉬맘이 명령을 내리면 움직이는 앞쪽 혹은 뒤쪽 방향이 바뀌게 됩니다.
처음에 오른쪽을 보고 있고 위치 $x$에 존재했던 버섯과 왼쪽을 보고있고 위치 $4L-x$에 존재했던 버섯은, 앞쪽으로 $4L-x$, 혹은 뒤쪽으로 $x$만큼 움직인 적이 있으면 떨어지게 됩니다. 결국, 어떤 상황에서 중요한 것은 현재 보고 있는 방향, 왼쪽으로 움직였던 최대 위치, 오른쪽으로 움직였던 최대 위치입니다. (이를 이용하면 가능한 상태가 $\mathcal O (N^2L)$개밖에 없다는 것도 증명할 수 있습니다.)

왼쪽을 바라보고 있는 버섯을 앞쪽으로, 오른쪽을 바라보고 있는 버섯을 뒤쪽으로 떨어뜨리는게 목표이고, 앞쪽으로 움직였을 때 버섯이 떨어지는 순서는 고정되어있기 때문에, 특정한 위치까지 앞쪽으로 떨어뜨리고, 나머지를 뒤쪽으로 떨어뜨리는 것이 가능합니다. 이를 이용하면 $K=1$인 답이 항상 존재한다는 것을 증명할 수 있습니다.

이 버섯의 개수를 찾는 방법은 처음에 왼쪽을 보고 있던 버섯은 $+1$, 오른쪽을 보고 있던 버섯은 $-1$로 생각해서 떨어지는 순서로 누적합을 구해 누적합이 최대가 되는 시점을 구하면 됩니다. 특정 개수만큼 떨어뜨리고 방향을 바꾸고 싶을 때 버섯의 번호를 추적하는 것은 위의 관찰을 이용해서 떨어지는 방향을 시뮬레이션하면 됩니다.



solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - F - Editorial

먼저 길이 제한이 없다고 생각해 봅시다. '빼버려'에서 표현 가능한 집합은 어떤 형태일까요?

**주장 1**. '빼버려'는 원래 식에 등장하는 모든 집합에 들어 있지 않은 집합(`~A&~B&...&~T` 등)이 포함된 집합을 표현할 수 없다.

**증명**. '빼버려'의 모든 식이 원래 식에 등장하는 모든 집합의 합집합(`A|B|...|T` 등)의 부분집합임을 보이면 됩니다. 이 합집합을 $V$라 놓고 수학적 귀납법을 사용합니다.

- (Base Case) 등장한 모든 집합은 $S$는 집합 $V$의 부분집합입니다.
- (Inductive Case) 세 가지 종류의 연산이 있습니다.
  - `X|Y`: $X \subseteq V$이고 $Y \subseteq V$이면, $X \cup Y \subseteq V$입니다.
  - `X&Y`: $X \subseteq V$이면 $X \cap Y \subseteq V$입니다.
  - `X\Y`: $X \subseteq V$이면 $X \setminus Y \subseteq V$입니다.

$\square$

이제부터, "식에 등장하는 모든 집합의 합집합"을 $V$라 하고, "식에 등장하는 모든 집합에 들어 있지 않은 집합"을 $\mathcal{C}$라 하겠습니다. 특히 $V$와 $C$는 전체집합의 partition($V \cap C = \emptyset$, $V \cup C$는 전체집합)입니다.

**주장 2**. 임의의 집합 $X$에 대해, $\mathcal{C} \not\subseteq X$라면 $X$는 '빼버려'로 표현할 수 있다.

**증명**. '아니야'에서 식에 등장하는 모든 집합에 `~`을 달거나 달지 않은 뒤 모두 교집합한 집합을 **기초 집합**이라 하겠습니다. 예를 들어, `A`부터 `C`까지로 이루어진 식이 있다면 이 식에 대한 기초 집합은 `A&B&C`, `A&B&~C`, `~A&B&~C` 등으로 총 $2^{3} = 8$개 있습니다. 특히 $\mathcal{C}$는 기초 집합입니다. 아래 두 가지를 보입니다.

- 이 식은 $\mathcal{C}$를 제외한 기초 집합의 합집합으로 표현할 수 있다.
  - 기초 집합의 임의의 원소가 이 집합에 모두 속하거나 모두 속하지 않음(어떤 것은 속하고 어떤 것은 속하지 않는 경우가 없음)을 고려하면 쉽게 증명할 수 있습니다.
  - $\mathcal{C}$는 $X$를 표현함에 있어 합집합의 원소로 들어갈 수 없는데, 이는 $\mathcal{C} \not\subseteq X$이기 때문입니다.
- $\mathcal{C}$를 제외한 기초 집합은 동등한 '빼버려'의 식으로 표현할 수 있다.
  - 이 기초 집합은 $\mathcal{C}$가 아니므로, 그 표현에 반드시 하나는 `~`이 붙지 않은 집합이 존재합니다.
  - 이 `~`이 붙지 않은 집합들을 맨 앞으로 가져와 놓습니다.
  - 이제 첫 번째 집합이 아닌 집합 앞의 기호를, `~`이 붙었다면 `\`로 아니라면 `&`로 바꾸어 씁니다.
  - 예를 들어 `~A&B&~C&D`는 `B&D\A\C`로 쓸 수 있습니다.

이제 $X$를 $\mathcal{C}$를 제외한 기초 집합의 합집합으로 표현한 뒤, 각각의 기초 집합을 '빼버려'의 식으로 표현하고 (괄호를 두른 다음) 모두 `|`해 준 식이 $X$에 대응하는 '빼버려'의 식이 됩니다. $\square$

즉, '빼버려'에서 표현 가능한 식은 정확히 $\mathcal{C}$를 포함하지 않는 식들이고, 어떤 집합 $X$가 $\mathcal{C}$를 포함한다면 `~X`는 $\mathcal{C}$를 포함하지 않으므로 '빼버려'로 표현이 가능합니다. 이제 다음과 같은 식을 표현하는 언어를 '빼버려++'라 합시다!

```
Expression = OldExpr | "~" OldExpr
OldExpr = ('빼버려'의 Expression)
```

'빼버려++'는 '아니야'의 모든 식을 표현할 수 있습니다. 이제, '아니야'의 식을 '빼버려++'로 바꾸는 트랜스파일러를 생각합니다. 이는 귀납적으로 생성할 수 있습니다.

- (Base Case) 집합은 그대로 집합으로 표현하면 됩니다.
- (Inductive Case) 세 가지 경우가 있습니다.
  - `X&Y`: `X`를 표현한 식을 `E_X`, `Y`를 표현한 식을 `E_Y`라 합시다.
    - 만일 `E_X`와 `E_Y`가 모두 `OldExpr`이라면, `E_X&E_Y`가 '빼버려++'의 식이 됩니다.
    - 만일 `E_X`와 `E_Y` 중 하나가 `OldExpr`이고 다른 하나가 `"~" OldExpr`이라면 (일반성을 잃지 않고 `E_Y = "~" F_Y`라 하겠습니다), `E_X\F_Y`가 '빼버려++'의 식이 됩니다.
    - 만일 `E_X`와 `E_Y`가 모두 `"~" OldExpr`이어서 `E_X = "~" F_X`, `E_Y = "~" F_Y`라면, `~(F_X|F_Y)`가 '빼버려++'의 식이 됩니다.
  - `X|Y`: `X`를 표현한 식을 `E_X`, `Y`를 표현한 식을 `E_Y`라 합시다.
    - 만일 `E_X`와 `E_Y`가 모두 `OldExpr`이라면, `E_X|E_Y`가 '빼버려++'의 식이 됩니다.
    - 만일 `E_X`와 `E_Y` 중 하나가 `OldExpr`이고 다른 하나가 `"~" OldExpr`이라면 (일반성을 잃지 않고 `E_Y = "~" F_Y`라 하겠습니다), `~(F_Y\E_X)`가 '빼버려++'의 식이 됩니다.
    - 만일 `E_X`와 `E_Y`가 모두 `"~" OldExpr`이어서 `E_X = "~" F_X`, `E_Y = "~" F_Y`라면, `~(F_X&F_Y)`가 '빼버려++'의 식이 됩니다.
  - `"~" X`: `X`를 표현한 식을 `E_X`라 하겠습니다.
    - 만일 `E_X`가 `OldExpr`이라면, `~(E_X)`가 '빼버려++'의 식이 됩니다.
    - 만일 `E_X`가 `"~" OldExpr`이어서 `E_X = "~" F_X`라면, `F_X`가 '빼버려++'의 식이 됩니다.

Inductive Case를 표로 정리하면 다음과 같습니다.

<table>
  <thead>
    <tr>
      <th rowspan=2></th>
      <th colspan=2><code>E_X</code>가 <code>OldExpr</code></th>
      <th colspan=2><code>E_X</code>가 <code>"~" OldExpr</code><br />(<code>E_X = "~" F_X</code>)</th>
    </tr>
    <tr>
      <th><code>E_Y</code>가 <code>OldExpr</code></th>
      <th><code>E_Y</code>가 <code>"~" OldExpr</code><br />(<code>E_Y = "~" F_Y</code>)</th>
      <th><code>E_Y</code>가 <code>OldExpr</code></th>
      <th><code>E_Y</code>가 <code>"~" OldExpr</code><br />(<code>E_Y = "~" F_Y</code>)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td><b><code>X&Y</code></b></td>
      <td align="center"><code>E_X&E_Y</code></td>
      <td align="center"><code>E_X\F_Y</code></td>
      <td align="center"><code>E_Y\F_X</code></td>
      <td align="center"><code>~(F_X|F_Y)</code></td>
    </tr>
    <tr>
      <td><b><code>X|Y</code></b></td>
      <td align="center"><code>E_X|E_Y</code></td>
      <td align="center"><code>~(F_Y\E_X)</code></td>
      <td align="center"><code>~(F_X\E_Y)</code></td>
      <td align="center"><code>~(F_X&F_Y)</code></td>
    </tr>
    <tr>
      <td><b><code>X&Y</code></b></td>
      <td align="center" colspan=2><code>~E_X</code></td>
      <td align="center" colspan=2><code>F_X</code></td>
    </tr>
  </tbody>
</table>

이 풀이에서 몇 가지를 관찰할 수 있습니다.
- 우선, 최종 변환된 식이 `"~" OldExpr` 꼴이면 이 식은 $\mathcal{C}$를 포함하므로 '빼버려'로 표현하는 것이 불가능합니다. 이외의 경우는 이미 '빼버려'의 식입니다.
- 이 방식은, 원래 식에 있던 `~`를 제외한 연산자의 개수를 $k$라 했을 때, `~`을 제외하고 $k$개의 연산자를 사용합니다.
  - 모든 Case에서 `~`를 제외한 연산자의 개수가 유지되기 때문입니다.
- 원래 식의 길이를 $n$이라 하면, 이 방식으로 변환된 식의 길이는 언제나 $2n$을 넘지 않습니다.
  - $k$개의 `~`가 아닌 연산자가 있다는 것은 $(k+1)$개의 집합 문자가 있다는 것이므로, $k + (k+1) = 2k + 1\leq n$입니다.
  - 식이 `"~" OldExpr` 꼴이 아니면 식에 `~`가 없으므로, 연산자를 $k$개 사용한 것과 같습니다.
  - 모든 연산자마다 괄호로 하나씩 감싸 표현해도, 각 연산자 당 $3$개의 문자를 사용하게 됩니다.
  - 이 경우 식의 길이는 $(k + 1) + 3k = 4k + 1 < 4k + 2 \leq 2n$입니다.

따라서, 최종 변환된 식이 `"~" OldExpr` 꼴이면 `NO`를 출력하고, `OldExpr` 꼴이면 `YES`를 출력한 뒤 모든 부분 식에 괄호를 쳐서 출력하면 됩니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 1) - G - Editorial

먼저 DFS를 수행하여 전체 폴더를 순서대로 나열합니다. 그러면 어떤 폴더가 포함하는 폴더들은 연속한 구간으로 나타낼 수 있습니다 (Euler Tour Technique).

접혀 있는 폴더마다 대응되는 구간을 색칠해 봅시다. 그러면 한 번도 색칠되지 않은 원소들이 목록에 보이는 폴더가 됩니다. 이와 같은 정보를 관리하면서, 아래의 연산들을 빠르게 수행하는 자료구조가 필요합니다.

- 폴더를 접거나 펼칠 때마다, 구간을 추가하거나 삭제하기
- 현재 커서의 위치를 $x$라고 하면, 목록에 보이는 폴더 중 $x$번째 폴더 찾기

이를 위해 두 개의 값 $\mathrm{cnt}, \mathrm{vis}$를 저장하는 세그먼트 트리를 관리합니다. 편의상 세그먼트 트리의 노드는 $n$, 두 자식 노드는 각각 $2n$과 $2n+1$로 표기하겠습니다.

$\mathrm{cnt}[n]$은 현재 노드가 몇 번 색칠되었는지를 저장합니다. 구간을 추가할 때, 구간에 대응되는 세그먼트 트리 노드들의 $\mathrm{cnt}[n]$ 값을 $1$ 증가시킵니다. 삭제할 때는 다시 $1$ 감소시킵니다.

$\mathrm{vis}[n]$은 세그먼트 트리에서 $n$을 루트로 하는 서브트리만 봤을 때, 색칠되지 않은 원소가 몇 개인지 저장합니다. $\mathrm{cnt}[n] \geq 1$이면 $\mathrm{vis}[n] = 0$으로, $\mathrm{cnt}[n] = 0$이면 $\mathrm{vis}[n] = \mathrm{vis}[2n] + \mathrm{vis}[2n+1]$으로 설정합니다.

$x$번째 폴더를 찾을 때에는 $x$와 왼쪽 서브트리의 $\mathrm{vis}$ 값을 비교합니다. $x$가 작거나 같다면 왼쪽 서브트리를, 크다면 $x$에서 $\mathrm{vis}[2n]$을 뺀 뒤 오른쪽 서브트리를 재귀적으로 탐색합니다.

이제 쿼리를 처리할 준비가 되었습니다. 현재 커서가 몇 번째 폴더를 가리키는지를 나타내는 $x$와 각 폴더의 펼침 여부를 관리합시다.

- `toggle`: 세그먼트 트리에서 $x$번째 폴더의 번호를 구한 뒤, 폴더의 펼침 여부를 변경하고 구간을 추가하거나 삭제합니다. 시간복잡도는 $\mathcal O(\log N)$입니다.
- `move` $k$: $x$에 $k$를 더한 뒤, $[1, \mathrm{vis}[1]]$ 범위를 벗어난 경우 범위 내 값으로 다시 설정합니다. 시간복잡도는 $\mathcal O(1)$입니다.

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