高度由习惯堆积
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)&...

HDU6061 RXD and functions

题目题目链接思路显然可以发现,那些a其实和最终的结果没有关系,我们关心的仅仅是所有a的总和,设这个和为$a$。也就是说$g(x)=f(x-a)$通过二项式定理展开得:$\sum_{i=0}^{n}c_i \sum_{j=0}^{i} \binom{i}{j} (-a)^{i-j}x^{j}$因为要求的是$x^j$的系数,所以整理一下,把$j$写在前面。$$ \sum_{j=0}^{n}\su...