注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2733(hnoi2012) 永无乡neverland(不完美)  

2013-02-09 17:11:36|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

splay+启发式合并

时间复杂度n logn logn

但是我第9个点超时了

其实只要把一些查询之类的地方的splay操作去掉就可以大大加速(也就是介于二叉排序树和splay之间)

另外还有就是二叉排序树也可以过……

反倒是splay很难过……

标准的splay更难过……

这随机数据随机的太厉害了

所以不管他了。我特地找了个splay版本的标程,然后在该splay的地方都splay了下,然后就超时了

这种恶心情况我无力吐槽

update:其实听说合并有个优化,那就是用启发式合并时如果两棵splay的size很接近,将两棵splay变成两个数组再归并排序再建成splay。嗯听说去很不错,先留在这里有时间写写

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 100010
#define update(p) (size[p]=size[son[p][0]]+size[son[p][1]]+1)
using namespace std;
int n,m,q,queue[MAXN],F[MAXN],sum[MAXN];
int value[MAXN],size[MAXN],father[MAXN],son[MAXN][2];
int Get(int p)
{
    if(F[p]==0)  return p;
    F[p]=Get(F[p]);
    return F[p];
}
void Rotate(int p,int x)
{
    int mark=p==son[x][1],y=son[p][mark^1],z=father[x];
    if(y!=0)  father[y]=x;
    if(x==son[z][0])  son[z][0]=p;
    if(x==son[z][1])  son[z][1]=p;
    son[p][mark^1]=x,father[p]=z,son[x][mark]=y,father[x]=p,update(x);
}
void Splay(int p)
{
    while(father[p])
    {
        int x=father[p],y=father[x];
        if(y==0)  Rotate(p,x);
        else if((p==son[x][0])^(x==son[y][0]))  Rotate(p,x),Rotate(p,y);
        else Rotate(x,y),Rotate(p,x);
    }
    update(p);
}
void Insert(int p,int root)
{
    for(int i=root;;i=son[i][value[p]>value[i]])
        if(son[i][value[p]>value[i]]==0)
        {
            son[i][value[p]>value[i]]=p,father[p]=i,Splay(p);
            return ;
        }
}
void merge(int x,int y)
{
    if(x==y)  return ;
    x=Get(x),y=Get(y);
    if(x==y)  return ;
    if(sum[x]>sum[y])  swap(x,y);
    F[x]=y,sum[y]+=sum[x];
    Splay(x),Splay(y);
    int front=0,rear=1,p;
    if(size[x]>size[y])  swap(x,y);
    queue[rear]=x,queue[front]=y;
    while(front<rear)
    {
        p=queue[++front];
        if(son[p][0])  queue[++rear]=son[p][0];
        if(son[p][1])  queue[++rear]=son[p][1];
        Insert(p,queue[front-1]);
    }
}
int Find(int p,int rank)
{
    Splay(p);
    if(size[p]<rank)  return -1;
    while(size[son[p][0]]+1!=rank)
    {
        if(size[son[p][0]]+1>rank)  p=son[p][0];
        else rank=rank-size[son[p][0]]-1,p=son[p][1];
    }
    Splay(p);
    return p;
}
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void ReadTask(char &p){  for(p=getchar();p!='B'&&p!='Q';p=getchar());  }
void read()
{
    Read(n),Read(m);
    for(int i=1;i<=n;i++)
    {
        Read(value[i]);
        sum[i]=size[i]=1;
    }
    for(int i=1,a,b;i<=m;i++)
    {
        Read(a),Read(b);
        merge(a,b);
    }
}
void Ask()
{
    Read(q);
    char task;
    for(int i=1,a,b;i<=q;i++)
    {
        ReadTask(task),Read(a),Read(b);
        if(task=='B')  merge(a,b);
        if(task=='Q'printf("%d\n",Find(a,b));
    }
}
int main()
{
    read();
    Ask();
    return 0;
}


  评论这张
 
阅读(1413)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017