返回结构体。。。。你妈炸了
1 program hehe; 2 type 3 shu=record 4 l,r,h,he,maxr,maxl:longint; 5 end; 6 var 7 n,m,i,j,k,ll,rr:longint; 8 b:array[0..500000] of longint; 9 x:array[0..5000000] of shu; 10 11 function max(a,b:longint):longint; 12 begin 13 if a>b then exit(a); 14 exit(b); 15 end; 16 17 function min(a,b:longint):longint; 18 begin 19 if a>b then exit(b); 20 exit(a); 21 end; 22 23 procedure update(a:longint); 24 begin 25 x[a].he:=x[a<<1].he+x[a<<1+1].he; 26 x[a].h:=max(x[a<<1].h,x[a<<1+1].h); 27 x[a].h:=max(x[a].h,x[a<<1].maxr+x[a<<1+1].maxl); 28 x[a].maxl:=max(x[a<<1].maxl,x[a<<1].he+x[a<<1+1].maxl); 29 x[a].maxr:=max(x[a<<1+1].maxr,x[a<<1+1].he+x[a<<1].maxr); 30 end; 31 32 function num(a,b:longint):longint; 33 var 34 mid:longint; 35 begin 36 if x[a].l=x[a].r then exit(a); 37 mid:=(x[a].l+x[a].r)>>1; 38 if b>mid then exit(num(a<<1+1,b)); 39 exit(num(a<<1,b)) 40 end; 41 42 procedure maintain(a,b:longint); 43 begin 44 if a=1 then exit; 45 if x[a].l=x[a].r then 46 begin 47 x[a].he:=b; 48 x[a].h:=b; 49 x[a].maxr:=b; 50 x[a].maxl:=b; 51 end 52 else update(a); 53 maintain(a>>1,b); 54 end; 55 56 procedure build(a,l,r:longint); 57 var 58 mid:longint; 59 begin 60 x[a].l:=l; 61 x[a].r:=r; 62 if l=r then 63 begin 64 read(x[a].h); 65 x[a].he:=x[a].h; 66 x[a].maxl:=x[a].h; 67 x[a].maxr:=x[a].h; 68 inc(k); 69 b[k]:=x[a].h; 70 exit; 71 end; 72 mid:=(l+r)>>1; 73 build(a<<1,l,mid); 74 build(a<<1+1,mid+1,r); 75 update(a); 76 end; 77 78 function plus(a,b:shu):shu; 79 var 80 t:shu; 81 begin 82 t.maxl:=max(a.maxl,a.he+b.maxl); 83 t.maxr:=max(a.maxr+b.he,b.maxr); 84 t.h:=max(max(a.h,b.h),a.maxr+b.maxl); 85 t.he:=a.he+b.he; 86 exit(t); 87 end; 88 89 function find(a,l,r:longint):shu; 90 var 91 mid,s:longint; 92 begin 93 if (x[a].l=l)and(x[a].r=r) then exit(x[a]); 94 mid:=(x[a].l+x[a].r)>>1; 95 if l>mid then exit(find(a<<1+1,l,r)); 96 if r<=mid then exit(find(a<<1,l,r)); 97 exit(plus(find(a<<1,l,mid),find(a<<1+1,mid+1,r))); 98 end; 99 100 begin101 readln(n,m);102 build(1,1,n);103 for i:=1 to m do104 begin105 readln(k,ll,rr);106 if k=1 then107 begin108 if ll>rr then109 begin110 j:=ll;111 ll:=rr;112 rr:=j;113 end;114 writeln(find(1,ll,rr).h);115 end116 else117 begin118 b[ll]:=rr;119 ll:=num(1,ll);120 maintain(ll,rr);121 end;122 end;123 end.
P1083小白逛公园
描述
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
格式
输入格式
第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N， a可以大于b！）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。
其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。