911D : Inversion Counting

Codeforces 911D Inversion Counting

숫자로 이루어진 집합에서 그 집합에서의 특정 두 원소 ai, aj의 위치가 i > j 일떄 ai<aj 인 경우 inversion 이라고 한다.

iinversion의 문제를 푼적은 BoJ에서 푼 경험이 있는데 그 때는 merge sort를 응용해서 풀었다.

merge sort로 응용하는것은 geeks for geeks inversion counting이라고 검색하면 구할 수 있다.

대개 작은 배열의 크기 (100,000만 크기이하) 는 충분히 brute force 방식으로 일일히 inversion을 체크해주면된다.

그런데 codeforces 에서 더 큰일날 문제를 만났으니, 그건 911D의 inversion counting 이였다.

문제를 보자 대략 정신이 멍해졌다. 왜냐하면 배열의 크기가 최대 1500이니, n^n 이여도 2백25만, 할만하네 라고 생각했는데, 반전인게 쿼리를 날리는 횟수가 2*10^5다 ㅋㅋㅋㅋㅋ

쿼리를 [l, r] 형식으로 날리면 l r 구간의 배열을 뒤집고 난 뒤에 다시 전체의 inversion이 odd인지 even인지 체크해야한다.

 

타임리밋은 2초인데, 그걸 쿼리를 최악의 경우로 2*10^5 회를 한다고 해보면 언제 배열값복사하고 n^n으로 inversion counting을 해야하나?ㅋㅋㅋ 시간내에 불가능이다.

처음엔 dp를 생각해보기도했다. 당시에는 어떻게 생각해도 부분문제로 떨어지질 않았다.

푸는 방법은 그래프의 개념( 걍 n vertex가 존재할때 edge의 수 세는 법) 이 필요했다

크기가 4인 배열이있다고하자. (4, 1, 3, 2)  

이때 inversion 은 다음과같다. (4,1), (4, 3), (4,2) (3, 2)

그렇다면 다음과 같은 행렬로 그릴수있다.

이때 쿼리 [2, 4] 을 날려서 (4, 2, 3, 1) 로 만들어보자

그렇다면 inversion은 (4, 2) (4,3) (4, 1), (2,1), (3,1) 로 다섯개가된다. 

이경우 그래프는 다음과같다.

다시 쿼리를 [2, 3]을 날려서 (4, 3, 2, 1)로 만들어보자

그렇다면 inversion은 총 6개가 된다. (모두)

이 경우 그래프는 다음과같다.

보면 inversion 관계가 전체 배열에서 몇 개가 있건간에 query는 항상 query에서 날리는 구간의 inversion 관계를 xor해준다.

처음의 두 그림을 보면 [2, 4] 구간 사이의 (1, 2, 3)의 서로 관계가 행렬에서 xor된것을 볼수있다.

두번째와 세번째 그림을 보면 쿼리 [2, 3]에서 [2, 3]구간 사이의 (3, 2)의 서로 관계가 행렬에서 xor 된것을 볼수있다. 

자 그럼 문제는 다풀렸다. 

우선 첫 입력 에서 삼각행렬을 완성한다.

그 뒤 쿼리가 들어오면 배열을 쿼리에 맞게 뒤집는다.

그리고 쿼리 구간에 포함되어있는 숫자들을 파악한다.

그리고 관계-삼각행렬에서 해당 숫자들의 관계들(row, col)만 xor 시킨다.

삼각행렬에서의 총합(1의 개수 == inversion 개수)이 짝수인가? 홀수인가? 체크한다.

근데 잠깐 ㅋ

쿼리가 10^5... 10만개인데, 배열을 뒤집는게 복잡도 O(n)이다. 그렇다면 최악의 경우1천5백 * 10만 이니까. 으아.. 일단 이것만해도 복잡도 1억5천...

거기다 쿼리구간 포함되어있는 숫자파악에다가 관계삼각행렬에 xor ...크 ... 구현도 만만치않다.

난 좀 구현했는데 시간초과나는 아찔한 상황이 연출될거 같아서. 이내 생각을 포기하고싶었다. ㅋ

하지만 이렇게 구현하면 시간초과가 날지 안날지는 잘 모르겠지만, 아마 날거같다.

나는 다른이들의 솔루션을 보았기 때문에 좀더 나이스한 접근법을 알게되었다.

우선 첫 입력에서 inversion을 카운팅한다. 

그리고 쿼리가 들어온 구간의 길이 (포함된 숫자의 개수)의 관계수 n*(n-1)/2 만큼 더해준다.

이게 짝수면 답이 짝수고, 홀수면 답이 홀수다.

왜 그럴까?

다시 삼각행렬로 돌아가보면, 알 수 있다.

여기서 쿼리 [2, 4]를 날리려고하자. 그러면 구간 [2, 4]의 숫자를 알고 그것을 xor 해야한다.

그런데 일단 2, 4 구간의 숫자는 3갠데 그것의 관계수는 3개이다. (vertex 3개서 선을 그을수 있는수)

그런데 위 삼각행렬에서 어떤 요소든 3개를 xor 시켜도 항상 홀수이다. ㅋ

따라서 쿼리 구간의 관계 수와 기존 inverse 수를 계속 더해나가면서 홀짝인지만 검증해주면된다.

하나 배운것같다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/graph/911D.c