蓝了是啥啊

peterwuyihong @ 2021-08-30 18:01:08

by cyffff @ 2021-08-30 18:43:38

这题就是蓝的难度吧

by cyffff @ 2021-08-30 18:44:20

@一只大龙猫 实际上这并不玄学，复杂度要证明的。

by 一只大龙猫 @ 2021-08-30 18:50:36

@cyffff 已经有证明了啊

只不过说相当于比较“正经”的笛卡尔树或分块来说，暴力的方法比较“玄学”而已

by 年年有年 @ 2021-08-30 18:52:02

咍咍 笛卡尔树很正经。

by cyffff @ 2021-08-30 18:52:37

by 一只大龙猫 @ 2021-08-30 18:53:05

@int64 不是……我申请降蓝前一次看那个帖子还只有三页（当时zyx了）

by 一只大龙猫 @ 2021-08-30 18:53:45

@年年有年 啊……不是吗……

我学术不精，请您指教

by 年年有年 @ 2021-08-30 18:55:34

题解里面的笛卡尔树没有一个严格线性的。。说实话 tarjan 做到线性甚至比 O(n)-O(1) rmq 更复杂。

by 年年有年 @ 2021-08-30 18:56:29

或者说期望线性，可惜笛卡尔树也不是。

by Spasmodic @ 2021-08-30 19:09:06

@cyffff 什么玩意 你学的什么笛卡尔树