[BZOJ 3196]二逼平衡树 线段树+splay

 

1+

Finger search

据说按中序遍历启发式合并平衡树是$O(n \log n)$的(不然就要两个log)

有待验证


1+

【模板】动态树 Link-cut-Tree

身心愉悦…


 

2+

树状数组求逆序对【模板】

存板子

0

ST表【模板】

\(st_{i,j}\)表示以\(i\)开头\(i+2^j\)结尾的区间的最值。

初态:\(st_{i,0} = a_i\)
状态转移: \(st_{i,j} = \min/\max (st_{i,j-1}, st_{i+ 2 ^ {j-1},j-1})\)


 

0

线段树模板【CodeVS 1082】

考前就不学新的东西了,板子敲一遍吧


 

0

1030总结

T1

这一题太水了,然而还是写错了 TwT 以后要认真读题

T2

答案是

\[ \frac { \left[ \sum _ { i = 1 } ^ {  { k } } \sum _ { j = 1 } ^ {  { k } } \operatorname { dis } \left( d _ { i } , d _ { j } \right) \right] \times ( k – 1 ) ! } { k ! }\]

然后\( O(n)\)树形dp即可

T3

考虑从每个点向外出发,状压一个\(S\)表示\(4P+1 \sim 4P+3\)步走到的点。
然后bfs即可。
检验某个点是否被覆盖\(k\)次,如果是则符合题意。
\(O(k(n+m))\),实际上还要带个常数\(16\)

0