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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

splay模板(bzoj1862)  

2014-06-28 12:04:38|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
此题做为splay的模板
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#define nn 251000
using namespace std;
map<string,int>M;
int i,x,y,j,n,m,root,fa[nn],data[nn],ch[nn][2],size[nn];
string s,name[nn];
char cc,c;
int min(int a,int b){return (a>b)?b:a;}
void news(int w,int far)
 {fa[w]=far;ch[w][0]=ch[w][1]=-1;size[w]=1;}
void xz(int x,int f)
 {int y=fa[x];int z=fa[y];
  ch[y][1-f]=ch[x][f];if (ch[x][f]!=-1)fa[ch[x][f]]=y;
  fa[x]=z;if (z!=-1)if (ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;
  fa[y]=x;ch[x][f]=y;
  size[y]=size[ch[y][0]]+size[ch[y][1]]+1;
  size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
 }
void splay(int x,int u)
 {while (fa[x]!=u){int y=fa[x];int z=fa[y];
                  if (z==u){xz(x,ch[y][0]==x);break;}
                  if (ch[z][0]==y){
                   if (ch[y][0]==x){xz(y,1);xz(x,1);}
                   else {xz(x,0);xz(x,1);}
                                  }
                              else{
                   if (ch[y][1]==x){xz(y,0);xz(x,0);}
                   else {xz(x,1);xz(x,0);}
                                  
                  }
 if (u==-1)root=x;
 }
void del(int w)
 {splay(w,-1);if (ch[w][0]==-1&&ch[w][1]==-1){root=-1;return;}
  if (ch[w][0]==-1){root=ch[w][1];fa[root]=-1;return;}
  if (ch[w][1]==-1){root=ch[w][0];fa[root]=-1;return;}
  int j=ch[w][0];
  while (ch[j][1]!=-1)j=ch[j][1];fa[ch[w][0]]=-1;splay(j,-1);ch[j][1]=ch[w][1];
  fa[ch[w][1]]=j;root=j;
 }
void insert(int w)
 {if (root==-1){news(w,-1);root=w;return;}
  int now=root;
  while (1) {size[now]++;
        if (data[w]<=data[now]){
              if (ch[now][1]==-1){ch[now][1]=w;news(w,now);return;}
              else now=ch[now][1];
                                   }
                               else{
              if (ch[now][0]==-1){ch[now][0]=w;news(w,now);return;}
              else now=ch[now][0];
                                   }
            }
 }
int find(int w,int s)
 {int z=(ch[w][0]==-1)?0:size[ch[w][0]];
  if (s==z+1)return w;
  if (s>z)return find(ch[w][1],s-z-1);
  else return find(ch[w][0],s);
 }
void dg(int w)
 {int i;
 if (ch[w][0]!=-1)dg(ch[w][0]);
 printf(" ");for (i=0;i<name[w].length();i++)printf("%c",name[w][i]);
 if (ch[w][1]!=-1)dg(ch[w][1]);
 }
void write(int x,int y)
 {int i;
 splay(y,-1);if (x!=y)splay(x,y);
 for (i=0;i<name[x].length();i++)printf("%c",name[x][i]);
 if (y!=x){
 if (ch[x][1]!=-1)dg(ch[x][1]);printf(" ");
 for (i=0;i<name[y].length();i++)printf("%c",name[y][i]);
          }
  printf("\n");
  }
  评论这张
 
阅读(24999)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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