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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Spoj】【线段树】【GSS4】  

2014-01-22 14:04:04|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   GSS4很多人说木有找到...咱就觉得奇怪了...明明就是SPOJ2713....
   提供两种操作的维护序列,第一种是 对区间 【x,y】的所有数开平方根。第二种是询问【x,y】的和。
   由于被剧透了..所以咱也就知道了这很像一个脑筋急转弯...每一个数依次开方下去最多开6次...(10^18自己数数就知道了...),所以暴力在线段树上修改就可以了,总的复杂度为O((N+M)logN)的...
   本来是这么想当然地想的.....可是在TLE三次加上编译优化啥的之后...痛定思痛...这才发现有的节点是没有必要求的....修改到1之后再继续修改只是浪费时间...对此我们可以用一个布尔数组记录每个数是否被弄到1,被弄到1了的话咱就不向下修改了....
这样子修改的时间就省了一大半,降为O(2NlogN),然后还是TLE.....
   问题在于for i:=ll to rr,这里虽然特判了要不要修改,但是还是要进入循环,所以TLE了....
   所以得保证每一次进入的都是要修改的才可以。
   纠结了半天,晚上再继续来纠结...
========================================================================
program gss4;
var w:array[1..100010]of int64;
    a,b,l,r,last,next,max:array[1..200010]of longint;
    sum:array[1..200010]of int64;
    n,m,tot,t:longint;ans:int64;
procedure maintain(x:longint);
begin
  sum[x]:=sum[l[x]]+sum[r[x]];
  max[x]:=maxx(max[l[x]],max[r[x]]);
end;

procedure build(s,t:longint);
var mid,now:longint;
begin
  inc(tot);now:=tot;
  a[now]:=s;b[now]:=t;
  if s+1<t then begin
    mid:=(s+t)shr 1;
    l[now]:=tot+1;build(s,mid);
    r[now]:=tot+1;build(mid,t);end
  else begin sum[now]:=w[t];exit;end;
  maintain(now);
end;

procedure insert(s,t,x:longint);
var mid:longint;
begin
  if (a[x]>=s)and(b[x]<=t) then begin
    sum[x]:=int(sqrt(sum[x]));
    if sum[x]=1 then f[b[x]]:=true;exit;end;
  mid:=(a[x]+b[x])shr 1;
  if mid>s then insert(s,t,l[x]);
  if mid<t then insert(s,t,r[x]);
  maintain(x);
end;

procedure query(s,t,x:longint);
var mid:longint;
begin
  if (a[x]>=s)and(b[x]<=t)then begin
     inc(ans,sum[x]);exit;end;
  mid:=(a[x]+b[x])shr 1;
  if mid>s then query(s,t,l[x]);
  if mid<t then query(s,t,r[x]);
end;


procedure init;
var i,j,ch,ll,rr:longint;
begin
  inc(t);
  writeln('Case #',t,':');
  readln(n);
  for i:=1 to n do read(w[i]);
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  fillchar(l,sizeof(l),0);
  fillchar(r,sizeof(r),0);
  fillchar(sum,sizeof(sum),0);
  fillchar(last,sizeof(last),0);
  fillchar(next,sizeof(next),0);
  for i:=1 to n do last[i]:=i-1;
  for i:=1 to n do next[i]:=i+1;
  tot:=0;
  build(0,n);
  read(m);
  for i:=1 to m do begin
    readln(ch,ll,rr);
    if ll>rr then begin j:=ll;ll:=rr;rr:=j;end;
    if ch=0 then begin
                 insert(j-1,j,1);
                 end
            else begin
                 ans:=0;query(ll-1,rr,1);
                 writeln(ans);end;end;
  writeln;
end;

begin
  //assign(input,'f.in');reset(input);
  while not seekeof do
   init;
  //close(input);
end.


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

历史上的今天

评论

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

页脚

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