加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:59,866
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

大连现场赛B题——splay tree解法

(2011-10-03 19:09:04)
标签:

杂谈

分类: 数据结构

哈哈,果然splay可以过,而且更快啊!神级数据结构啊!膜拜啊!但是每次写都会先TLE两次,然后就找出bug发现是死循环了,然后就过了,以不慢的速度。

下个月去成都打现场赛,努力啊努力!努力夺银!

庆祝一下!yes!

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int left[110000],right[110000],key1[110000],key2[110000],num[110000],fa[110000],root,M,cnt;
bool is[110000];
long long W,H;

inline int Max(int a,int b)
{
    return a>b?a:b;
}

inline void right_rotate(int n)
{
    int t=left[n],r=right[t],f=fa[n];

    left[n]=r,fa[r]=n;
    right[t]=n,fa[n]=t;

    num[n]=num[left[n]]+num[right[n]];
    if(is[n])
        num[n]+=Max(0,key2[n]-key1[n]+2-M);

    num[t]=num[left[t]]+num[right[t]];
    if(is[t])
        num[t]+=Max(0,key2[t]-key1[t]+2-M);

    if(root==n)
    {
        root=t;
        return ;
    }

    fa[t]=f;
    if(left[f]==n)
        left[f]=t;
    else
        right[f]=t;
}
inline void left_rotate(int n)
{
    int t=right[n],l=left[t],f=fa[n];

    right[n]=l,fa[l]=n;
    left[t]=n,fa[n]=t;

    num[n]=num[left[n]]+num[right[n]];
    if(is[n])
        num[n]+=Max(0,key2[n]-key1[n]+2-M);

    num[t]=num[left[t]]+num[right[t]];
    if(is[t])
        num[t]+=Max(0,key2[t]-key1[t]+2-M);

    if(root==n)
    {
        root=t;
        return ;
    }

    fa[t]=f;
    if(left[f]==n)
        left[f]=t;
    else
        right[f]=t;
}

inline void splay(int n)
{
    int f,ff;
    while(n-root)
    {
        f=fa[n],ff=fa[f];

        if(n==left[f])
        {
            if(f==root)
                right_rotate(f);
            else
            {
                if(f==left[ff])
                    right_rotate(ff),right_rotate(f);
                else
                    right_rotate(f),left_rotate(ff);
            }
        }
        else
        {
            if(f==root)
                left_rotate(f);
            else
            {
                if(f==right[ff])
                    left_rotate(ff),left_rotate(f);
                else
                    left_rotate(f),right_rotate(ff);
            }
        }
    }
}

inline void search(int n)
{
    int t=root;

    while(n<key1[t]||n>key2[t])
    {
        if(n<key1[t])
            t=left[t];
        else
            t=right[t];
    }
    splay(t);
}

void insert1(int a,int b)
{
    search(a);

    if(key1[root]==a&&key2[root]==b)
    {
        is[root]=0;
        num[root]=num[left[root]]+num[right[root]];
        return ;
    }
    if(key1[root]==a)
    {
        is[root]=0;
        key1[++cnt]=b+1,key2[cnt]=key2[root];
        right[cnt]=right[root],fa[right[root]]=cnt;
        right[root]=cnt,fa[cnt]=root;
        key2[root]=b;

        is[cnt]=1;
        num[cnt]=num[right[cnt]]+Max(0,key2[cnt]-key1[cnt]+2-M);
        num[root]=num[cnt]+num[left[root]];

        return ;
    }

    if(key2[root]==b)
    {
        is[root]=0;
        key1[++cnt]=key1[root],key2[cnt]=a-1;
        left[cnt]=left[root],fa[left[cnt]]=cnt;
        left[root]=cnt,fa[cnt]=root;
        key1[root]=a;

        is[cnt]=1;
        num[cnt]=num[left[cnt]]+Max(0,key2[cnt]-key1[cnt]+2-M);
        num[root]=num[cnt]+num[right[root]];

        return ;
    }

    is[root]=0;
    key1[++cnt]=key1[root],key2[cnt]=a-1;
    left[cnt]=left[root],fa[left[cnt]]=cnt;
    left[root]=cnt,fa[cnt]=root;
    key1[root]=a;

    is[cnt]=1;
    num[cnt]=num[left[cnt]]+Max(0,key2[cnt]-key1[cnt]+2-M);

    key1[++cnt]=b+1,key2[cnt]=key2[root];
    right[cnt]=right[root],fa[right[root]]=cnt;
    right[root]=cnt,fa[cnt]=root;
    key2[root]=b;

    is[cnt]=1;
    num[cnt]=num[right[cnt]]+Max(0,key2[cnt]-key1[cnt]+2-M);
    num[root]=num[cnt]+num[left[root]];
}

void insert2(int a,int b)
{
    search(a);
    int roo=root;

    if(a>1)
    {
        root=left[root];
        search(a-1);
        fa[root]=roo,left[roo]=root,root=roo;

        if(is[left[root]])
        {
            key2[left[root]]=key2[root];
            right[left[root]]=right[root],fa[right[root]]=left[root];
            root=left[root];
            roo=root;
            num[root]=num[left[root]]+num[right[root]]+Max(0,key2[root]-key1[root]+2-M);
        }
    }
    if(b<W)
    {
        root=right[root];
        search(b+1);
        fa[root]=roo,right[roo]=root,root=roo;

        if(is[right[root]])
        {
            key1[right[root]]=key1[root];
            left[right[root]]=left[root],fa[left[root]]=right[root];
            root=right[root];
            num[root]=num[left[root]]+num[right[root]]+Max(0,key2[root]-key1[root]+2-M);
        }
    }
    is[root]=1;
    num[root]=num[left[root]]+num[right[root]]+Max(0,key2[root]-key1[root]+2-M);

}

struct P
{
    int x1,x2,y1,y2;
}p[50010];

struct S
{
    int x1,x2,y;
    bool is;
}seg[110000];

int cmp(const void *a,const void *b)
{
    if(((S *)a)->y==((S *)b)->y)
        return ((S *)b)->is-((S *)a)->is;
    return ((S *)a)->y-((S *)b)->y;
}

int main()
{
    long long t,s,ans;
    int i,j,N;

    while(scanf("%lld%lld%d%d",&W,&H,&N,&M)!=EOF)
    {
        s=0,ans=0;
        memset(left,0,sizeof(left));
        memset(right,0,sizeof(right));
        for(i=1;i<=N;i++)
            scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2),s+=((long long)(p[i].x2-p[i].x1+1))*((long long)(p[i].y2-p[i].y1+1));
        if(M==1)
        {
            printf("%lld\n",W*H-s);
            continue;
        }
        if(N==0)
        {
            printf("%lld\n",W*(H-M+1)+H*(W-M+1));
            continue;
        }

        root=1,cnt=1;is[1]=1;
        key1[1]=1,key2[1]=W,num[1]=Max(0,key2[1]-key1[1]+2-M);

        for(i=1;i<=N;i++)
        {
            seg[i].x1=p[i].x1,seg[i].x2=p[i].x2,seg[i].y=p[i].y1,seg[i].is=0;
            seg[i+N].x1=p[i].x1,seg[i+N].x2=p[i].x2,seg[i+N].y=p[i].y2+1,seg[i+N].is=1;
        }
        qsort(seg+1,2*N,sizeof(S),cmp);

        ans+=((long long )num[1])*((long long)seg[1].y-1);
        seg[N*2+1].y=H+1;

        for(i=1;i<=N*2;i++)
        {
            if(seg[i].is)
                insert2(seg[i].x1,seg[i].x2);
            else
                insert1(seg[i].x1,seg[i].x2);
            ans+=((long long)num[root])*((long long)(seg[i+1].y-seg[i].y));
        }

        i=W,W=H,H=i;
        memset(left,0,sizeof(left));
        memset(right,0,sizeof(right));

        root=1,cnt=1;is[1]=1;
        key1[1]=1,key2[1]=W,num[1]=Max(0,key2[1]-key1[1]+2-M);

        for(i=1;i<=N;i++)
        {
            seg[i].x1=p[i].y1,seg[i].x2=p[i].y2,seg[i].y=p[i].x1,seg[i].is=0;
            seg[i+N].x1=p[i].y1,seg[i+N].x2=p[i].y2,seg[i+N].y=p[i].x2+1,seg[i+N].is=1;
        }
        qsort(seg+1,2*N,sizeof(S),cmp);

        ans+=((long long )num[1])*((long long)seg[1].y-1);
        seg[N*2+1].y=H+1;

        for(i=1;i<=N*2;i++)
        {
            if(seg[i].is)
                insert2(seg[i].x1,seg[i].x2);
            else
                insert1(seg[i].x1,seg[i].x2);
            ans+=((long long)num[root])*((long long)(seg[i+1].y-seg[i].y));
        }

        printf("%lld\n",ans);
    }
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有