#替罪羊

平衡树简单教程及模板(splay, 替罪羊树, 非旋treap)

原文链接https://www.cnblogs.com/zhouzhendong/p/Balanced-Binary-Tree.html注意是简单教程,不是入门教程。假设点y原是点x的father,旋转操作可以在不改变中序遍历的基础上,将y变成x的儿子。例如: 旋转后:代码:intwson(intx){ret...

UOJ#55. 【WC2014】紫荆花之恋 点分树 替罪羊树 平衡树 splay Treap

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ55.html做法还是挺容易想到的。但是写的话……首先这种题如果只要求一棵树中的满足条件的点数(不需要在加点的同时维护答案),那么显然可以点分治:假设当前点分中心为x,设点y与x的距离为d[y],然后...