关于Tarjan

P3793 由乃救爷爷

aipostan @ 2019-10-30 17:26:53

这题为什么Tarjan挂了？？？

明明时间复杂度是对的……为什么空间会炸??

(话说好像要800MB+才开的下)

而且在笛卡尔树上乱跳(划掉)的时间复杂度真的对吗？？？

是因为数据随机才没卡吧……不然分分钟卡成O(nq)

不然也应该是O(qlogn)的均摊复杂度吧……

by 142857cs @ 2019-10-30 17:27:48

qlogn过不去啊

by 长安何处在 @ 2019-10-30 17:29:36

orz

by aipostan @ 2019-10-30 19:09:17

@142857cs 过不去吗？2*10^7*log_2(2*10^7) 不是大概4亿的样子吗？大概1s多一点的样子

by aipostan @ 2019-10-30 19:10:48

而且ST表模板那题用Tarjan居然比在笛卡尔树上乱跳要慢……