当前位置:编程学习 > C/C++ >>

HDU 3487 Play with Chain (Splay tree)

再撸一发Splay。
包括区间切割和反转操作。
对于Splay处理区间[l,r],将l-1转至根部,将r+1转至根的右孩子,这样根的右孩子的左子树便为[l,r],相当犀利啊,Splay的操作大多基于这样的旋转操作。
对于切割,便是旋转之后,把子树先取下,然后再转到要插入的位置,将子树接上。
反转操作,加个懒惰标记,表示子树是否要交换,

[cpp]
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<cstdio> 
#include<algorithm> 
#define N 300015 
#define inf 1<<29 
#define MOD 100000007 
#define LL long long 
#define Key_value ch[ch[root][1]][0] 
#define _match(a,b) ((a)==(b)) 
using namespace std; 
int n,q; 
int size[N],pre[N],key[N],num[N],rev[N]; 
int ch[N][2],tot,root,node[N]; 
//debug部分copy from hh   
void Treaval(int x) {   
    if(x) {   
        Treaval(ch[x][0]);   
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);   
        Treaval(ch[x][1]);   
    }   
}   
void debug() {printf("%d\n",root);Treaval(root);}   
//以上Debug   
void NewNode(int &r,int k,int father){ 
    r=++tot; 
    ch[r][0]=ch[r][1]=0; 
    pre[r]=father; 
    rev[r]=0; 
    key[r]=k; 

void Push_Up(int r){ 
    size[r]=size[ch[r][0]]+size[ch[r][1]]+1; 

void Push_Down(int r){ 
    if(rev[r]){ 
        swap(ch[r][0],ch[r][1]); 
        rev[ch[r][0]]^=1; 
        rev[ch[r][1]]^=1; 
        rev[r]=0;        
    } 

void Bulid(int &r,int L,int R,int father){ 
    if(L>R) 
        return ; 
    int mid=(L+R)/2; 
    NewNode(r,mid,father); 
    Bulid(ch[r][0],L,mid-1,r); 
    Bulid(ch[r][1],mid+1,R,r); 
    Push_Up(r); 

void Init(){ 
    tot=root=0; 
    ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0; 
    NewNode(root,-1,0); 
    NewNode(ch[root][1],-1,root); 
    size[root]=2; 
    Bulid(Key_value,1,n,ch[root][1]); 
    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){   
    Push_Down(r); 
    while(pre[r]!=goal){   
        if(pre[pre[r]]==goal)   
            Rotate(r,ch[pre[r]][0]==r);   
        else{   
            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){ 
    Push_Down(r); 
    int t=size[ch[r][0]]; 
    if(t==k-1) 
        return r; 
    if(t>=k) 
        return Get_Kth(ch[r][0],k); 
    else 
        return Get_Kth(ch[r][1],k-t-1); 

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 Reversal(int a,int b){ 
    int x=Get_Kth(root,a); 
    int y=Get_Kth(root,b+2); 
    Splay(x,0); 
    Splay(y,root);       
    rev[Key_value]^=1; 

void Cut(int a,int b,int c){ 
    int x=Get_Kth(root,a); 
    int y=Get_Kth(root,b+2);     
    Splay(x,0); 
    Splay(y,root); 
    int tmp=Key_value; 
    Key_value=0; 
    Push_Up(ch[root][1]); 
    Push_Up(root); 补充:软件开发 , C++ ,

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,