루트 야매

그냥 이번에 코드포스에 나와서.

버킷 등의 특별한 자료구조를 안 쓰고 O(Sqrt(N)) 의 시간복잡도를 보이는 테크닉을

아는것만... 서술하겠다.

1.

http://koistudy.net/?mid=prob_page&NO=1069

Naive하게 코딩했을때 O(QNlgN) 이 나온다. (사실 데이터 약해서 카운팅소트로 된대여... 비밀!)

이때 쿼리를 다음과 같이 정렬해보자. (query 구조체는 s,e 값을 가진다)

bool cmp(query x, query y){

return x.s/SQRT == y.s/ SQRT ? (x.e < y.e) : (x.s < y.s)

}

start / SQRT 값이 일정할 때 end 값은 단조증가할 것이기 때문에 end의 기준에서는 1 ~ N까지의 원소를 N * SQRT 번 훑게 된다.

한편, start의 기준에서는 1 ~ N까지의 원소를 한번 훑은 후 한 쿼리당 최대 SQRT만큼의 변화가 생길 것이다. 때문에 원소를 Q * SQRT번 훑게 된다.

이 때문에 전 쿼리에 계산했던 값을 이용해 이번 쿼리를 계산하는 식으로 하면 빨라진다.

Binary Indexed Tree를 사용해서 계산하면, 복잡도는 O((Q + N) * N^0.5 * lgN + QlgQ) 이다. Sqrt(N) 배 더 빨라졌다.

http://geniusainta.com/problems/view/JOI14_historical

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

얘도 재밌다!

2.

http://codeforces.com/problemset/problem/506/D

열심히 풀었는데 아쉽게 틀린 문제, 코딩 미스는 자고 일어나서 발견했다.

일단 얘를 그래프 문제가 아닌 자료 구조 문제로 뜯어고쳐야 한다. (사이클 있는 무향 그래프인데 union find 써도 쿼리당 O(M)이니..)

일단 관찰해야 할거는

1. 색깔이 같아도 다른 컴포넌트에 있으면 다른 색깔로 봐도 무방하다 예로 3번 색 엣지를 가진 그래프의 컴포넌트가 두개면 사실 3, 4 이렇게 색을 붙여줘도 상관없다는 것이다

2. 이렇게 색깔을 붙여줘도 색깔의 개수는 M 이하이다 당연.

때문에 각 컴포넌트를 M개의 색깔 집합으로 만들고, 적당한 자료구조에 때려박은 후 모든 색깔 집합을 다 돌면서 u,v가 같은 집합 안에 있을 때 cnt++ 해주면 된다.

그리고 또하나는

3. 색깔 집합의 원소 개수의 합은 O(M) 이다

저조건 때문에 루트 야매를 사용할 수 있다.

적당한 DFS를 통해서 다음과 같은 테이블을 만들자. O(M)에 하면 되는데 난 BST를 사용해서 O(MlgM) 에 했다.

vector<int> color[i] = i번 노드가 속한 색깔 집합의 번호들 ( 2번 4번 6번에 속했다면 color[i] = {2,4,6})

3번이 성립하기 때문에 Sum(color[i].size()) = O(M)이고, query(i,j)가 들어왔을때 Color(i)와 Color(j)의 교집합의 원소 수를 세면 된다.

이는 binary search를 통해 O(QMlgM)에 해결할 수 있다.

참고로, binary search를 할때 각 집합의 원소가 A, B개이고 A > B 라면, 꼭 AlgB가 아니라 BlgA로 binary search를 하도록 하자. 컷팅 면으로 보면 당연한데 사실 이건 뒤에서 매우 중요해진다.

그리고 핵심.

4. 위 O(QMlgM) 알고리즘은 중복 쿼리가 들어오지 않는다면 사실 O(QSqrt(Q)*lgM)에 작동한다.

Case를 나눠서 증명할 수 있다. 집합의 원소가 A,B 개고 A > B라 하자.

1. B <= Sqrt(Q) 이다.

계산 시간이 BlgA <= Sqrt(Q)lgM이므로 당연하다.

2. B > Sqrt(Q)이다.

일단 B > Sqrt(Q) 인 쌍의 개수는 Sqrt(Q) * Sqrt(Q) = Q개 존재할 수 있다. 또한 B의 경우의 수도 Sqrt(Q)개 이하이다.

모든 Sqrt(Q) * Sqrt(Q) 개의 쌍에 대해서 계산 시간을 총 더해보자면

Sum(B,A)(O(BlgA)) <= Sum(B,A)(O(BlgM)) 이고,

Sum(B,A)(O(BlgM)) <= Sum(B)(O(BlgM * Sqrt(Q)) 이고 (A의 개수가 Sqrt(Q)개 미만이니)

Sum(B) (O(B)) * O(Sqrt(Q) *lgM) <= O(Q * Sqrt(Q) * lgM) 이다. (B의 경우의 수를 모두 더하면 전체 집합의 개수보다 작다)

설명이 거지인데 직접 해보면 알것이다.

이로써 이 알고리즘은 O(Q^1.5 lgM)에 작동한다.

하지만, 사실 중복 쿼리가 안들어온다는 보장을 해준 사람이 없기 때문에 B > Sqrt(Q)인 모든 Q개의 케이스를 dp table을 만들어서 중복 쿼리를 처리해줘야 한다.

이리 하면 문제를 풀 수 있다.