_Gion

Splay是一种能快速分裂与合并的平衡树，常用于解决某些序列问题. rotate : 单旋 先理解一下右旋，左旋与右旋是完全对称的操作. 如图，右旋的作用就是一个结点是左儿子，它旋转到父亲的位置，并且可以发现旋转后依然满足二叉搜索树的性质 双旋 双旋就是一次往上旋两层，保证复杂度，而单旋不保证. 定义dir(x)dir(x)dir(x)表示xxx是左子树还是右子树。 如果dir(...

像线段树那样，维护一个懒标记就行 #include <algorithm> #include <cstdio> using namespace std; namespace Splay { const int N = 1e5 + 10; int root, ch[N][2], sz[N], fa[N]; int tag[N], mx[N], va[N]; bool...