HDU 5306. Gorgeous Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=5306

세 종류의 쿼리를 지원하는 자료구조를 설계하는 문제이다. O((N + Q)lgN)에 해야 한다.

 * 1. 구간 [L, R]에 a[i] = min(a[i], V) 대입

 * 2. 구간 최댓값

 * 3. 구간 합

보통 이러한 문제들은 세그먼트 트리에 익숙하면 쉽게 풀 수 있고, 실제로 2번 쿼리까지는 쉬운 문제지만, 이 문제는 3번 쿼리 때문에 굉장히 어려운 문제가 되었다.

해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다.

먼저 이 값들을 제대로 관리했다면, 질의에 대해서 응답하는 것은 자명하다. 문제는 값 갱신 상황인데, 일단 노드 자체는 O(lgN)개를 보게 될 것이니, 각각의 노드에 대해서 다음과 같은 요령으로 값을 갱신하자 :

 * 만약에 V >= 최댓값이면, 갱신할 필요가 없다.

 * 만약에 최댓값 > V > 두번째 최댓값이면, 갱신을 한다. (lazy propagation의 요령으로 자식까지 갱신시켜줄 수 있다.)

 * 만약에 두번째 최댓값 >= V이면, 해당 노드를 갱신하지 않고, 그냥 아래 자식을 재귀적으로 본다.

코드 : https://gist.github.com/koosaga/7094b03194bb22c79706cfa33293626a

자식의 값을 토대로 루트의 값을 가져올 수 있으니, 이 알고리즘이 맞는 답을 출력함은 자명하다. 그렇다면, 시간 복잡도는 어떻게 될까? 그냥 생각하면 두번째 최댓값이 V 이상일 때 모든 노드를 갱신하니 O(QN) 이지만, 실제로는 O((N+Q)lgN)에 작동한다고 한다.

증명은... http://blog.csdn.net/oilover/article/details/47073621 참고. 저 풀이를 이해했다면, 이제 tag = maximum 이라고 대응시켜놓고 생각해보자. 두 풀이가 동치인것을 알 수 있다.