leehosu01   5년 전


노드관계가 (예를들면 단순히 i+1 은 i의 자식노드 이렇게 ) 일직선인것에다가

질의 종류는 0,1 구분없이 맨 끗 점에서만 집어넣어도 뚤릴 소스코드가 있습니다(https://www.acmicpc.net/submit...)

LCA 가 O(N)이어서 복잡도가 O(QN)입니다

startlink   5년 전

LCA lgN으로 구현한 것 같은데요

startlink   5년 전

낚시에 걸려들었네요.. N이었네요

leehosu01   5년 전

후훗 감사합니다

startlink   5년 전

이게 a, b 각각은 lg로 올라가고, 같이는 n으로 올라가서 말씀하신 데이터는 O(QlgN) 이에요

댓글을 작성하려면 로그인해야 합니다.