25339번 - 반전 수와 쿼리

1부터 $N$까지의 수가 한 번씩 등장하는 수열 $P = \lbrace 1, 2, \cdots, N \rbrace$이 주어진다.

수열 $P$에 대해, $i < j$ 이면서 $P_i > P_j$를 만족하는 순서쌍 $(i, j)$의 개수를 $P$의 반전 수라고 정의하자.

이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 $l$ $r$ : $P_l$와 $P_r$를 교환한다.
• 2 $l$ $r$ : $P_l$에서 $P_r$ 사이의 수를 뒤집는다. 뒤집은 뒤의 수열은 다음과 같다.
  • $\lbrace P_1, \cdots, P_{l-1}, P_r, P_{r-1}, \cdots, P_{l+1}, P_l, P_{r+1}, \cdots, P_N \rbrace$

각각의 쿼리를 처리한 다음 수열의 반전 수를 2로 나눈 나머지를 출력한다.

첫째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^9$, $1 \leq Q \leq 10^5$)

둘째 줄부터 $Q$개의 줄에 쿼리의 정보 $a, l, r$이 공백으로 구분되어 주어진다. ($1\leq a \leq 2$, $1 \leq l < r \leq N$)

각 쿼리를 처리한 다음 수열의 반전 수를 2로 나눈 나머지를 한 줄에 하나씩 출력한다.

• Python 사용자는 PyPy로 제출하는 것을 권장한다.