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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Spoj】【树链剖分】【Gss7】  

2014-03-02 15:52:47|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   下午写bzoj1038有点晕...所以写道spoj的题目吧...
   gss7,首先连续修改线段树可做无压力,然后麻烦的东西就是这个最大连续和....所以普通的那种往上爬的做法就不行了,但是咱们也不是没有办法....对于其中一边我们用栈存着它每一次到达新链所在的节点,然后我们先求出另一个点到最近公共祖先的最大连续子段和,剩余的部分我们弹栈倒着来做。
  然后就可以了。
*********下面是第二天的总结...(实际上第一天因为看错了题目所以没去写)***************
  这里犯了一个傻×的错误...我们定义的线段树中,左边的深度较小,所以我们是从深度小的到深度大的询问,可是这个公共祖先的路径是先深度减小,再深度增大,最大连续子序列和在深度减小的时候应该是从左往右的,到达公共祖先之后的另一边的线段树就应该是从右往左了....所以在其中一边取的是rmax,另一边就应该是 lmax。而且询问的时候递归顺序也应该是一个先递归左边一个先递归右边。调试了半天才发现了这个错误。
  接下来又发现....maintain函数写错了...
    maxx:=max(t[l].maxx,t[r].maxx);
    maxx:=max(maxx,t[l].rmax+t[r].lmax)
    maxx:=max(lmax,rmax)
   最后一个更新成功地把前面计算的给丢了.....
  然后就是无限RE了时候,对拍了半个小时,突然想起来,会不会是线段树数组开小了?一口气开了400000 然后就AC了....
  300+代码加咱这蒟蒻的调试时间和能力.....这题可以训练出一颗多么强大的心灵呵....
   咱真的就是一个大傻叉。
  另外默哀BZOJ又一次成功地牺牲...
  附一组数据以造福后人....
    20
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15 -16 17 -18 19 -20
1 2
6 1
5 1
15 5
1 3
3 4
4 14
14 20
4 13
13 19
2 7
10 7
2 8
8 11
8 9
17 9
16 9
12 11
18 11
20
1 18 19
1 15 16
2 16 18 -1
2 12 12 10
1 12 19
1 12 9
2 7 2 -5
2 10 10 11
1 10 3
1 18 20
2 15 19 -10
2 3 2 100
2 8 18 -13
1 12 10
1 10  20
1 19 6
1 17 5
2 6 14 -10
1 6 20
1 2 15
output:
33
21
38
10
11
4
106
306
200
203
0
100

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

program spojgss7;
const maxn=100010;
type
edge=record
v,pre:longint;
end;

node=record
new,l,r,a,b:longint;
lmax,rmax,maxx,sum:int64;
end;

var e:array[0..maxn shl 1]of edge;
t:array[0..maxn shl 2]of node;
last,dep,son,size,f,id,top,root,seg,d,st:array[0..maxn]of longint;
ln,up,n,m:longint;
tot,ans:int64;

procedure addedge(u,v:longint);
begin
inc(tot);
e[tot].v:=v;
e[tot].pre:=last[u];
last[u]:=tot;
inc(tot);
e[tot].v:=u;
e[tot].pre:=last[v];
last[v]:=tot;
end;

function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;

procedure maintain(x:longint);
begin
with t[x] do
begin
sum:=t[l].sum+t[r].sum;
lmax:=max(t[l].lmax,t[l].sum+t[r].lmax);
rmax:=max(t[r].rmax,t[r].sum+t[l].rmax);
maxx:=max(t[l].maxx,t[r].maxx);
maxx:=max(maxx,t[l].rmax+t[r].lmax);
maxx:=max(maxx,lmax);
maxx:=max(maxx,rmax);
end;
end;

procedure release(x:longint);
begin
with t[x] do
begin
if new=maxn then exit;
t[l].new:=new;
t[l].sum:=(t[l].b-t[l].a)*new;
if new>0 then
begin
t[l].maxx:=t[l].sum;
t[l].lmax:=t[l].sum;
t[l].rmax:=t[l].sum;
end
else
begin
t[l].maxx:=new;
t[l].lmax:=new;
t[l].rmax:=new;
end;
t[r].new:=new;
t[r].sum:=(t[r].b-t[r].a)*new;
if new>0 then
begin
t[r].maxx:=t[r].sum;
t[r].lmax:=t[r].sum;
t[r].rmax:=t[r].sum;
end
else
begin
t[r].maxx:=new;
t[r].lmax:=new;
t[r].rmax:=new;
end;
new:=maxn;
end;
end;

procedure build(l,r:longint);
var mid,now:longint;
begin
inc(tot);
now:=tot;
t[now].a:=l;t[now].b:=r;
t[now].new:=maxn;
if l+1<r then
begin
mid:=(l+r)shr 1;
t[now].l:=tot+1;build(l,mid);
t[now].r:=tot+1;build(mid,r);
maintain(now);
end
else
begin
t[now].sum:=seg[r];
t[now].maxx:=seg[r];
t[now].lmax:=seg[r];
t[now].rmax:=seg[r];
end;
end;

procedure insert(l,r,x,w:longint);
var mid:longint;
begin
if (t[x].a>=l)and(t[x].b<=r)then
begin
t[x].new:=w;
t[x].sum:=(t[x].b-t[x].a)*w;
if w>0 then t[x].maxx:=t[x].sum
else t[x].maxx:=w;
t[x].lmax:=t[x].maxx;
t[x].rmax:=t[x].maxx;
exit;
end;
release(x);
mid:=(t[x].a+t[x].b)shr 1;
if mid>l then insert(l,r,t[x].l,w);
if mid<r then insert(l,r,t[x].r,w);
maintain(x);
end;

procedure query(l,r,x,w:longint);
var mid:longint;
begin
if (t[x].a>=l)and(t[x].b<=r)then
if w=0 then
begin
if tot<0 then tot:=0;
ans:=max(ans,t[x].maxx);
ans:=max(ans,tot+t[x].lmax);
tot:=max(tot+t[x].sum,t[x].rmax);
ans:=max(ans,tot);
exit;
end
else
begin
if tot<0 then tot:=0;
ans:=max(ans,t[x].maxx);
ans:=max(ans,tot+t[x].rmax);
tot:=max(tot+t[x].sum,t[x].lmax);
ans:=max(ans,tot);
exit;
end;
release(x);
mid:=(t[x].a+t[x].b)shr 1;
if w=0 then
begin
if mid>l then query(l,r,t[x].l,w);
if mid<r then query(l,r,t[x].r,w);
end
else
begin
if mid<r then query(l,r,t[x].r,w);
if mid>l then query(l,r,t[x].l,w);
end;
maintain(x);
end;

procedure dfs1(x:longint);
var tmp:longint;
begin
tmp:=last[x];
size[x]:=1;
while tmp<>0 do
begin
if e[tmp].v<>f[x] then
begin
f[e[tmp].v]:=x;
dep[e[tmp].v]:=dep[x]+1;
dfs1(e[tmp].v);
size[x]:=size[x]+size[e[tmp].v];
if size[son[x]]<size[e[tmp].v] then son[x]:=e[tmp].v;
end;
tmp:=e[tmp].pre;
end;
end;

procedure dfs2(x,u:longint);
var tmp:longint;
begin
id[x]:=ln+1;
seg[dep[x]]:=d[x];
if son[x]=0 then
begin
inc(ln);
top[ln]:=u;
root[ln]:=tot+1;
build(dep[u]-1,dep[x]);
end
else dfs2(son[x],u);
tmp:=last[x];
while tmp<>0 do
begin
if id[e[tmp].v]=0 then
dfs2(e[tmp].v,e[tmp].v);
tmp:=e[tmp].pre;
end;
end;

procedure modify(u,v,w:longint);
var t:longint;
begin
while id[u]<>id[v] do
begin
if id[u]<id[v] then
begin
t:=u;u:=v;v:=t;
end;
insert(dep[top[id[u]]]-1,dep[u],root[id[u]],w);
u:=f[top[id[u]]];
end;
if dep[u]>dep[v] then
begin
t:=u;u:=v;v:=t;
end;
insert(dep[u]-1,dep[v],root[id[u]],w);
end;

procedure ask(u,v:longint);
var tt,i:longint;
change:boolean;
begin
ans:=0;tot:=0;up:=0;
change:=false;
while id[u]<>id[v] do
begin
if id[u]<id[v] then
begin
tt:=u;u:=v;v:=tt;
change:=not change;
end;
if change then
begin
inc(up);
st[up]:=u;
u:=f[top[id[u]]];
end
else
begin
query(dep[top[id[u]]]-1,dep[u],root[id[u]],1);
u:=f[top[id[u]]];
end;
end;
if change then
begin
tt:=u;u:=v;v:=tt;
end;
if dep[u]>dep[v] then query(dep[v]-1,dep[u],root[id[u]],1)
else query(dep[u]-1,dep[v],root[id[u]],0);
for i:=up downto 1 do
begin
v:=st[i];
u:=top[id[v]];
query(dep[u]-1,dep[v],root[id[u]],0);
end;
end;

procedure init;
var i,u,v,w,ch:longint;
begin
read(n);
for i:=1 to n do read(d[i]);
tot:=0;
fillchar(last,sizeof(last),0);
for i:=1 to n-1 do
begin
read(u,v);
addedge(u,v);
end;
tot:=0;ln:=0;
fillchar(dep,sizeof(dep),0);
fillchar(top,sizeof(top),0);
fillchar(son,sizeof(son),0);
fillchar(size,sizeof(size),0);
fillchar(f,sizeof(f),0);
fillchar(id,sizeof(id),0);
dep[1]:=1;
dfs1(1);
dfs2(1,1);
read(m);
for i:=1 to m do
begin
read(ch);
case ch of
1:begin
read(u,v);
ask(u,v);
writeln(ans);
end;
2:begin
read(u,v,w);
modify(u,v,w);
end;
end;
end;
end;

begin
init;
end.

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

历史上的今天

评论

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

页脚

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