Loading...

普通平衡树 洛谷P3369 (finger—tree)

check评论:0 条 remove_red_eye浏览量:327 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-12

关于finger-tree的介绍,就不再多说
这是一种可以实现所有splay的操作以及可持久化的数据结构
为了保持平衡,可以选择旋转或者像替罪羊一样重构
这里采用的是旋转
maintain(旋转)函数:

/*
平衡系数设为4
*/
inline void maintain(Node *rt)
{ 
    if(rt->ls->size>rt->rs->size*4) 
    { 
        rt->rs=NewNode(rt->rs->val,rt->ls->rs->size+rt->rs->size,rt->ls->rs,rt->rs); 
        Node *tmp=rt->ls;
        rt->ls=rt->ls->ls;
        *tmp=*rt->rs;
        rt->rs=tmp;//垃圾回收,下面同理 
        cnt--; 
    } 
    else if(rt->ls->size*4<rt->rs->size) 
    { 
        rt->ls=NewNode(rt->rs->ls->val,rt->rs->ls->size+rt->ls->size,rt->ls,rt->rs->ls); 
        Node *tmp=rt->rs;
        rt->rs=rt->rs->rs;
        *tmp=*rt->ls;
        rt->ls=tmp; 
        cnt--; 
    } 
} 

这个就是旋转操作的代码,其实在洛谷P3369上提交不需要这个操作也可以过(数据水)
接下来贴完整代码
code:

#include<bits/stdc++.h> 
#define MAXN 300006 
using namespace std; 
struct Node 
{ 
    int val,size; 
    Node *ls,*rs; 
    void pushup() 
    { 
        if(ls==NULL)
        {
            return ; 
        }    
        size=ls->size+rs->size; 
        val=rs->val;
    } 
    Node(int v,int s,Node *l,Node *r):val(v),size(s),ls(l),rs(r){}
    Node(){} 
}pool[MAXN]; 
int cnt=0;
Node *root=NULL; 
Node *NewNode(int val,int size,Node *ls,Node *rs) 
{ 
    pool[cnt]=Node(val,size,ls,rs); 
    return &pool[cnt++]; 
} 
int find(int k,Node *rt)
{ 
    if(rt->size==1)
    {
        return rt->val; 
    }
    if(k<=rt->ls->size)
    {
        return find(k,rt->ls);
    }     
    else 
    {
        return find(k-rt->ls->size,rt->rs); 
    }
} 
int Rank(int x,Node *rt)
{ 
    if(rt->size==1) 
    { 
        return 1; 
    } 
    else 
    { 
        if(x<=rt->ls->val)
        { 
            return Rank(x,rt->ls); 
        } 
        else
        { 
            return Rank(x,rt->rs)+rt->ls->size; 
        } 
    } 
} 
inline void maintain(Node *rt)
{ 
    if(rt->ls->size>rt->rs->size*4) 
    { 
        rt->rs=NewNode(rt->rs->val,rt->ls->rs->size+rt->rs->size,rt->ls->rs,rt->rs); 
        Node *tmp=rt->ls;
        rt->ls=rt->ls->ls;
        *tmp=*rt->rs;
        rt->rs=tmp;//垃圾回收,下面同理 
        cnt--; 
    } 
    else if(rt->ls->size*4<rt->rs->size) 
    { 
        rt->ls=NewNode(rt->rs->ls->val,rt->rs->ls->size+rt->ls->size,rt->ls,rt->rs->ls); 
        Node *tmp=rt->rs;
        rt->rs=rt->rs->rs;
        *tmp=*rt->ls;
        rt->ls=tmp; 
        cnt--; 
    } 
} 
void ins(int val,Node *&rt)
{ 
    if(rt==NULL)
    {
        rt=NewNode(val,1,NULL,NULL);
        return ;
    } 
    if(rt->size==1) 
    { 
        rt->ls=NewNode(min(val,rt->val),1,NULL,NULL); 
        rt->rs=NewNode(max(val,rt->val),1,NULL,NULL); 
    } 
    else 
    { 
        if(val>rt->ls->val)
        {
            ins(val,rt->rs);
        } 
        else 
        {
            ins(val,rt->ls); 
        }
    } 
    rt->pushup(); 
    //maintain(rt); 
} 
void del(Node *rt,Node *fa,int val)
{ 
    if(rt->size==1)
    {    
        *fa=fa->ls->val==val?*fa->rs:*fa->ls;
    }     
    else 
    { 
        if(val<=rt->ls->val)
        {
            del(rt->ls,rt,val);
        } 
        else 
        {
            del(rt->rs,rt,val); 
        }
    } 
    rt->pushup(); 
} 
int main() 
{ 
    int n; 
    scanf("%d",&n); 
    root=NewNode(2147483647,1,NULL,NULL); 
    for(int i=1;i<=n;i++) 
    { 
        int opt,x; 
        scanf("%d%d",&opt,&x); 
        if(opt==1)
        {
            ins(x,root);
        } 
        if(opt==2)
        {
            del(root,NULL,x);
        } 
        if(opt==3)
        {
            printf("%d\n",Rank(x,root));
        } 
        if(opt==4)
        {
            printf("%d\n",find(x,root));
        } 
        if(opt==5)
        {
            printf("%d\n",find(Rank(x,root)-1,root));
        } 
        if(opt==6)
        {
            printf("%d\n",find(Rank(x+1,root),root));
        }
    }
}

chevron_left 并查集

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名