By Standing On The Shoulders Of Giants

요약

before < now 면서 A[before] > A[now]인

(before,now)의 쌍의 개수를 구한다.

현재 now 일 때(고정) 이전에 사용했던 before들 중에서(탐색)

A[now]보다 큰 A[before] 의 개수를 세는 것이다.

세그먼트트리 구성

- 세그먼트트리 : A가 가진 값들의 사용횟수를 저장

- 쿼리 : N > A[i] > A[j] 을 만족하는 A[i]의 개수

- 쿼리구간 : [A[j]+1, N]

개념

역으로 된 쌍을 세는 문제유형

무엇이 역으로 되어있을까?

i < j 면서 A[i] > A[j] 인 ---inversion

(i,j) 의 쌍의 개수를 구한다. ---counting

5,1,3,1,2 라는 수열이 주어졌을 때 inversion 된 쌍의 수는

(5,1)  = 1 < 2 면서 A[1]>A[2]( = 5>1)

(5,3)  = 1 < 3 면서 A[1]>A[3]( = 5>3)

(5,1)  = 1 < 4 면서 A[1]>A[4]( = 5>1)

(5,2)  = 1 < 5 면서 A[1]>A[5]( = 5>2)

(3,1)  = 3 < 4 면서 A[3]>A[4]( = 3>1)

(3,2)  = 3 < 5 면서 A[3]>A[5]( = 3>2)

이다.

즉 내림차순과 같이 순서는 뒤면서 값은 앞에 나온 수보다 작은 경우인 것이다.

i < j 면서 A[i] > A[j]인

(i,j) 의 쌍의 개수를 구한다.

를 좀 더 뜯어먹기 좋은 표현으로 바꾸면

before < now 면서 A[before] > A[now]인

(before,now)의 쌍의 개수를 구한다.

즉,

현재 now 일 때(고정) 이전에 사용했던 before들 중에서(탐색)

A[now]보다 큰 A[before] 의 개수를 세는 것이다.

구현

그러면 어떻게 i<j 면서 A[i]>A[j]인 i의 개수를 찾을 수 있을까?

시간복잡도를 계산해보자

1~N까지의 j를 기준으로 할 때 조건에 맞는 i를 찾아 쌍을 만드는 것이므로

j의 N회 순회는 반드시 필요하다.

1. $O(N \times ???)$ 

1. $O(N\times N)$ 

* [ 는 이상, ) 는 이하를 의미

$N$ : j의 순회[0, N)

$N$ : i의 순회[0, j) 완전탐색

int A[Max];
int cnt = 0;
for (int j = 0; j < N; j++)
	for (int i = 0; i < j; i++)
		if (A[i] > A[j])
			cnt++;

2. $O(N\times logN)$ 

$N$ : j 의 순회[0, N)

$logN$ : i의 순회[0, j) 세그먼트트리

int A[Max];
int cnt = 0;
for (int j = 0; j < N; j++)
	query(A[j] + 1, N);

구현_세그먼트트리

2. $O(N\times logN)$ 

$N$ : j 의 순회[0, N)

$logN$ : i의 순회[0, j) 세그먼트트리

세그먼트트리를 이용하기 위해서는

i < j

A[i] > A[j]

를 다시봐야한다.

i의 범위 : [0,j)

그래서 세그먼트트리를 구성할 때

당연히 세그먼트트리 idx = 저장된 데이터의 idx = 입력순서

로 생각할 수 있는데 세그먼트트리의 idx가 저장순서로 사용되면 의미가 없다.

요약 : 세그먼트트리 구성

- 세그먼트트리 : A가 가진 값들의 사용횟수를 저장

- 쿼리 : N > A[i] > A[j] 을 만족하는 A[i]의 개수

- 쿼리구간 : [A[j],N]

세그먼트트리로 구해야할 사항은

[0,j) 에서 A[i] >A[j]인 i의 개수

가 된다.

이때

i<j 는 [0,j) 의 범위지정으로 자연스레 조건만족이된다.

A[i] > A[j] 는 어떻게하면될까? 

자연스레 세그먼트트리의 idx를 A[i]와 A[j]의 값으로 쓸 수 있게 하는 것이다.

즉,

세그먼트트리

현재 j일 때

idx : A 값

segTree[idx] : j가 훝어온 A[j]값의 사용횟수

로 구성하는 것이다.

이 때 query의 범위는 [j+1,N) 가 되어

A[i](=이전의 j의 A[j] 값) 값이

현재 j의 A[j]값보다 큰게 몇개가 있는지 logN으로 합을 구하는 것이다.

다음과 같이 같은 값이라도 A[2]=1,A[4]=1이 구분되듯 다르게 센다.

예제

www.acmicpc.net/problem/5419-세그먼트트리(inversion counting)+좌표압축+스위핑