백준 13887 ( 루비 도전기 < Day - 1 > )

처음에 이 문제를 봤을 때는 1번이 굉장히 어려워보였다.

 

아니 삽입, 삭제 + O(n^3) 연산??

 

 

 

그러나, <삽입, 삭제, 갱신> 연산은 스플레이 트리로 처리할 수 있다.

 

그리고 그 스플레이 트리의 노드들에 대해서 다차원 세그먼트 트리를 처리해주면 1번쿼리를 처리할 수 있다.

 

 

 

그러면 어떻게 세그먼트 트리로 1번 쿼리를 처리하는가??

 

 

이는 두 노드들의 집합 A, B에 대해 1번 쿼리에 대한 답을 merge하는 알고리즘을 만들면 된다!

 

 

A = { A1, A2, A3, A4 ... An }

B = { B1, B2, B3, B4 ... Bm }

일때,

 

1번 쿼리는 A+B 집합에 대해서 (n+m)C3 번째 수들의 곱으로 생각할 수 있다.

 

그러나, 이는 분명히 A 집합에 대해 nC3번째 수들의 곱, B집합에 대해 nC3번째 수들의 곱을 포함하고 있다.

 

 

그리고 (A집합 nC2번째 수들의 곱) * (B집합의 아무 숫자)

(B집합 nC2번째 수들의 곱) * (A집합의 아무 숫자)

를 더해주면 (n+m)C3번째 수들의 곱을 구할 수 있다.

 

 

(n+m)C2는 nC2 + mC2 + nC1 * mC1이고,

(n+m)C1은 nC1 + mC1이다.

 

이를 그저 세그먼트 트리에 적용시키면 된다.

 

구간합 문제였다면 tree[node] = tree[left child] + tree[right child] 로 트리를 초기화할 수 있지만,

 

이 문제에서는

tree[node].C3 = tree[left child].C3 + tree[right child].C3
+ (tree[left child].C2 * tree[right child].C1) + (tree[left child].C1 * tree[right child].C2)


tree[node].C2 = tree[left child].C2 + tree[right child].C2 + (tree[left child].C1 * tree[right child].C1)


tree[node].C1 = tree[left child].C1 + tree[right child].C1

 

으로 초기화할 수 있다. 즉, 트리의 노드 클래스는 이렇게 정의된다.

 

class tree{
public:
	int C3, C2, C1;
}

 

그리고 집합 A = {A1}인 리프노드에서는

tree[leaf node].C3 = 0
tree[leaf node].C2 = 0
tree[left node].C1 = A1

 

으로 초기화할 수 있다.

 

 

 

다음 시간에는 " 서로 다른 수의 개수 " 를 처리하는 방법에 대해서 탐구해보겠다.

 

스플레이 트리로 삽입, 삭제, 갱신 연산을 한 이상 <백준 13547 : 수열과 쿼리 5>처럼 간단하게 처리할 수는 없다.

 

그걸 어떻게 처리할 것인지에 대해 탐구해보겠다.