# [Gold III] 반전 수와 쿼리 [문제 링크](https://www.acmicpc.net/problem/25339) ## 문제 설명 <p>1부터 $N$까지의 수가 한 번씩 등장하는 수열 $P = \lbrace 1, 2, \cdots, N \rbrace$이 주어진다.</p> <p>수열 $P$에 대해, $i < j$ 이면서 $P_i > P_j$를 만족하는 순서쌍 $(i, j)$의 개수를 $P$의 <strong>반전 수</strong>라고 정의하자.</p> <p>이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.</p> <ul> <li>1 $l$ $r$ : $P_l$와 $P_r$를 교환한다.</li> <li>2 $l$ $r$ : $P_l$에서 $P_r$ 사이의 수를 뒤집는다. 뒤집은 뒤의 수열은 다음과 같다. <ul> <li>$\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$</li> </ul> </li> </ul> <p>각각의 쿼리를 처리한 다음 수열의 반전 수를 2로 나눈 나머지를 출력한다.</p> ## 입력 <p>첫째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^9$, $1 \leq Q \leq 10^5$)</p> <p>둘째 줄부터 $Q$개의 줄에 쿼리의 정보 $a, l, r$이 공백으로 구분되어 주어진다. ($1\leq a \leq 2$, $1 \leq l < r \leq N$)</p> ## 출력 <p>각 쿼리를 처리한 다음 수열의 반전 수를 2로 나눈 나머지를 한 줄에 하나씩 출력한다.</p> ## 풀이 - $j<i$인 i와 j에 대해 1번 연산을 하면 $P_j$와 $P_i$ 사이 원소들에 대해서만 반전 수가 변한다. $P_j$와 사이 원소들의 반전 수가 $x_1$이라 할 때, $P_j$가 $P_i$ 위치로 가면 반전 수가 $i-j-1-x_1$으로 변한다. 비슷하게 $P_i$가 $P_j$ 위치로 가면 반전 수가 $i-j-1-x_2$으로 변한다. 이때 추가로 $x_1$과 $x_2$가 달라 반전 수가 1 증가하거나 감소한다. 따라서 연산 1의 반전 수 변화량은 $2(i-j-1-x_1-x_2)±1$로 항상 결과값이 변한다. - 2번 연산은 1번 연산을 반복적으로 수행한 것과 같다. 1번 연산을 총 $(i-j+1)/2$번 수행한 것과 같기에 연산 횟수가 짝수 번이면 그대로이고 홀수 번이면 변한다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int ret=0; while(q--) { int a, l, r; cin >> a >> l >> r; if(a==1) ret ^= 1; else ret ^= (r-l+1)/2%2; cout << ret << '\n'; } } ```