2010 天津赛区G hdu 3726 splay

哎,一道裸splay的题目,网上竟然木有解题报告。我第一次写splay,犯了很多很多NC的错误。。调了有一个下午,最后写了个测试模块+生成了随机数据,才发现错误。
说说我的失误吧。。
1、首先zig zag实现的时候一定要配对,不能乱,加个儿子节点就要把儿子节点的父亲节点同时初始化好
2、新加入节点的size域及其祖先的size域名不用调整,会在splay过程中自动修正完毕
3、千万别要试图将一颗子树的根节点插入到另外一棵树中,以为将两棵树给合并住了。。BST的定义是左子树中的所有节点严格小于根节点,而不仅仅是左儿子节点,右子树亦同。

然后针对本题说说,要倒过来操作,不断的将连通分支合并,相当于合并两颗splay,没有快速的方法,把size小的子树里的节点一个一个塞到大树中。记得这个思想MS是09年一场网络赛里有过的,不过那题的询问很简单,恩
代码
# include <cstdio>
# include <utility>
# include <functional>
# include <cstdlib>
# include <vector>
using namespace
std;
struct
node
{

    int
sz;
    pair<int,int> val;
    node *l,*r,*pre;
    void
clear()
    {

        l=r=pre=NULL;
    }
}
buff[20005];
inline
bool cmp(const pair<int,int> &a,const pair<int,int> &b)
{

    if
(a.first!=b.first) return a.first<b.first;
    else return
a.second<b.second;
}

inline
void update(node *pos)
{

    pos->sz=(pos->l?(pos->l->sz):0)+(pos->r?(pos->r->sz):0)+1;
}

void
zig(node *pos)
{

    node *gf=pos->pre->pre,*f=pos->pre;
    (
f->l)=(pos->r);
    if
(pos->r) (pos->r->pre)=f;
    update(f);
    (
pos->r)=f;
    (
f->pre)=pos;
    (
pos->pre)=gf;
    if
(gf&&(gf->l)==f) gf->l=pos;
    else if
(gf&&(gf->r)==f) (gf->r)=pos;
}

void
zag(node *pos)
{

    node *gf=pos->pre->pre,*f=pos->pre;
    (
f->r)=(pos->l);
    if
(pos->l) (pos->l->pre)=f;
    update(f);
    f->pre=pos;
    pos->l=f;
    pos->pre=gf;
    if
(gf&&gf->l==f) (gf->l)=pos;
    else if
(gf&&gf->r==f) (gf->r)=pos;
}

void
spaly(node *pos)
{

    while
(pos->pre)
    {

        if
(pos->pre->pre==NULL)
            if
(pos==(pos->pre->l)) zig(pos);
            else
zag(pos);
        else

        {

            node *t=pos->pre->pre;
            if
(t->l&&pos==(t->l->l))
                zig(pos->pre),zig(pos);
            else if
(t->r&&pos==(t->r->r))
                zag(pos->pre),zag(pos);
            else if
(t->l&&pos==(t->l->r))
                zag(pos),zig(pos);
            else

            {

                zig(pos);
                zag(pos);
            }
        }
    }

    update(pos);
}

void
sub_insert(node *p1,node *p2)
{

    node *pre;
    spaly(p2);
    while
(p2)
    {

        pre=p2;
        if
(cmp(p1->val,p2->val)) p2=p2->l;
        else
p2=p2->r;
    }

    if
(cmp(p1->val,pre->val))
        pre->l=p1,p1->pre=pre,spaly(p1);
    else

        pre->r=p1,p1->pre=pre,spaly(p1);
}

void
ins(node *p1,node *p2)
{

    if
(p1->l) ins(p1->l,p2);
    if
(p1->r) ins(p1->r,p2);
    p1->l=p1->r=p1->pre=NULL;
    p1->sz=1;
    sub_insert(p1,p2);
}

void
insert(node *p1,node *p2)
{

    spaly(p1),spaly(p2);
    if
(p1->sz<p2->sz)
        ins(p1,p2);
    else
ins(p2,p1);
}

int
select(int pos,int k)
{

    node *p=buff+pos;
    spaly(p);
    if
(k>(p->sz)||k<1) return 0;
    else
k=(p->sz)+1-k;
    int
co=0;
    while
(true)
    {

        if
(co++>500000) exit(0);
        if
((p->l?p->l->sz:0)>=k) p=p->l;
        else if
((p->l?p->l->sz:0)+1==k)
           break
;
        else
k-=(p->l?(p->l->sz):0)+1,p=p->r;
    }

     spaly(p);
     return
p->val.first;
}

void
change(pair<int,int> val)
{

    node *p=buff+val.second;
    spaly(p);
    p->val=val;
    if
(p->l&&p->r)
    {

        node *t1=(p->l),*t2=(p->r);
        (
t1->pre)=(t2->pre)=(p->l)=(p->r)=NULL;
        while
(t1->r) t1=t1->r;
        spaly(t1);
        (
t1->r)=t2;
        (
t2->pre)=t1;
        spaly(t2);
        insert(t2,p);
    }

    else if
(p->l)
    {

        node *t=p->l;
        (
p->l)=(t->pre)=NULL;
        insert(t,p);
    }

    else if
(p->r)
    {

        node *t=p->r;
        (
p->r)=(t->pre)=NULL;
        insert(t,p);
    }

}

int
n,m;
pair<int,int> edge[60005];
bool
used[60005];
int
father[20005];
pair<int,pair<int,int> >  ask[1000005];
int
co=0;
int
find(int pos)
{

    if
(father[pos]==pos) return pos;
    else return
father[pos]=find(father[pos]);
}

int
main()
{

    int
test=1;
    while
(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {

        for
(int i=1;i<=n;i++)
        {

            buff[i].clear();
            buff[i].val.second=i;
            father[i]=i;
            scanf("%d",&buff[i].val.first);
        }

        for
(int i=1;i<=m;i++)
        {

            used[i]=true;
            scanf("%d%d",&edge[i].first,&edge[i].second);
        }

        char
type[5];
        int
number=0;
        co=0;
        while
(scanf("%s",type)&&*type!='E')
        {

            pair<int,pair<int,int> > tmp;
            switch
(*type)
            {

            case
'D':
                tmp.first=2;
                scanf("%d",&tmp.second.first);
                used[tmp.second.first]=false;
                break
;
            case
'C':
            {

                tmp.first=1;
                scanf("%d%d",&tmp.second.second,&tmp.second.first);
                int
tt=buff[tmp.second.second].val.first;
                buff[tmp.second.second].val=tmp.second;
                tmp.second.first=tt;
                break
;
            }

            case
'Q':
                tmp.first=0;
                number++;
                scanf("%d%d",&tmp.second.first,&tmp.second.second);
                break
;
            };

            ask[co++]=tmp;
        }

        for
(int i=1;i<=m;i++)
            if
(used[i]&&find(edge[i].first)!=find(edge[i].second))
                insert(buff+edge[i].first,buff+edge[i].second),father[find(edge[i].first)]=find(edge[i].second);

           
        double
total=0;
        for
(int i=co-1;i>=0;i--)
        {

            switch
(ask[i].first)
            {

            case
0:
                total+=select(ask[i].second.first,ask[i].second.second);
                break
;
            case
1:
                change(ask[i].second);
                break
;
            case
2:
                //break;
                if(find(edge[ask[i].second.first].first)!=find(edge[ask[i].second.first].second))
                insert(buff+edge[ask[i].second.first].first,buff+edge[ask[i].second.first].second),
                father[find(edge[ask[i].second.first].first)]=find(edge[ask[i].second.first].second);
                break
;
            };
        }

        printf("Case %d: %.6f\n",test++,number?total/number:0);

    }

    return
0;
}

posted on 2011-09-30 08:51 yzhw 阅读(454) 评论(0)  编辑 收藏 引用 所属分类: data struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜