高度由习惯堆积

2019年3月

LCT的初步理解

用处LCT主要用于处理森林的问题,也就是处理点与点之间的断边和连边问题。它是以$Splay$为基础,均摊时间复杂度$O(nlogn)$的数据结构。它可以实现如下功能:连边断边换根路径修改路径查询它的实质是若干棵$Splay$,每棵$Splay$维护的是树上的某一条边($Splay$的中序遍历即为此路径从浅到深)实现有几篇好文章可供参考:PaulliantLCT总结——概念篇QTREE解法的一...
March 26, 2019

HDU1890 Robotic Sort

题目题目大意是让你找在一个区间内找一个最小权值的点,让它通过旋转的方式换到最前面。思路注意Splay的性质:中序遍历不变。所以这里就可以把Splay看作一个超级数组,而不是通常定义的二叉查找树(左边的子树权值都小于它,右边的子树权值都大于它)。然后它就可以通过打标记的方式实现区间的翻转操作。具体方法是:如果要对一段区间进行操作的话,只要:int L=find(l-1),R=find(r+1)...
March 21, 2019

Splay初步

这里主要讲一讲Splay的基础操作(插入,删除)。前言Splay本质上是一棵二叉查找树。这种树有许多美妙的性质:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉查找树。但是它也有缺点:可能退化成一条链。所以Splay就是通过不断地对树中的点进行旋转和变换,让树的高度保持在logn。旋转y...
March 17, 2019

MTT板子

先放个板子。void MTT(LL *A,LL *B,int la,int lb,LL *C){ int mm=la+lb,nn,c=0; for(nn=1;nn<mm;nn<<=1)c++; for(int i=0;i<nn;i++){ rev[i]=(rev[i>>1]>>1)|((i&1)&...