백준 25339 / C++

https://www.acmicpc.net/problem/25339

25339번: 반전 수와 쿼리

 

쿼리마다 반전수의 홀짝성을 확인해주는 문제이다.

수학이 전부인 문제.

 

[ 풀이 ] 

// 1번 쿼리의 경우

Ai와 Aj를 교환한다고 하자. Ai와 Aj 사이의 수열에만 관심이 있다.

나머지 A1~Ai-1, Aj+1~An은 Ai와 Aj가 교환되도 반전수에 영향이 없다. 

Ai+1~Aj-1중 Ai와 반전쌍을 이루는 것의 개수를 x1이라 하면.. Ai와 반전쌍이 아닌건 (j-i-1)-x1개이다. 

따라서 Ai와 Aj를 교환하면, Ai와 반전쌍을 이루는게 바로 j-i-1-x1개이다. 

(이 논리는 모든 값이 다르기 때문에 가능함)

마찬가지로 Ai+1~Aj-1 중 Aj와 반전쌍을 이루는 것의 개수를 x2이라 하면, 

교환 후에 j-i-1-x2개가 된다. 마지막으로 Ai와 Aj 자체의 쌍은 부등호가 바뀌므로 무조건 1 차이가 난다. 

따라서 x1+x2 에서  2(j-i-1)-(x1+x2)+1 꼴로 변하므로 항상 홀짝성이 바뀐다.

 

// 2번 쿼리의 경우

Ai~Aj를 전부 Aj~Ai로 바꾸는 경우 이들간의 반전쌍만 세주면 된다. 

나머지 쌍들은 수열이 뒤집어져도 반전쌍에 영향이 없다. 

Ai~Aj 쌍의 수는 j-i+1C2 개이므로 Ai~Aj 반전쌍을 x개라 하면, 뒤집은 후 반전쌍은 (j-i+1)C2 - x개가 된다.

따라서 (j-i+1)(j-i)/2 의 홀짝성만 따져주면 된다.

 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int n, q, a, l, r, ans = 0;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    while (q--) {
        cin >> a >> l >> r;
        // 1번 쿼리 항상 홀짝성 바뀜
        if (a == 1) ans ^= 1; 
 
        // 2번 쿼리: (r-l+1)(r-l)/2 의 홀짝성 따지기 
        else {
            int mod = (r - l) % 4;
            if (mod == 1 || mod == 2) ans ^= 1;
        }
        cout << ans << '\n';
    }
}