[BOJ] 16136번: 준하의 정수론 과제 (Divmaster)

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

f(A) = A의 약수의 갯수라고 할 때, f(A)는 2*sqrt(A) 이하이므로 대충 5-6번 정도만 연산을 하고 나면 2가 될 것입니다. (물론 A가 1이면 f(A)는 1이고요.) 그러니 1번째 작업의 경우는 각 수에 대해서 대충 5번 정도만 이루어지고 나면 더 이상 할 필요가 없는 작업이 됩니다. 저는 segment tree 2개를 두어, 첫 번째 segment tree는 일반적인 구간 합을 처리하는 segment tree이고 두 번째 segment tree는 특정 수가 2 이하인지를 확인하는 segment tree로 두어 1번 쿼리가 들어왔을 때 현재 확인한 node의 st부터 en까지가 전부 2 이하일 경우 더이상 따라들어가지 않고 return, 또 현재 확인한 node의 st부터 en까지가 전부 2 초과일 경우 연산을 진행하는 방식으로 처리했습니다.

다른 사람의 코드를 보니 구간 합을 처리하는 segment tree 1개에 union find로 해결을 한 경우도 있었습니다.

https://github.com/blisstoner/BOJ/blob/master/16136.cpp