티스토리 뷰
Link
Tag
- Segment Tree
- Spare Table
Time Complexity
- $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$
$f(x)=2x^2-1, g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나? 결론부터 말하자면 $f \cdot g = g \cdot f$다. 그래서 1,2번 쿼리가 어떤 순서로 들어왔는지는 중요하지 않고, 각각 $A_i$에 $f,g$가 각각 몇번 적용되었는지 알아내고 빠르게 계산할 수 있으면 된다.
$f,g$가 각각 몇번 적용되었는지는 range-update point-query 세그먼트 트리 두개면 된다. 실제 $A_i$를 빠르게 계산하는건 Sparse Table로 전처리하면 $O(lgQ)$에 가능하다.
Sparse Table 전처리에 $O(XlgX)$ $(X=100003)$, 1,2번 쿼리당 $O(lgN)$, 3번 쿼리당 $O(lgN+lgQ)$에 처리 가능하다. 대충 엔로그엔~~
Code
댓글