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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1878】【SDOI2009】【HH的项链】  

2014-05-03 16:21:50|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    TAT 已经堕落的z君...
    题目大意:给出一个数列,询问区间数的种类数。

    现在应该是很水了,本来离线各种秒的= =,所以想做一做在线的,然后就用了可持久化线段树。做法比较简单,咱们只统计这个区间里面每一个颜色第一次出现的位置即可,怎么做到呢?咱们给每一个位置记录一个pre[]表示上一个和这个位置的数相同的位置在哪里,那么咱们询问[l,r]中的颜色的个数,实际上就是[l,r]内部的pre[]<l的数的个数,然后这个嘛...考虑只一次询问的简单做法,首先咱们对于pre[]可以建立一棵权值线段树,然后咱们把[l,r]的pre[]插入到这一棵权值线段树里面,然后询问[1,l-1]的部分的个数即可。然后显然对于多组询问,咱们可以用可持久化线段树做,咱们用r时刻的权值线段树减去l-1时刻的权值线段树,就是l,r的权值线段树。然后直接查询[1,l-1]的权值和即可。

      写完了连WA三发= =然后不知道为什么额...然后上午就废在这道题上面了【貌似昨天被一道题卡了一天233】,然后最后到中午的时候就去补完 即将出第二季的 无头骑士【绝对神作!!】 和泡面番 黑白小姐....然后下午又没睡觉躺在长椅上困到3,4点...0.0然后发现他们的APIO貌似考完了饿...0.0然后突然醒来之后,一拍脑袋想咱该不会是空间开的O(n*4),然后可持久化线段树还忘了开一个Logn吧...一交果然是的233333,连戳某z自己三巴掌= = 
   
=====================

program bzoj1878;
const maxn=1000010;
      maxm=50010;
type node=record
     l,r,a,b,sum:longint;
     end;

var a,root:array[0..maxm]of longint;
    t:array[0..maxm shl 2*15]of node;
    last:array[0..maxn]of longint;
    n,m,tot:longint;

procedure new(x:longint);
var mid:longint;
begin
  mid:=(t[x].a+t[x].b)shr 1;
  inc(tot);t[tot].a:=t[x].a;t[tot].b:=mid;
  t[tot].sum:=0;t[tot].l:=0;t[tot].r:=0;
  t[x].l:=tot;
  inc(tot);t[tot].a:=mid;t[tot].b:=t[x].b;
  t[tot].sum:=0;t[tot].l:=0;t[tot].r:=0;
  t[x].r:=tot;
end;

procedure maintain(l,r,x:longint);
begin
  inc(tot);t[tot].l:=l;t[tot].r:=r;
  t[tot].a:=t[x].a;t[tot].b:=t[x].b;
  t[tot].sum:=t[x].sum+1;
end;

function insert(c,x:longint):longint;
var mid,ne:longint;
begin
  if (t[x].a=c-1)and(t[x].b=c)then
   begin
     inc(tot);t[tot].l:=0;t[tot].r:=0;
     t[tot].a:=t[x].a;t[tot].b:=t[x].b;
     t[tot].sum:=t[x].sum+1;
     exit(tot);
   end;
  if t[x].l=0 then new(x);
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>c-1 then
   begin
     ne:=insert(c,t[x].l);
     maintain(ne,t[x].r,x);
   end;
  if mid<c then
   begin
     ne:=insert(c,t[x].r);
     maintain(t[x].l,ne,x);
   end;
  exit(tot);
end;

function query(l,r,c:longint):longint;
var mid:longint;
    ans:longint;
begin
  if (t[l].a>=-1)and(t[l].b<=c)then exit(t[r].sum-t[l].sum);
  mid:=(t[l].a+t[l].b)shr 1;
  if t[l].l=0 then new(l);
  if t[r].l=0 then new(r);
  ans:=0;
  if mid>-1 then ans:=ans+query(t[l].l,t[r].l,c);
  if mid<c then ans:=ans+query(t[l].r,t[r].r,c);
  exit(ans);
end;

procedure init;
var i,u,v:longint;
begin
  read(n);
  fillchar(root,sizeof(root),0);
  fillchar(last,sizeof(last),0);
  tot:=0;
  t[0].a:=-1;t[0].b:=n;
  for i:=1 to n do
   begin
     read(a[i]);
     root[i]:=insert(last[a[i]],root[i-1]);
     last[a[i]]:=i;
   end;
  read(m);
  for i:=1 to m do
   begin
     read(u,v);
     writeln(query(root[u-1],root[v],u-1));
   end;
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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