선행 : 모스 알고리즘 모스 알고리즘으로 해결 가능하다. [Li, Ri] 쿼리 구간에 대해 COUNT[x] = (A[j]==x) 인 j 의 갯수 위와 같은 정보를 저장하자. 그러면 모스 알고리즘이 돌아가면서 COUNT[x] 값이 갱신될 때, 정답도 같이 갱신해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465// code by RiKang, weeklyps.com#include#include#include#define PII pair#define PIII pair using namespace::std; const int N = ..
Table of Contents 개요 트리 펼치기 Mo's algorithm 의 적용 문제 1. 개요 https://www.acmicpc.net/problem/13518 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다. ( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 ) 2. 트리 펼치기 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다...