13309번 - 트리
노드관계가 (예를들면 단순히 i+1 은 i의 자식노드 이렇게 ) 일직선인것에다가
질의 종류는 0,1 구분없이 맨 끗 점에서만 집어넣어도 뚤릴 소스코드가 있습니다(https://www.acmicpc.net/submit...)
LCA 가 O(N)이어서 복잡도가 O(QN)입니다
LCA lgN으로 구현한 것 같은데요
낚시에 걸려들었네요.. N이었네요
후훗 감사합니다
이게 a, b 각각은 lg로 올라가고, 같이는 n으로 올라가서 말씀하신 데이터는 O(QlgN) 이에요
https://www.acmicpc.net/rejudg...
댓글을 작성하려면 로그인해야 합니다.
leehosu01 5년 전
노드관계가 (예를들면 단순히 i+1 은 i의 자식노드 이렇게 ) 일직선인것에다가
질의 종류는 0,1 구분없이 맨 끗 점에서만 집어넣어도 뚤릴 소스코드가 있습니다(https://www.acmicpc.net/submit...)
LCA 가 O(N)이어서 복잡도가 O(QN)입니다