本文共 4869 字，大约阅读时间需要 16 分钟。
题意：给一个数组，有6种操作：
add x y d ： [x,y]中所有数加d
reverse x y: [x,y]区间翻转
revolve x y t: [x,y]循环右移t位，t可取任意整数
insert x v: 在第x个位置插入一个值为v的数
delete x : 删除第x个数
min x y : 求区间[x,y]的最小值
题解：典型splay，通过旋转使得要处理的区间转到root的右孩子的左子树上，然后所有操作均在这上面处理：
add/reverse :可以直接用标记处理，在下次旋转时通过下传标记解决
revolve :则可看做把最右边含t个结点的子树嫁接到最左端去
insert :可以将要插入位置转到根节点，然后把它下一个结点转到根节点的右孩子上，这样直接在这两个结点间添加一个结点便可以解决
delete :将x位置上一位转到根节点，x位置下一位转到根节点的右孩子上，然后删除其左孩子。
这是我第一棵splay，看论文花了半天，写花了半天，调试用了一天，re无数，wa一次，反反复复优化，最后勉强进入一秒。若光从旋转操作上看splay,它的确是个水结构，但是各种翻转，轮换叠加在一起也足以让人蛋疼一阵子了。
#include#include #include using namespace std;typedef struct sp_node * Node;const int MAXN=210010,inf=100000000;struct sp_node{ Node pre,ch[2]; int value,lazy,Min,size;//结点价值，lazy标记，子树最小值，子树大小 bool rev;//是否旋转 void init(int _value) { pre=ch[0]=ch[1]=NULL; Min=value=_value; lazy=0; size=1; rev=false; }} nstack[MAXN];int scnt;//静态申明splay结点的栈顶位置Node root;inline int getsize(Node &x)//取得x子树大小，主要是解决x=NULL的情况{ return x?x->size:0;}void pushdown(Node &x)//将x标记下移{ if(!x) return; if(x->lazy) { int w=x->lazy; x->value+=w; if(x->ch[0]) { x->ch[0]->lazy+=w; x->ch[0]->Min+=w; } if(x->ch[1]) { x->ch[1]->lazy+=w; x->ch[1]->Min+=w; } x->lazy=0; } if(x->rev) { Node t=x->ch[0]; x->ch[0]=x->ch[1]; x->ch[1]=t; x->rev=false; if(x->ch[0]) x->ch[0]->rev^=1; if(x->ch[1]) x->ch[1]->rev^=1; }}void updata(Node &x)//更新x结点信息{ if(!x) return; x->size=1; x->Min=x->value; if(x->ch[0]) { x->Min=min(x->Min,x->ch[0]->Min); x->size+=x->ch[0]->size; } if(x->ch[1]) { x->Min=min(x->Min,x->ch[1]->Min); x->size+=x->ch[1]->size; }}void rotate(Node &x, int d) // 旋转操作，d=0 表示左旋，d=1 表示右旋{ Node y=x->pre; pushdown(y); pushdown(x); pushdown(x->ch[d]); y->ch[!d]=x->ch[d]; if (x->ch[d]!=NULL) x->ch[d]->pre=y; x->pre = y->pre; if (y->pre!=NULL) { if (y->pre->ch[0]==y) y->pre->ch[0]=x; else y->pre->ch[1]=x; } x->ch[d]=y,y->pre=x; updata(y); if (y == root)//因为是指针，所以root可能被转下去了 root = x;}void splay(Node &x, Node &f) // Splay 操作，表示把结点x 转到结点f{ for (pushdown(x); x!=f;) { if(x->pre==f) { if(f->ch[0]==x) rotate(x,1); else rotate(x,0); break; } else { Node y=x->pre,z=y->pre; if (z->ch[0] == y) if (y->ch[0] == x) rotate(y,1),rotate(x, 1); // 一字形旋转 else rotate(x, 0), rotate(x, 1); // 之字形旋转 else if (y->ch[1] == x) rotate(y, 0), rotate(x, 0); // 一字形旋转 else rotate(x, 1), rotate(x, 0); // 之字形旋转 if(z==f)//转了之后，x就到了原来z的位置，如果z就是要到的地方，就可以退出了 break; } updata(x); } updata(x);}void select(int k, Node &f){ int tmp; Node t; for(t=root;;) { pushdown(t); tmp=getsize(t->ch[0]); // 得到t 左子树的大小 if (k == tmp + 1) break; // 得出t 即为查找结点，退出循环 if (k <= tmp) // 第k 个结点在t 左边，向左走 t = t->ch[0]; else // 否则在右边，而且在右子树中，这个结点不再是第k 个 k -=tmp+1,t=t->ch[1]; } pushdown(t); splay(t, f); // 执行旋转}void insert(int pos,int value){ select(pos+1,root); select(pos+2,root->ch[1]); Node t=nstack+scnt++,x=root->ch[1]; pushdown(root); pushdown(x); t->init(value); t->ch[1]=x; x->pre=t; root->ch[1]=t; t->pre=root; splay(x,root);}void add(int a,int b,int d){ select(a,root); select(b+2,root->ch[1]); Node x=root->ch[1]->ch[0]; pushdown(x); updata(x); x->Min+=d; x->lazy+=d; splay(x,root);}void reverse(int a,int b){ select(a,root); select(b+2,root->ch[1]); root->ch[1]->ch[0]->rev^=1; Node x=root->ch[1]->ch[0]; splay(x,root);}void revolve(int a,int b,int t){ Node p1,p2; select(a,root); select(b+2,root->ch[1]); select(b+1-t,root->ch[1]->ch[0]); p1=root->ch[1]->ch[0]; pushdown(p1); p2=p1->ch[1]; p1->ch[1]=NULL; select(a+1,root->ch[1]->ch[0]); p1=root->ch[1]->ch[0]; pushdown(p1); p1->ch[0]=p2; p2->pre=p1; splay(p2,root);}int getmin(int a,int b){ select(a,root); select(b+2,root->ch[1]); Node x=root->ch[1]; pushdown(x); x=x->ch[0]; pushdown(x); updata(x); return x->Min;}void erase(int pos){ select(pos,root); select(pos+2,root->ch[1]); pushdown(root->ch[1]); root->ch[1]->ch[0]=NULL; Node x=root->ch[1]; splay(x,root);}int main(){ int i,a,b,c,k,n,m; scnt=0; root=nstack+scnt++; root->init(inf); root->ch[1]=nstack+scnt++; root->ch[1]->init(inf); scanf("%d",&n); for(i=0; i
转载地址：http://lxbqi.baihongyu.com/