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.
又写了一个版本的,还是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.