Splay伸展树学习小记 Poj 3580 SuperMemo

我不是女神ヾ 2023-07-03 07:20 46阅读 0赞

伸展树看了几天了，总算是摸着点方向，只能说这真的是神一样的数据结构，各种延迟标记……

参考了很多大牛的博客，代码的基本写法从网上挑了一种比较好理解的开始模仿。

这里有一个模板和对一道题的分析，一开始我模仿的就是这个，最后发现指针还是有点不习惯……最后我会贴出用这个模板解这题的代码。

这个模板是少数这道题可以跑进1s内的，不过利用数组建树那部分似乎有bug：

[Splay Tree 标签\_51CTO技术博客][Splay Tree _51CTO]

以下链接是网上关于Splay的总结，里面有许多题解……这些都给了我很大的帮助！

cxlove的，网上很多人都是他的写法修改的：[伸展树（Splay tree）学习小结 - 窝是爱酱,喵~~~~ - 博客频道 - CSDN.NET][Splay tree_ - _ - _ - CSDN.NET]

kuangbin的，我正在模仿他的写法：[Splay Tree（伸展树总结） - kuangbin - 博客园][Splay Tree_ - kuangbin -]

今年8月写了400多博文的 haha593572013 的：[无比强大的数据结构 伸展树总结 - 鲜花会有的，AC会有的！ - 博客频道 - CSDN.NET][_ - _AC_ - _ - CSDN.NET]

FZU\_Jason的，还没有仔细看：[【总结】伸展树 - DrunBee - 博客园][- DrunBee -]  
  
这道题的题意和分析在上面几篇博客里都有，我就不写了。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    
    #define Key_value ch[ch[root][1]][0] //根节点右孩子的左孩子
    #define Key_Value ch[ch[root][1]][0]
    
    const int N=200010;
    const int INF=0x3f3f3f3f;
    //分别表示父结点,左右孩子(0为左孩子，1为右孩子),键值,结点规模
    int pre[N],ch[N][2],key[N],size[N];
    //加法延迟标记,翻转延迟标记,最小值
    int add[N],rev[N],m[N];
    int root,tot1;  //根节点,节点数量
    int s[N],tot2;//内存池、内存池容量
    int data[N];  //初始数列数组
    int n,q;
    
    void NewNode (int &r,int father,int k)
    {
        if (tot2)r=s[tot2--];
        else r=++tot1;
        ch[r][0]=ch[r][1]=0;
        pre[r]=father;
        size[r]=1;
        add[r]=rev[r]=0;
        key[r]=m[r]=k;
    }
    void Update_Rev (int r)  //更新r节点的翻转值
    {
        if(!r)return;
        swap(ch[r][0],ch[r][1]);
        rev[r]^=1;
    }
    void Update_Add (int r,int ADD) //更新r节点的加法值
    {
        if(!r)return;
        add[r]+=ADD;
        key[r]+=ADD;
        m[r]+=ADD;
    }
    void Push_Up (int r) //向上更新,由r节点的儿子更新r节点
    {
        size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
        m[r]=key[r];
        if(ch[r][0])m[r]=min(m[r],m[ch[r][0]]);
        if(ch[r][1])m[r]=min(m[r],m[ch[r][1]]);
    }
    void Push_Down (int r)  //向下更新,由r节点更新其儿子节点
    {
        if (rev[r])
        {
            Update_Rev(ch[r][0]);
            Update_Rev(ch[r][1]);
            rev[r]=0;
        }
        if (add[r])
        {
            Update_Add(ch[r][0],add[r]);
            Update_Add(ch[r][1],add[r]);
            add[r]=0;
        }
    }
    
    void Build (int &x,int l,int r,int father)
    {//利用数组data建树,data从1开始,有n个元素
    //调用格式 Build(Key_value,1,n,ch[root][1]);
        if (l>r) return;
        int mid=(l+r)>>1;
        NewNode(x,father,data[mid]);
        Build(ch[x][0],l,mid-1,x);
        Build(ch[x][1],mid+1,r,x);
        Push_Up(x);
    }
    
    void Init ()
    {//Splay初始化
        root=tot1=tot2=0;
        ch[root][0]=ch[root][1]=size[root]=add[root]=rev[root]=pre[root]=0;
        m[root]=INF;//这个不用也可以,如果在push_up那判断了的话，否则需要
        NewNode(root,0,INF);
        NewNode(ch[root][1],root,INF);
        
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Rotate (int x,int kind)
    {//旋转
        int y=pre[x];
        Push_Down(y);
        Push_Down(x);
        ch[y][!kind]=ch[x][kind];
        pre[ch[x][kind]]=y;
        if(pre[y])
            ch[pre[y]][ch[pre[y]][1]==y]=x;
        pre[x]=pre[y];
        ch[x][kind]=y;
        pre[y]=x;
        Push_Up(y);
    }
    
    void Splay (int r,int goal) 
    {//Splay调整,将第r节点调整到goal位置
        Push_Down(r);
        while(pre[r]!=goal)
        {
            if(pre[pre[r]]==goal)
            {
                //这题有反转操作，需要先push_down,再判断左右孩子
                Push_Down(pre[r]);
                Push_Down(r);
                Rotate(r,ch[pre[r]][0]==r);
            }
    
            else
            {
                //这题有反转操作，需要先push_down,再判断左右孩子
                Push_Down(pre[pre[r]]);
                Push_Down(pre[r]);
                Push_Down(r);
                int y=pre[r];
                int kind=(ch[pre[y]][0]==y);
                //两个方向不同，则先左旋再右旋
                if(ch[y][kind]==r)
                {
                    Rotate(r,!kind);
                    Rotate(r,kind);
                }
                //两个方向相同，相同方向连续两次
                else
                {
                    Rotate(y,kind);
                    Rotate(r,kind);
                }
            }
        }
        Push_Up(r);
    	//更新根节点
        if(goal==0)root=r;
    }
    
    int Get_Kth (int r,int k)   //找第k个节点
    {
        Push_Down(r);
        int t=size[ch[r][0]]+1;
        if(t==k)return r;
        if(t>k)return Get_Kth(ch[r][0],k);
        else return Get_Kth(ch[r][1],k-t);
    }
    int Get_Min (int r)
    {
        Push_Down(r);
        while (ch[r][0])
        {
            r=ch[r][0];
            Push_Down(r);
        }
        return r;
    }
    
    int Get_Max (int r)
    {
        Push_Down (r);
        while (ch[r][1])
        {
            r=ch[r][1];
            Push_Down(r);
        }
        return r;
    }
    
    //下面是操作了
    
    void Add (int l,int r,int D)
    {//区间l到r全部加D
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        Update_Add(Key_value,D);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Reverse (int l,int r)
    {//区间l到r全部翻转
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        Update_Rev(Key_value);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Revolve (int l,int r,int T)
    {//循环右移T长度,其实就是交换区间
        int len=r-l+1;
        T=(T%len+len)%len;
        if (T==0)return;
        int c=r-T+1;//将区间[c,r]放在[l,c-1]前面
        Splay(Get_Kth(root,c),0);
        Splay(Get_Kth(root,r+2),root);
        int tmp=Key_value;
        Key_value=0;   //此时已将区间拆下
        Push_Up(ch[root][1]);  //拆下后记得更新
        Push_Up(root);
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,l+1),root);  //放在l之前
        Key_value=tmp;
        pre[Key_value]=ch[root][1];//这个不要忘记
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Insert (int x,int P)
    {//在第x个数后面插入P
        Splay(Get_Kth(root,x+1),0);
        Splay(Get_Kth(root,x+2),root);
        NewNode(Key_value,ch[root][1],P);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void erase (int r)
    {//回收内存
        if(r)
        {
            s[++tot2]=r;
            erase(ch[r][0]);
            erase(ch[r][1]);
        }
    }
    
    void Delete (int x)
    {//删除第x个数
        Splay(Get_Kth(root,x),0);
        Splay(Get_Kth(root,x+2),root);
        erase(Key_value);
        pre[Key_value]=0;
        Key_value=0;
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    int Query_Min (int l,int r)
    {//查找区间最小
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        return m[Key_value];
    } 
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int n,m,i;
    	char str[10];
    	scanf("%d",&n);
    	Init();
    	for (i=1;i<=n;i++)
    		scanf("%d",&data[i]);
    	
    	Build(Key_value,1,n,ch[root][1]);
    	scanf("%d",&m);
    	int x,y,tmp;
    	while (m--)
    	{  
    		scanf("%s",str);  
            switch (str[0])
            {  
    		case 'A':
    			scanf("%d%d%d", &x, &y, &tmp);  
    			Add(x,y,tmp);  
    			break;
    		case 'R':  
    			if ('E' == str[3])  
    			{ 
    				scanf("%d%d", &x, &y);
    				Reverse(x, y);  
    			}  
    			else  
    			{
    				scanf("%d%d%d", &x, &y, &tmp);
    				Revolve(x, y, tmp);
    			}
    			break;
    		case 'I':
    			scanf("%d%d", &x, &tmp);
    			Insert(x,tmp);
    			break;  
    		case 'D':  
    			scanf("%d", &x);
    			Delete(x);
    			break;  
    		case 'M':  
    			scanf("%d%d", &x, &y);
    			printf("%d\n",Query_Min(x,y));
    			break;  
    		}
    	}  
    	return 0;
    }

#include <iostream> 
    #include <cstdio> 
    #include <cstring> 
    #include <cstdlib> 
    #include <cmath> 
    #define max(a,b) ((a)>(b)?(a):(b))
    #define max3(a,b,c) (max(a,max(b,c)))
    #define min(a,b) ((a)<(b)?(a):(b))
    #define min3(a,b,c) (min(a,min(b,c)))
    using namespace std;
    
    const int INF=0x7fffffff; 
    const int MAXPT=1000005; 
    
    class SPLAYTREE
    {
    public:
    	 struct Node
    	 { 
             int key,minv,size,add;//键值,区间最小值,子树规模,相加延迟标记
             bool rev;  //翻转标记
             Node *left,*right,*father;
             Node (){}
             Node(int _key):key(_key){minv=_key,size=1,add=0,rev=false;} 
         }SPLAY[MAXPT],*SP,*root,*head,*tail; 
    
         void init () //初始化一棵伸展树，只有head和tail结点
    	 {//tail.size=1,head.size=1(初始)而且保证以后接入的结点：Node.size>=head.size
             SP=SPLAY;
             SPLAY->key=SPLAY->minv=INF,SPLAY->size=0;SPLAY->rev=false;SPLAY->add=0; 
             SPLAY->left=SPLAY->right=SPLAY->father=SPLAY; 
             head=new(++SP)Node(INF); 
             head->left=head->right=head->father=SPLAY; 
             tail=new(++SP)Node(INF); 
             tail->left=tail->right=tail->father=SPLAY; 
             head->right=tail,tail->father=head,head->size++; 
             root=head;//最开始,root的值为head,head和tail是固定不变的,而root的指向的地址是会变化的 
         } 
    
         void pushdown (Node *&t)//延迟操作的经典代码：把当前的标记下推一个节点
    	 { 
             if (t->rev)
    		 {//如果区间需要旋转 
                 swap(t->left,t->right); 
                 t->left->rev=!t->left->rev; 
                 t->right->rev=!t->right->rev; 
                 t->rev=false; 
             } 
             if (t->add)
    		 {//如果区间的值要加add 
                 if(t->left!=SPLAY){ 
                     t->left->key+=t->add; 
                     t->left->minv+=t->add; 
                     t->left->add+=t->add; 
                 } 
                 if(t->right!=SPLAY){ 
                     t->right->key+=t->add; 
                     t->right->minv+=t->add; 
                     t->right->add+=t->add; 
                 } 
                 t->add=0; 
             } 
         } 
    
         void pushup (Node *&t)//更新区间的最小值和区间元素的个数 
    	 { 
             t->size=t->left->size+t->right->size+1; 
             t->minv=min3(t->key,t->left->minv,t->right->minv); 
         } 
    
         void zig (Node *&t)
    	 { //右旋转操作 
             Node *f=t->father,*r=t->right; 
             pushdown(f->right); 
             pushdown(t->left); 
             pushdown(t->right); 
             t->father=f->father; 
             if (f==root) root=t; 
             else{ 
                 if(f->father->left==f) f->father->left=t; 
                 else f->father->right=t; 
             } 
             t->right=f,r->father=f,f->father=t,f->left=r; 
             pushup(f);pushup(t); 
         } 
    
         void zag (Node *&t)
    	 { //左旋转操作 
             Node *f=t->father,*l=t->left; 
             pushdown(f->left); 
             pushdown(t->left); 
             pushdown(t->right); 
             t->father=f->father; 
             if(f==root) root=t; 
             else{ 
                 if(f->father->left==f) f->father->left=t; 
                 else f->father->right=t; 
             } 
             t->left=f,l->father=f,f->father=t,f->right=l; 
             pushup(f);pushup(t); 
         } 
    
         void splay (Node *&root,Node *&t)
    	 {// 伸展树的核心：伸展操作 
             pushdown(t); 
             while (root!=t)
    		 { 
                 if(t->father==root){ 
                     if(t->father->left==t) zig(t); 
                     else zag(t);//单旋转 
                 } 
                 else{ 
                     if(t->father->father->left==t->father){ 
                         if(t->father->left==t) zig(t->father),zig(t);//一字旋转 
                         else zag(t),zig(t);//之字旋转 
                     }else{ 
                         if(t->father->left==t) zig(t),zag(t);//之字旋转 
                         else zag(t->father),zag(t);//一字旋转 
                     } 
                 } 
             } 
         } 
    
    //         建树            /
    
         Node* build (Node *father,int *a,int ll,int rr)  //返回该树根节点
    	 { //仿线段树建树方式建立一个splay树，与build_tree合用
             if(ll>rr)return SPLAY; 
             int mid=(ll+rr)>>1; 
             SP=SP+mid; 
             Node *t; 
             t=new(SP)Node(a[mid]); 
             t->father=father; 
             t->left=build(t,a,ll,mid-1); 
             t->right=build(t,a,mid+1,rr); 
             pushup(t); 
             return t; 
         } 
         /* 
          * function: 把数组a建立成一棵伸展树。采用的建树方式与线段树的建树方式相同 
          * 
          * @param:root 新建立树的根 
          * @param: a  建树用到的数组，0位置不存元素 
          * @param: n  数组a中元素的个数 
          * */ 
         void build_tree (Node *&t,int *a,int n)
    	 { 
             int ll=1,rr=n; 
             int mid=(ll+rr)>>1; 
             SP=SP+mid; 
             t=new(SP)Node(a[mid]); 
             t->father=SPLAY; 
             t->left=build(t,a,ll,mid-1); 
             t->right=build(t,a,mid+1,rr); 
             pushup(t); 
         } 
    
         void insert (int key,int pos)
    	 {// 插入一个值到指定的位置 
             Node *t=new(++SP)Node(key); 
             t->left=t->right=t->father=SPLAY; 
             Node *r=root,*p; 
             bool flag=false;//默认插入树的左孩子上 
             while(pushdown(r),r!=SPLAY){ 
                 p=r,r->size++; 
                 if(r->left->size+1>pos)r=r->left,flag=false; 
                 else pos-=r->left->size+1,r=r->right,flag=true; 
             } 
             if(flag) p->right=t; 
             else p->left=t; 
             t->father=p; 
             splay(root,t); 
         } 
    
    //         建树            /
        
         void select (Node *&root,int pos)
    	 {// 把pos位置的元素旋转到根结点(或任意*&root所指的位置)
             Node *r=root; 
             while (pushdown(r),r->left->size+1!=pos){ 
                 if(r->left->size+1>pos) r=r->left; 
                 else pos-=r->left->size+1,r=r->right; 
             } 
             splay(root,r); 
         } 
    
         void insert_k (int pos,int *a,int n)      //函数有bug!!!!!!!
    	 { //把a中的n个数插入数组中，a的0号位不用 
             Node *t; 
             build_tree(t,a,n); 
             select(root,pos); 
             select(root->right,1); 
             root->right->left=t; 
             t->father=root->right; 
             pushup(root->right); 
             pushup(root); 
             splay(root,t); 
         } 
    
         void remove (int pos)
    	 {// 把pos位置的元素删除
             select(root,pos); 
             if(root->left==SPLAY) root=root->right; 
             else if(root->right==SPLAY) root=root->left; 
             else{ 
                 select(root->left,root->left->size); 
                 root->left->right=root->right; 
                 root->right->father=root->left; 
                 root=root->left; 
             } 
             root->father=SPLAY;
             pushup(root); 
         } 
    
          void remove_k (int ll,int rr)
    	  { //删除区间[l,r] 
              //确定区间 
              select(root,ll); 
              select(root->right,rr-ll); 
              //执行删除操作 
              root->right->left=SPLAY; 
              pushup(root->right); 
              pushup(root); 
          } 
    
         void plus (int l,int r,int a)
    	 {//区间[l,r]同时加上a
             //确定区间 
             select(root,l); 
             select(root->right,r-l); 
             //执行操作 
             Node *t=root->right->left; 
             t->add+=a,t->key+=a,t->minv+=a; 
             splay(root,t);  //记得splay
         } 
    
         void reverse (int l,int r)
    	 {// 翻转区间[l,r] 
             select(root,l); 
             select(root->right,r-l); 
             Node *t=root->right->left; 
             t->rev=!t->rev; 
             splay(root,t);  //记得splay
         }
    
         void revolve (int l,int r,int a)
    	 {// 区间[l,r]循环右移a次,revolve l r a 其实就是交换(l,r-a)和(r-a+1,r)两个区间。
    		 if (a%(r-2-l+1))  //传递过来的参数与带求差2
    		 {
    			 a=a%(r-2-l+1);
    			 select(root,l); 
    			 select(root->right,r-l); 
    			 select(root->right->left,root->right->left->size-a); 
    			 select(root->right->left->right,root->right->left->right->size); 
    			 Node *p=root->right->left,*t=root->right->left->right; 
    			 p->right=SPLAY; 
    			 p->father->left=t,t->father=p->father; 
    			 t->right=p,p->father=t; 
    			 pushup(t);pushup(p); 
    			 splay(root,p); //}   //记得splay
    		 } 
    	 }
    
         int query (int l,int r)
    	 { //查询区间的最小值 
             select(root,l); 
             select(root->right,r-l); 
             return root->right->left->minv; 
         } 
    
         void inorder (Node *t)
    	 { //从结点t开始 中序遍历树
             pushdown(t); 
            if (t->left!=SPLAY) 
                inorder(t->left); 
            if (t->key!=INF)printf("%d ",t->key); 
            if (t->right!=SPLAY) 
                inorder(t->right); 
    
        } 
    }tree; 
    
    int l,r,x,pos;
    char str[10];
    int data[100000+10];
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int n,m,i;
    	scanf("%d",&n);
    	tree.init();
    	for (i=1;i<=n;i++)
    		scanf("%d",&data[i]);//,tree.insert(data[i],i);
    	
    	tree.insert_k(1,data,n);
    	scanf("%d",&m);
    	int x,y,tmp;
    	while (m--)
    	{  
    		scanf("%s",str);  
            switch (str[0])
            {  
    		case 'A':
    			scanf("%d%d%d", &x, &y, &tmp);  
    			y+=2;
    			tree.plus(x,y,tmp);  
    			break;  
    		case 'R':  
    			if ('E' == str[3])  
    			{ 
    				scanf("%d%d", &x, &y);  x,y+=2;
    				tree.reverse(x, y);  
    			}  
    			else  
    			{
    				scanf("%d%d%d", &x, &y, &tmp);  x,y+=2;
    				tree.revolve(x, y, tmp);  
    			}  
    			break;  
    		case 'I':  
    			scanf("%d%d", &x, &tmp);  x++;
    			tree.insert(tmp,x);  
    			break;  
    		case 'D':  
    			scanf("%d", &x);  x++;
    			tree.remove(x);
    			break;  
    		case 'M':  
    			scanf("%d%d", &x, &y);  x,y+=2;
    			int ans=tree.query(x, y);  
    			printf("%d\n",ans);
    			break;  
    		}  
    	}  
    	return 0;
    }

[Splay Tree _51CTO]: http://blog.51cto.com/tag-Splay%20Tree.html
[Splay tree_ - _ - _ - CSDN.NET]: http://blog.csdn.net/acm_cxlove/article/details/7815019
[Splay Tree_ - kuangbin -]: http://www.cnblogs.com/kuangbin/archive/2013/04/21/3034081.html
[_ - _AC_ - _ - CSDN.NET]: http://blog.csdn.net/crazy_ac/article/details/8034264
[- DrunBee -]: http://www.cnblogs.com/DrunBee/archive/2012/08/20/2646593.html