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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

可并堆模板  

2014-06-27 13:49:23|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
bzoj2333真是可并堆的恶心题;
下面贴下模板,插入+删除;合并两个堆,删除某个节点。data再此题中可用编号代替
#include<cstdio>
#include<algorithm>
#define nn 300005
using namespace std;
struct node{int key,l,r,fa,add;}heap[2][nn];
char s[4];
int i,q,n,m,root,add;
void down(int x)
 {int ok=heap[0][x].add;
 heap[0][heap[0][x].l].key+=ok;
 heap[0][heap[0][x].r].key+=ok;
 heap[0][heap[0][x].l].add+=ok;
 heap[0][heap[0][x].r].add+=ok;
 heap[0][x].add=0;
 }
int fa(int w)
{int tem=w;
 while (heap[0][tem].fa)tem=heap[0][tem].fa;
 return tem;
}
void news(int flag,int x,int v)
 {heap[flag][x].key=v;
  heap[flag][x].fa=heap[flag][x].l=heap[flag][x].r=0;
 }
int sum(int x){
  int tem=x,sum=0;
  while (tem=heap[0][tem].fa)sum+=heap[0][tem].add;
  return sum;
}
int merge(int flag,int x,int y)
 {
 if ((!x)||(!y))return (x)?x:y;
 if (heap[flag][x].key<heap[flag][y].key)swap(x,y);
 if (!flag)down(x);
 heap[flag][x].r=merge(flag,heap[flag][x].r,y);
 heap[flag][heap[flag][x].r].fa=x;
 swap(heap[flag][x].l,heap[flag][x].r);
 return x;
 }
int del0(int x)
 {down(x);
  int y=merge(0,heap[0][x].l,heap[0][x].r);
  if (x==heap[0][heap[0][x].fa].l)heap[0][heap[0][x].fa].l=y;
  else heap[0][heap[0][x].fa].r=y;
  heap[0][y].fa=heap[0][x].fa;
  return fa(y);
 }
void del1(int x)
 {
 int y=merge(1,heap[1][x].l,heap[1][x].r);
 if (x==root)root=y;
 if (x==heap[1][heap[1][x].fa].l)heap[1][heap[1][x].fa].l=y;
  else heap[1][heap[1][x].fa].r=y;
 heap[1][y].fa=heap[1][x].fa;
 }
void init()
 {int z;
 if (n>=2)z=merge(1,1,2);
  for (i=3;i<=n;i++)z=merge(1,z,i);
  root=z;
 }
void U()
 {int x,y;scanf("%d%d",&x,&y);
 int fx=fa(x);int fy=fa(y);
 if (fx!=fy)if (merge(0,fx,fy)==fx)
     del1(fy);else del1(fx);
 }
void A1()          
 {int x,v;scanf("%d%d",&x,&v);
  del1(fa(x));int y=del0(x);
  news(0,x,heap[0][x].key+v+sum(x));
  int z=merge(0,y,x);
  news(1,z,heap[0][z].key);
  root=merge(1,root,z);
 }
void A2()
 {int x,v,y;scanf("%d%d%d",&x,&v);
  del1(y=fa(x));
  heap[0][y].key+=v;
  heap[0][y].add+=v;
  news(1,y,heap[0][y].key);
  root=merge(1,root,y);
 }
void A3(){int v;scanf("%d",&v);add+=v;}
void F1(){
int x;scanf("%d",&x);
 printf("%d\n",heap[0][x].key+sum(x)+add);
}
void F2(){
int x;scanf("%d",&x);
 printf("%d\n",heap[0][fa(x)].key+add);
}
void F3(){printf("%d\n",heap[1][root].key+add);}
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++)
 scanf("%d",&heap[0][i].key),heap[1][i].key=heap[0][i].key;
init();
scanf("%d",&q);
for (i=1;i<=q;i++)
       {
       scanf("%s",s);
       if (s[0]=='U')U();
       else if (s[0]=='A')
             {
        if (s[1]=='1')A1();
        if (s[1]=='2')A2();
        if (s[1]=='3')A3();
             }
         else {
        if (s[1]=='1')F1();
        if (s[1]=='2')F2();
        if (s[1]=='3')F3(); 
              }
       }
return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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