[SPOJ QTREE] Link Cut Tree引发的血案

最近在整理5月份和老毛子5V5的模板,发觉自己以前的LCT简直是圡得无法直视……
于是把wjmzbmr大大的模板down下来观摩了一番,写了个QTREE。原以为很快搞定的,没想到TLE到死。
上网找了一些LCT的代码交上去,发现都挺慢的……于是继续改,陆陆续续地加了点常数优化全都不顶事。最后不知道哪根筋抽了居然会想起在每个函数前加一个inline,然后它就过了……
原来根本原因是坑爹的SPOJ没有开O2 = =b
好在在搜集代码的过程中学习了好多新姿势,于是我的Splay模板又可以继续改进了。算是忙乎一晚上的一点成果吧。

Qtree
[传送门]
[Code]

感觉这个写法还是挺舒服的,于是以后就用这好了。
有空把剩下的QTREE再刷刷完吧~扎实点总没错的

[email protected] 17:00

Qtree2
[传送门]
[Code]

感觉这个LCT写得姿势更好了……

Qtree3
[传送门]
[Code]

……和Qtree2没啥区别,改改就过了。注意一下范围大了10倍就好。

留下评论

您的电子邮箱地址不会被公开。