温存's Blog

procedure maintain(o, l, r:integer);   //维护节点o，对应区间[l,r]
var
  lc,rc:integer;
begin
  lc := o*2;
  rc := o*2+1;
  sumv[o] := 0;
  minv[o] := 0;
  maxv[o] := 0;
  if (l<r) then                         //如果o有孩子
  begin
    sumv[o] := sumv[lc]+sumv[rc];      
    minv[o] := min(minv[lc], minv[rc]);
    maxv[o] := max(maxv[lc], maxv[rc]);
  end;
  inc(minv[o], addv[o]);                //加上lazy tag
  inc(maxv[o], addv[o]);
  inc(sumv[o], addv[o]*(r-l+1));
end;

procedure update(o, l, r:integer);
var
  lc,rc,m:integer;
begin
  lc:=o*2;
  rc:=o*2+1;
  if ((y1<=l)and(y2>=r))then //限定范围
    inc(addv[o], v)          //lazy tag 标志
  else
  begin
    m:=l+ (r-l) div 2;      //(l+r)>>1，防止溢出
    if (y1<=m) then
      update(lc,l,m);
    if (y2>m) then
      update(rc,m+1,r);     //如果所求仍然在o的子树里，则下去查找
  end;
  maintain(o,l,r);         //递归完成后是从最后一个节点往前的，故可以实现
end;

var
  min_, max_, sum_:integer;  //答案
procedure query(o,l,r,add:integer); //add表示当前所有祖先的add和
var
  m:integer;                     
begin
  if (y1<=l)and(y2>=r)then
  begin
    inc(sum_,sumv[o]+add*(r-l+1)); 
    min_:=min(min_, minv[o]+add);
    max_:=max(max_, maxv[o]+add);
  end
  else
  begin
    m:=l+(r-l)div 2;      //数据不流氓，用(L+R)Div 2 或 (L+R)>>1 或 (L+R) shr 1 也可以
    if y1<=m then query(o*2, l, m, add+addv[o]);
    if y2>m then query(o*2+1, m+1, r, add+addv[o]);
  end;
end;