[CF 911D] Inversion Counting

[CF 911D] Inversion Counting - 1700

문제 설명 : 

초기의 1~n으로 이루어진 permutation이 주어진다. 그리고 m개의 쿼리마다 [l,r]범위에 포함되는 인덱스를 reverse한다. 이 때 매 쿼리마다 어떤 임의의 인덱스 i,j에 대해서 i<j면서 a_i<a_j를 만족시키는 서로 다른 i,j의 pair가 짝수개인지 홀수개인지 구하는 문제이다. 매 쿼리는 이전 쿼리들에 의해 누적된 permutation에 대해서 시행한다.

풀이 : 

n=1500, 쿼리(m)는 20만이다. O(nm)은 3억이므로 잘 하면 풀 수도 있겠지만 정해는 아닐거라 생각해서 어떻게든 O(m*logn) 혹은 O(m*1)으로 푸는 방법이 있을 것이라고 생각했다. 오랜 시간을 투자해서 여러가지 방법을 계속 생각해봤는데, 매 쿼리는 종속적이다보니 짝수,홀수인지는 어떻게 구간 배열로 판명한다고 쳐도, update하는게 불가능해서 실패했다.

이 문제의 정답은 결론부터 애기하고 이후에 증명하는게 나을 것 같다. 결론은 매 쿼리의 구간의 크기(=r-l+1)을 seg라고 둔다면, seg*(seg-1)/2의 값이 짝수라면 이전 state와 동일하고, 홀수라면 이전 state와 반대의 결과가 나온다. 왜 그런지 살펴보자.

문제에서 매 쿼리[l,r]마다 reverse 연산을 수행하게 되는데 쿼리에 포함되지 않는 바깥쪽 영역들은 이전 permutation의 counting과 결과가 동일하다. 다시 말해 [1,r-1], [l+1,n]의 카운팅 결과는 이전 상태와 동일하다. 따라서 내가 고려해야 할 것은 오직 [l,r]의 카운팅 결과가 어떻게 되는지이다. 그런데 여기서 또 하나의 규칙을 발견할 수 있다. 구간의 크기를 seg라고 했을 때, (reverse 시행 전 [l,r]의 카운팅) + (reverse 시행 후 [l,r]카운팅) = seg*(seg-1)/2 가 반드시 성립한다는 것이다. 각 수를 그래프의 한 node라고 생각하고 counting조건을 부합한다는 것을 i->j로 가는 directed  edge를 그리는 것으로 생각해보면 reverse연산을 수행한다는 것은 그래프에서 모든 edge들을 뒤집는다는 뜻이다. 처음의 edge와 뒤집어진 edge의 합집합은 노드의 개수가 n개인 그래프에서 그을 수 있는 모든 edge의 경우의 수이므로 n*(n-1)/2 개 이다.

여기까지 증명을 완료했고 문제를 다시 정리해보면, 결국 내가 고려해야 할 것은 [l,r] 구간의 카운팅이 이전 permutation의 홀짝과 동일하느냐이다. 이를 판단하기 위한 단서가 바로 시행 전 카운팅과 시행 후 카운팅이 반드시 seg*(seg-1)/2인 것이다. 그럼 이제 이 공식을 어떻게 적용해야 할 것인가? 정답은 바로 seg*(seg-1)/2 (=편의상 L로 두자)가 짝수인지 홀수인지로 판별할 수 있다. L이 만약 짝수라면 현재 카운팅은 이전의 카운팅과 동일할 것이고, L이 홀수라면 현재 카운팅은 이전 카운팅과 반대일 것이다. 

식으로 적어보면 count_prev + count_cur = L(=짝수) 라면 count_prev == count_cur가 성립하고,

count_prev + count_cur = L(홀수) 라면 count_prev + count_cur =1 (서로 반대라는 뜻)이 성립한다.

 

주의할 점 : 

-

배운 점 : 

아이디어성 문제였다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
/*********************Contest Template***********************/
const int SIZE= 1509;
 
int arr[SIZE];
 
int main(){
    int n;  scanf("%d",&n);
 
    int cnt=0;
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
 
    for(int i=1 ; i<=n ; i++){
        for(int j=i+1 ; j<=n ; j++){
            if(arr[i]>arr[j]) cnt^=1;
        }
    }
 
    int m;  scanf("%d",&m);
 
    while(m--){
        int l,r;    scanf("%d %d",&l,&r);
        int seg=r-l+1;
 
        if((seg*(seg-1)/2)%2==1) cnt^=1;
        printf("%s\n",(cnt)?"odd":"even");
    }
    
    return 0;
}
/*

*/