调Splay太恐怖了，虽然不难，但是为什么bug这么多。。。这里记一下原则性问题吧。。。

类名叫SplayTree

• 在我的写法里，每个SplayTree对象不仅代表一个点，它代表整棵子树
• 每个对象里有一个特殊的阈值，SplayTree *Nil，它代表不存在的点（即叶子结点的后继或者是总根节点的前驱），算法导论上好像称之为哨兵，预处理的时候所有的前驱后继都等于Nil（其实原来把Nil定义在了类的外面而不是类的阈值，但是这样会很麻烦。。所以干脆再开个变量叫Nil好了）
• 下面的代码表示阈值：

  • int v,size;//分别是键值，子树大小,
    bool pl;//place 表示该节点在父节点的哪个位置
    ST *pr,*suc[2],*Nil;//分别表示前驱，两个后继，和Nil节点的位置

• 下面的代码声明了各种函数：

  • /*由于SpayTree太长了，一下所写为ST*/
    void mt();//maintain 即维护Splay，保证信息的正确性
    void ini();//初始化，将所有的前驱后继都改成Nil
    void trans(ST *tar,bool place);//将该子树移动到tar的place边（place=0表示左子树，反之右子树）
    void rotate();//旋转，一个函数搞定左旋/右旋
    void Splay();//核心操作，即将某节点提到根
    ST *find_v(int fv)//找到fv所在的位置，找不到返回它应该在的位置的根(按照数字值查询)
    void insert(int iv/*也可以是 ST*p */);//插入iv到相应位置
    void find_s(int pos);//按照size找第pos小的元素，也就是如果要求第pos小的元素是哪个，就可以用这个函数在O(lgn)的时间复杂度内完成
    ST *fmin/*或fmax*/();//找到最小值所在的位置（返回指针）
    void merge(ST *obj);//将obj所在的Splay合并到该节点所在的Splay...

• 下面的代码描述了trans,rotate,Splay的过程

  • 	void trans(ST *tar,bool place){//ST::移形换位
    			pl=place;
    			pr=tar;
    			tar->suc[pl]=this;
    	}
    	void rotate(){//旋转
    	bool ppl=pl;
    	ST fprev=*pr;
    		suc[!pl]->trans(pr,pl);//移动子树
    		pr->trans(this,!pl);//移动原前驱
    		trans(fprev.pr,fprev.pl);//移动该节点
    		suc[!ppl]->mt();
    		mt();
    	}
    	void Splay(){//Splay操作
    		while(pr!=Nil){
    			if(pl==pr->pl && pr->pr!=Nil)
    				pr->rotate();
    			rotate();
    		}
    	}

•  的
• 的

中午的时候突然想起NOI2005的维护序列,于是就写了8小时搞出来,3小时写,5小时调,效率真够低的...

这是个很麻烦的问题,我用Splay解决的,首先题目要求的操作有6种,

其中翻转,求最大和比较麻烦.

1. 对于insert操作,效仿NOI2003的文本编辑器,我直接建了一颗几乎平衡的二叉树,然后塞到Splay中相应的位置(这样快一点点)
2. delete操作比较简单,找到相应的子树,删去即可.
3. MakeSame操作:用delta表示要改变成什么,并传递这个值,每次改变delta都覆盖原有的,注意,如果没有delta值,是不能传递或是更改的,否则就会出错,所以我用了一个极小的常量NA表示没有delta值
4. reverse操作:刚看过去感觉有点奇怪,稍稍思考一下发现reverse操作可以像MakeSame操作那样传递(翻转操作其实就是某棵树中所有的子树位值取反一下(左子树放右边,右子树放左边)),然后向下传递就行了
5. GetSum也好做,用Sum记录该子树的和,每次MakeSame或者是进行Splay操作后维护一下就好了(Sum=左子树的Sum+右子树的Sum+1)
6. MaxSum这个比较不好做,但是之前遇到在过线段树上比这个还要麻烦的问题(求某区间所有子串和的和...),就很容易想到了,即LMax表示某子树构成的序列中最大的前缀和是多少RMax表示最大的后缀和是多少,Max_Sum就表示最大子串和是多少,Max_Sum根据LMax和RMax算出就行了

Splay的两个维护函数:deliver()和maintain()

deliver()负责传递树根信息(翻转和MakeSame)

maintain()负责维护Splay的正确性(重新计算相关信息如Sum,LMax...)

我写了6K的代码,花了我很长的时间,然而并没有结束,因为明天还有继续优化代码和算法结构,以便下次再遇到能很快的写出.