vijos 1083小白线段树

返回结构体。。。。你妈炸了

  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 begin
101  readln(n,m);
102  build(1,1,n);
103  for i:=1 to m do
104  begin
105   readln(k,ll,rr);
106   if k=1 then
107   begin
108    if ll>rr then
109    begin
110     j:=ll;
111     ll:=rr;
112     rr:=j;
113    end;
114    writeln(find(1,ll,rr).h);
115   end
116   else
117   begin
118    b[ll]:=rr;
119    ll:=num(1,ll);
120    maintain(ll,rr);
121   end;
122  end;
123 end.

View Code

P1083小白逛公园

Accepted

标签：[显示标签]

描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着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的整数。

输出格式

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。