LCT
昨天调试一天没出来,今天推倒重写还是gg了,内心崩溃照着源代码抄,结果发现自己把原树fa和splay的fa一起维护,各种re。。。
其实我们手玩一下,发现其实树的形态变化很小,那么就可以用lct维护了,查询就是相当于查询点到root的点权和,点权为1
删除什么的手画一下就行了
然后我们要用一个数组维护一下原树形态,因为splay是二叉树,可以很方便地维护树的形态,但是一般的树比较麻烦,因为删除儿子什么的的确很烦。这些信息不能再lct上维护,因为lct上fa会变化,里面的fa是splay的fa,不是原树的fa,就破坏了原树形态,所以不能这样维护
然后就是lct各种操作。。。几个月没写都忘了。。。
#include<bits/stdc++.h> using namespace std; const int N = 100010, inf = 1000000010; namespace IO { const int Maxlen = N * 30; char buf[Maxlen], *C = buf; int Len; inline void read_in() { Len = fread(C, 1, Maxlen, stdin); buf[Len] = '