没事不要写LCT

没事不要写LCT

今天做了某题，大概需要维护个树链信息，题解区有以下几种做法

\(n=8e4\)，时限\(2s\)

1. 二分+树剖+树套树(线段树套平衡树)，\(O(n \log^4n)\)，题解卡了卡常过了
2. 二分+树剖+线段树，\(O(n \log^3n)\)，题解区稳过
3. 树上带修莫队 \(O(n ^{ 5/3})\)，题解区稳过
4. 树上分块\(O(n \sqrt n)\)，题解区稳过
5. 树套树(树状数组套主席树)，\(O(n \log^2n)\)，题解区稳过
6. 二分+树状数组，\(O(n\log^2n)\)，题解区稳过

题比较简单，能够一眼看出第二种解法，但是\(n \log^3n\) 算出来已经是\(3e8\)级别了，带着线段树的常数我觉得很不稳，于是我灵机一动，把树剖套线段树换成LCT理论复杂度就少了一个\(\log\)，我靠我这不稳过。
于是它

我******

吸了个氧才过。

于是我们得出结论LCT的常数比一只log还大

当然事实就是这样的，很少有题LCT跑得比树剖套线段树快，除了DDP之类的，所以没事少冲LCT，坚信树剖常数小

原文地址：http://www.cnblogs.com/Delov/p/16867440.html