讨论 / FP不要用线段树
S.C.Q. 2013-05-14 01:20:00
点我顶贴 收藏 删除
各种优化,包括读入优化、判断大小优化都用了,结果是50分,4组超时,1组WA。我十分好奇能让我WA的那组数据。其中sl,sr是左右子树。

program rqnoj626;

const

maxn=500000+10;inf=500000000+10;

type

treenode=record

l,r,sl,sr,lmax,rmax,mmax,sum:longint;

end;

var

root,pos:longint;

n,m:longint;

c,a,b:longint;

tree:array[0..2*maxn] of treenode;

procedure buildtree(var node:longint;a,b:longint);

var

mid:longint;

begin

node:=pos;

inc(pos);

tree[node].l:=a;tree[node].r:=b;

if a=b then

begin

read(tree[node].sum);

tree[node].lmax:=tree[node].sum;

tree[node].rmax:=tree[node].sum;

tree[node].mmax:=tree[node].sum;

exit;

end;

mid:=(a+b)>>1;

buildtree(tree[node].sl,a,mid);

buildtree(tree[node].sr,mid+1,b);

tree[node].sum:=tree[tree[node].sl].sum+tree[tree[node].sr].sum;

if tree[tree[node].sl].lmax>tree[tree[node].sl].sum+tree[tree[node].sr].lmax then

tree[node].lmax:=tree[tree[node].sl].lmax

else tree[node].lmax:=tree[tree[node].sl].sum+tree[tree[node].sr].lmax;

if tree[tree[node].sr].rmax>tree[tree[node].sr].sum+tree[tree[node].sl].rmax then

tree[node].rmax:=tree[tree[node].sr].rmax

else tree[node].rmax:=tree[tree[node].sr].sum+tree[tree[node].sl].rmax;

if tree[tree[node].sl].mmax>tree[tree[node].sr].mmax then

tree[node].mmax:=tree[tree[node].sl].mmax

else tree[node].mmax:=tree[tree[node].sr].mmax;

if tree[node].mmax<tree[tree[node].sl].rmax+tree[tree[node].sr].lmax then

tree[node].mmax:=tree[tree[node].sl].rmax+tree[tree[node].sr].lmax;

end;

function find(node:longint):treenode;

var

mid:longint;

tsl,tsr:treenode;

f1,f2:boolean;

begin

if (a<=tree[node].l)and(b>=tree[node].r) then

exit(tree[node]);

mid:=(tree[node].l+tree[node].r)>>1;

tsl.mmax:=-inf;tsr.mmax:=-inf;

tsl.sum:=-inf;tsr.sum:=-inf;

tsl.lmax:=-inf;tsr.lmax:=-inf;

tsl.rmax:=-inf;tsr.rmax:=-inf;

find.sum:=0;

f1:=false;f2:=false;

if a<=mid then

begin

tsl:=find(tree[node].sl);

inc(find.sum,tsl.sum);

f1:=true;

end;

if b>mid then

begin

tsr:=find(tree[node].sr);

inc(find.sum,tsr.sum);

f2:=true;

end;

if tsl.mmax>tsr.mmax then find.mmax:=tsl.mmax

else find.mmax:=tsr.mmax;

if tsl.rmax+tsr.lmax>find.mmax then find.mmax:=tsl.rmax+tsr.lmax;

if tsl.lmax>tsl.sum+tsr.lmax then find.lmax:=tsl.lmax

else find.lmax:=tsl.sum+tsr.lmax;

if not f1 then

if find.lmax<tsr.lmax then find.lmax:=tsr.lmax;

if tsr.rmax>tsr.sum+tsl.rmax then find.rmax:=tsr.rmax

else find.rmax:=tsr.sum+tsl.rmax;

if not f2 then

if find.rmax<tsl.rmax then find.rmax:=tsl.rmax;

end;

procedure renew(node:longint);

var

mid:longint;

begin

if(tree[node].l=tree[node].r) then

begin

tree[node].sum:=b;

tree[node].mmax:=b;

tree[node].lmax:=b;

tree[node].rmax:=b;

exit;

end;

mid:=(tree[node].l+tree[node].r)>>1;

if a<=mid then renew(tree[node].sl);

if a>mid then renew(tree[node].sr);

tree[node].sum:=tree[tree[node].sl].sum+tree[tree[node].sr].sum;

if tree[tree[node].sl].lmax>tree[tree[node].sl].sum+tree[tree[node].sr].lmax then

tree[node].lmax:=tree[tree[node].sl].lmax

else tree[node].lmax:=tree[tree[node].sl].sum+tree[tree[node].sr].lmax;

if tree[tree[node].sr].rmax>tree[tree[node].sr].sum+tree[tree[node].sl].rmax then

tree[node].rmax:=tree[tree[node].sr].rmax

else tree[node].rmax:=tree[tree[node].sr].sum+tree[tree[node].sl].rmax;

if tree[tree[node].sl].mmax>tree[tree[node].sr].mmax then

tree[node].mmax:=tree[tree[node].sl].mmax

else tree[node].mmax:=tree[tree[node].sr].mmax;

if tree[node].mmax<tree[tree[node].sl].rmax+tree[tree[node].sr].lmax then

tree[node].mmax:=tree[tree[node].sl].rmax+tree[tree[node].sr].lmax;

end;

procedure work;

var

i:longint;

begin

read(n,m);

root:=1;pos:=1;

buildtree(root,1,n);

for i:=1 to m do

begin

read(c);

if c=1 then

begin

read(a,b);

if a>b then

begin

a:=a xor b;

b:=a xor b;

a:=a xor b;

end;

writeln(find(1).mmax);

end else

begin

read(a,b);

renew(1);

end;

end;

end;

begin

work;

end.

#1 S.C.Q.@2013-05-14 01:20:00
回复 删除
不用判断大小的优化结果和用了的差不多,实际上用了会比不用快一倍。

又写了一个版本的,还是A 5组 T 4组 WA 1组

program rqnoj626;

const

maxn=500000+10;inf=800000000+10;

type

treenode=record

l,r,lmax,rmax,mmax,sum:longint;

end;

var

n,m:longint;

t,a,b:longint;

tree:array[0..3*maxn] of treenode;

function max(a,b,c:longint):longint;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

end;

procedure pup(node:longint);

begin

tree[node].sum:=tree[node<<1].sum+tree[node<<1+1].sum;

tree[node].lmax:=tree[node<<1].lmax;

if tree[node].lmax<tree[node<<1].sum+tree[node<<1+1].lmax then

tree[node].lmax:=tree[node<<1].sum+tree[node<<1+1].lmax;

tree[node].rmax:=tree[node<<1+1].rmax;

if tree[node].rmax<tree[node<<1+1].sum+tree[node<<1].rmax then

tree[node].rmax:=tree[node<<1+1].sum+tree[node<<1].rmax;

tree[node].mmax:=

max(tree[node<<1].mmax,tree[node<<1+1].mmax,tree[node<<1].rmax+tree

[node<<1+1].lmax);

end;

procedure buildtree(node,a,b:longint);

var

mid:longint;

begin

tree[node].l:=a;tree[node].r:=b;

if a=b then

begin

read(tree[node].sum);

tree[node].mmax:=tree[node].sum;

tree[node].lmax:=tree[node].sum;

tree[node].rmax:=tree[node].sum;

exit;

end;

mid:=(a+b)>>1;

buildtree(node<<1,a,mid);

buildtree(node<<1+1,mid+1,b);

pup(node);

end;

function find(node:longint):treenode;

var

mid:longint;

t1,t2:treenode;

begin

if (a<=tree[node].l)and(b>=tree[node].r) then exit(tree[node]);

mid:=(tree[node].l+tree[node].r)>>1;

t1.sum:=-inf;t2.sum:=-inf;

t1.mmax:=-inf;t2.mmax:=-inf;

t1.lmax:=-inf;t2.lmax:=-inf;

t1.rmax:=-inf;t2.rmax:=-inf;

find.sum:=0;

if a<=mid then

begin

t1:=find(node<<1);

inc(find.sum,t1.sum);

end;

if b>mid then

begin

t2:=find(node<<1+1);

inc(find.sum,t2.sum);

end;

find.lmax:=t1.lmax;

if find.lmax<t1.sum+t2.lmax then find.lmax:=t1.sum+t2.lmax;

find.rmax:=t2.rmax;

if find.rmax<t2.sum+t1.rmax then find.rmax:=t2.sum+t1.rmax;

find.mmax:=max(t1.mmax,t2.mmax,t1.rmax+t2.lmax);

end;

procedure renew(node:longint);

var

mid:longint;

begin

if (tree[node].l=tree[node].r) then

begin

tree[node].sum:=b;tree[node].mmax:=b;

tree[node].lmax:=b;tree[node].rmax:=b;

exit;

end;

mid:=(tree[node].l+tree[node].r)>>1;

if a<=mid then renew(node<<1);

if a>mid then renew(node<<1+1);

pup(node);

end;

procedure work;

var

i,x:longint;

begin

read(n,m);

buildtree(1,1,n);

for i:=1 to m do

begin

read(x,a,b);

if x=1 then

begin

if a>b then

begin

t:=a;a:=b;b:=t;

end;

writeln(find(1).mmax);

end;

if x=2 then renew(1);

end;

end;

begin

work;

end.

查看更多回复
提交回复