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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1483】【Hnoi2009】【梦幻布丁】  

2014-04-24 15:08:20|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:一个数列,两个操作:
    A.将所有的x变成y
    B.询问有多少段数【相同的数算一段】
    数列长度<=10^5,询问个数<=10^5

    0.0咱们可以把每一个数块给用链表记录下来,然后每一次修改的时候就可以遍历链表,看能否和周围的合并,如果能的话就可以合并,否则不合并。由于数块每合并一次都最少减少一个数块,所以最多只能合并O(n)次。

    本来想法是这样的...但是= =乃不能保证每一次找到的都是能合并的数块,如果要遍历的话,咱们可以设计一种相间的和永远不能合并的操作,那么复杂度就是O(NM)了...所以这个复杂度是承受不来的额。

    想想咱的思想止步在哪里了?为什么非得每一次都遍历一次?直接把两个数块链表合并一下就可以了嘛...然后这里就是将其中一个链表的所有数块丢到另一个里面,如果某一个和另一个数块的一些元素又重合就可以合并。然后这个的复杂度首先丢入是按照顺序的,所以复杂度均摊是O(1)的,然后合并也是均摊O(1)的,但是总的复杂度还是O(NM),这里启示了咱们...实际上这个合并可以使用启发式合并...0.0也就是说两个链表合并,将小的链表丢入到大的链表中去,类似平衡树的复杂度证明,对于每一个元素,它们最多被丢入O(logn)次【因为每丢入一次显然所在链表的大小会增加一倍】,然后这个的复杂度就是O(mlogn)的,然后就可以AC这道题了。

   关于模拟链表0.0,咱们只需要实现丢入和删除就可以了.......记录一个L,R构成双向链表然后弄一下即可。
   然后关于丢入额..不同的启发式的话注意要改变的东西是不同的...

   【话说...咱没写启发式合并直接合并就过了23333333333333】

======================

program hnoi2009day1a;
const maxn=600010;
type block=record
     l,r:longint;
     c:int64;
     end;

var l,r,a,size,last,st:array[0..maxn]of longint;
    col:array[0..maxn]of block;
    n,m,tot,ans:longint;

procedure insert(var x:longint;c,w:longint);
var tmp,y:longint;
begin
  col[c].c:=w;
  while (r[x]<>0)and(col[r[x]].l<col[c].l) do x:=r[x];
  l[c]:=x;r[c]:=r[x];l[r[x]]:=c;r[x]:=c;
  while(x<>0)and(col[x].r+1=col[c].l)do
   begin
     l[c]:=l[x];
     r[l[x]]:=c;
     col[c].l:=col[x].l;
     tmp:=l[x];
     l[x]:=0;r[x]:=0;
     x:=tmp;
     dec(size[col[c].c]);
     dec(ans);
   end;
  if x=0 then st[col[c].c]:=c;
  y:=r[c];
  while (y<>0)and(col[y].l=col[c].r+1) do
   begin
     r[c]:=r[y];
     l[r[y]]:=c;
     col[c].r:=col[y].r;
     tmp:=r[y];
     l[y]:=0;r[y]:=0;
     y:=tmp;
     dec(size[col[c].c]);
     dec(ans);
   end;
  if y=0 then last[col[c].c]:=c;
  x:=c;
end;

procedure init;
var i,j,k,u,v,w,tmp:longint;
begin
  read(n,m);
  for i:=1 to n do read(a[i]);
  i:=1;j:=1;tot:=0;
  fillchar(last,sizeof(last),0);
  fillchar(size,sizeof(size),0);
  fillchar(st,sizeof(st),0);
  while i<=n do
   begin
     while (i<n)and(a[i]=a[i+1]) do inc(i);
     inc(tot);
     col[tot].l:=j;
     col[tot].r:=i;
     col[tot].c:=a[i];
     l[tot]:=last[a[i]];
     r[last[a[i]]]:=tot;
     last[a[i]]:=tot;
     if st[a[i]]=0 then st[a[i]]:=tot;
     r[tot]:=0;
     inc(size[a[i]]);
     inc(i);
     j:=i;
   end;
  ans:=tot;
  for i:=1 to m do
   begin
     read(j);
     if j=1 then
      begin
        read(u,v);
        if u=v then continue;
        if st[u]=0 then continue;
        {if size[u]>size[v] then
         begin
           k:=u;u:=v;v:=k;
         end;}
        k:=st[u];
        r[0]:=st[v];
        l[0]:=last[v];
        w:=0;
        while k<>0 do
         begin
           tmp:=r[k];
           insert(w,k,v);
           k:=tmp;
         end;
        st[u]:=0;
        last[u]:=0;
      end
     else
      begin
        writeln(ans);
      end;
   end;
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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