科普：链式前向星为何慢
由于链式前向星访问数组时候，下标不是连续的，是打乱的，导致访问内存时候用时比连续访问的长，所以很慢
//但是我写图论题用链式前向星存边从来没被卡过啊。。。
by ghj1222 @ 2019-01-10 18:43:37
vector大法好
by King_of_gamers @ 2019-01-10 18:47:14
@[ghj1222](/space/show?uid=13091) %%%您怕不是写的后缀树
by ywy_c_asm @ 2019-01-10 18:50:24
@[ywy_c_asm](/space/show?uid=125124) 就是普通的倍增法。。。只是把平常用的vector/桶换成了链式前向星。。。
by ghj1222 @ 2019-01-10 18:53:06
@[ywy_c_asm](/space/show?uid=125124) %%%颜神orzorzorz
by ghj1222 @ 2019-01-10 18:53:24
@[ghj1222](/space/show?uid=13091) ~~欢迎来~~[~~P4964~~](https://www.luogu.org/problemnew/show/P4964)~~体验前向星被卡~~
其实并不会被卡，实测2.7s...当时出题的时候想卡 $O(n\log n)$ 做法，结果发现不仅卡不掉（除非毒瘤开 $1.5$ 倍以内的时限），还会对前向星非常不友好，~~并且还让输入变得毒瘤~~..
by ouuan @ 2019-01-28 18:37:02
说不定这道题的初衷也是想区分 DC3 和倍增的效率，一不小心就考验缓存优化了..事实证明不要妄想卡一个 log，能卡一个 log 的数据范围内存不连续的常数就比一个 log 还大了
by ouuan @ 2019-01-28 18:39:05
@[ouuan](/space/show?uid=49742) 于是我学了正经的后缀数组。。。
~~[WC2017]挑战 体验被卡常支配的恐惧~~ <-不敢做这题
可能是我自带常数
当时出题的时候应该是卡$O(n\log^2 n)$，然而我写的$O(n\log^2 n)$真的T了，T的比链式前向星惨
链式前向星的常数应该没有一个log大吧，因为最后还是过了
by ghj1222 @ 2019-01-28 19:21:16
$O(nlog^2n)$不是能过的吗
by zj余能 @ 2019-02-06 21:14:23