线段树（可能还会有树状数组吧）

看了下gdkoi2014……觉得完蛋了……除了一道莫队还可以写写一眼看出，其他基本不行……

发现学了一大堆东西都不会用……

那就从最基础的线段树还是吧。

都说了只是开坑还没写呢⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

POJ - 1151 Atlantis

妈蛋，都不会写线段树了……这道傻叉题竟然写了一个早上+一个下午&……

以前学的时候就一直搞乱云说的点树和区间树的区别。

都怪自己弱呵呵。

这道题竟然用lazy了……我到底是有多傻逼&（然后看了别人的代码终于醒悟）

type
  arr1=record
    left,right,tot,mark:longint;
    sum:double;
  end;
  arr2=record
    x,y1,y2:double;
    col:longint;
  end;

const
  maxn=300000;

var
  tree:array[0..maxn]of arr1;
  line:array[0..maxn]of arr2;
  hash,long:array[0..maxn]of double;
  num:array[0..maxn]of longint;
  total,n,t:longint;

procedure qsort1(l,r:longint);
var
  i,j:longint;
  mid,tmp:double;
begin
  i:=l;
  j:=r;
  mid:=hash[(l+r)>>1];
  repeat
    while hash[i]<mid do inc(i);
    while hash[j]>mid do dec(j);
    if i<=j then begin
      tmp:=hash[i];
      hash[i]:=hash[j];
      hash[j]:=tmp;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort1(i,r);
  if l<j then qsort1(l,j);
end;

procedure qsort2(l,r:longint);
var
  i,j:longint;
  mid:double;
  tmp:arr2;
begin
  i:=l;
  j:=r;
  mid:=line[(l+r)>>1].x;
  repeat
    while line[i].x<mid do inc(i);
    while line[j].x>mid do dec(j);
    if i<=j then begin
      tmp:=line[i];
      line[i]:=line[j];
      line[j]:=tmp;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort2(i,r);
  if l<j then qsort2(l,j);
end;

function find(x:double):longint;
var
  left,right,mid:longint;
begin
  left:=1;
  right:=total+1;
  while left+1<right do begin
    mid:=(left+right)>>1;
    if long[mid]=x then exit(mid);
    if long[mid]<x then left:=mid
      else right:=mid;
  end;
  exit(left);
end;

procedure build(x,l,r:longint);
var
  mid:longint;
begin
  tree[x].sum:=0;
  tree[x].left:=l;
  tree[x].right:=r;
  tree[x].tot:=0;
  mid:=(l+r)>>1;
  if l+1=r then exit;
  build(x<<1,l,mid);
  build(x<<1+1,mid,r);
end;

procedure update(x:longint);
begin
  if tree[x].tot>0 then
    tree[x].sum:=long[tree[x].right]-long[tree[x].left]
  else
    if tree[x].right-tree[x].left=1 then tree[x].sum:=0
      else
        tree[x].sum:=tree[x<<1].sum+tree[x<<1+1].sum;
end;

procedure change(x,ll,rr,y:longint);
var
  mid:longint;
begin
  if (tree[x].left=ll) and (tree[x].right=rr) then begin
    inc(tree[x].tot,y);
    update(x);
    exit;
  end;
  mid:=(tree[x].left+tree[x].right)>>1;
  if ll>=mid then change(x<<1+1,ll,rr,y)
    else
      if rr<=mid then change(x<<1,ll,rr,y)
        else begin
          change(x<<1,ll,mid,y);
          change(x<<1+1,mid,rr,y);
        end;
  update(x);
end;

procedure into;
var
  i:longint;
  x1,y1,x2,y2,yy:double;
begin
  for i:=1 to n do begin
    readln(x1,y1,x2,y2);
    line[i<<1-1].x:=x1;
    line[i<<1-1].y1:=y1;
    line[i<<1-1].y2:=y2;
    line[i<<1]:=line[i<<1-1];
    line[i<<1-1].col:=1;
    line[i<<1].col:=-1;
    line[i<<1].x:=x2;
    hash[i<<1-1]:=y1;
    hash[i<<1]:=y2;
  end;
  qsort1(1,n<<1);
  total:=1;
  num[1]:=1;
  long[1]:=hash[1];
  for i:=2 to n<<1 do begin
    if hash[i]<>hash[i-1] then begin
      inc(total);
      long[total]:=hash[i];
    end;
    num[i]:=total;
  end;
  qsort2(1,n<<1);
  build(1,1,total);
end;

procedure work;
var
  i,j:longint;
  ans:double;
begin
  ans:=0;
  for i:=1 to n<<1-1 do begin
    change(1,find(line[i].y1),find(line[i].y2),line[i].col);
    if line[i].x<>line[i+1].x then
      ans:=ans+(line[i+1].x-line[i].x)*tree[1].sum;
  end;
  writeln('Test case #',t);
  writeln('Total explored area: ',ans:0:2);
  writeln;
end;

begin
  t:=0;
  while true do begin
    readln(n);
    if n=0 then break;
    inc(t);
    into;
    work;
  end
end.

最后还被格式小小得坑了……&

点树和区间树区别在于[l,r]的两个儿子区间，如果是点树是[l,mid][mid+1,r]边界条件是l=r而区间树则是[l,mid][mid,r]边界条件是l+1=r。

bzoj 3306: 树

出题人什么心态，没写数据范围，害我以为是我的程序错了……

这题是bzoj3083的弱化版……我竟然还写了那么久

后来拿3083的程序（当时的题解http://hi.baidu.com/macaulish64/item/33fd9adbbb21b80738f6f746）交&……发现速度差不多……我的树链这么快么？

不说了竟然弱到这个地步

type
  arr1=record
    left,right:longint;
    min:int64;
  end;
  arr2=record
    toward,next:longint;
  end;
 
const
  maxn=400600;
 
var
  tree:array[0..maxn]of arr1;
  edge:array[0..maxn]of arr2;
  numin,numout,first,deep:array[0..maxn]of longint;
  hash,value:array[0..maxn]of int64;
  fa:array[0..maxn,0..20]of longint;
  n,root,esum,m,mm,time:longint;
 
function min(x,y:int64):int64;
begin
  if x<y then exit(x);
  exit(y);
end;
 
procedure addedge(i,j:longint);
begin
  inc(esum);
  edge[esum].toward:=j;
  edge[esum].next:=first[i];
  first[i]:=esum;
end;
 
procedure swap(var x,y:longint);
var
  i:longint;
begin
  i:=x;
  x:=y;
  y:=i;
end;
 
procedure dfs(x:longint);
var
  i,too:longint;
begin
  inc(time);
  numin[x]:=time;
  hash[time]:=value[x];
  i:=first[x];
  while i>0 do begin
    too:=edge[i].toward;
    deep[too]:=deep[x]+1;
    dfs(too);
    i:=edge[i].next;
  end;
  numout[x]:=time;
end;
 
procedure build(x,l,r:longint);
var
  mid:longint;
begin
  tree[x].left:=l;
  tree[x].right:=r;
  if l=r then begin
    tree[x].min:=hash[l];
    exit;
  end;
  tree[x].min:=maxlongint<<3;
  mid:=(l+r)>>1;
  build(x<<1,l,mid);
  build(x<<1+1,mid+1,r);
  tree[x].min:=min(tree[x<<1].min,tree[x<<1+1].min);
end;
 
procedure change(x,y:longint;z:int64);
var
  mid:longint;
begin
  if (tree[x].left=y) and (tree[x].right=y) then begin
    tree[x].min:=z;
    exit;
  end;
  mid:=(tree[x].left+tree[x].right)>>1;
  if y<=mid then change(x<<1,y,z)
    else change(x<<1+1,y,z);
  tree[x].min:=min(tree[x<<1].min,tree[x<<1+1].min);
end;
 
function askmin(x,l,r:longint):int64;
var
  mid:longint;
begin
  if (tree[x].left=l) and (tree[x].right=r) then exit(tree[x].min);
  mid:=(tree[x].left+tree[x].right)>>1;
  if l>mid then exit(askmin(x<<1+1,l,r))
  else
    if r<=mid then exit(askmin(x<<1,l,r))
    else
      exit(min(askmin(x<<1,l,mid),askmin(x<<1+1,mid+1,r)));
end;
 
function lca(x,y:longint):longint;
var
  i:longint;
begin
  if deep[x]<deep[y] then swap(x,y);
  for i:=mm downto 0 do
    if deep[y]+1<=deep[fa[x,i]] then
      x:=fa[x,i];
  if y=fa[x,0] then exit(x)
    else x:=fa[x,0];
  for i:=mm downto 1 do
    if fa[x,i]<>fa[y,i] then begin
      x:=fa[x,i];
      y:=fa[y,i];
    end;
  exit(x);
end;
 
procedure into;
var
  i,j:longint;
begin
  readln(n,m);
  for i:=1 to n do begin
    readln(fa[i,0],value[i]);
    if fa[i,0]=0 then root:=i
      else addedge(fa[i,0],i);
  end;
  deep[root]:=1;
  dfs(root);
  build(1,1,n);
  mm:=trunc(ln(n)/ln(2))+1;
  for j:=1 to mm do
    for i:=1 to n do
      fa[i,j]:=fa[fa[i,j-1],j-1];
end;
 
procedure work;
var
  ch:char;
  x,i:longint;
  l:int64;
begin
  while m>0 do begin
    dec(m);
    read(ch);
    if ch='Q' then begin
      readln(x);
      if x=root then writeln(tree[1].min)
      else begin
        i:=lca(root,x);
        if fa[i,0]<>x then writeln(askmin(1,numin[x],numout[x]))
        else
          if numout[i]<n then
            writeln(min(askmin(1,1,numin[i]-1),askmin(1,numout[i]+1,n)))
          else writeln(askmin(1,1,numin[i]-1));
      end;
    end
    else
    if ch='V' then begin
      readln(i,l);
      change(1,numin[i],l);
    end
    else readln(root);
  end;
end;
 
begin
  into;
  work
end.

UVA 11297 Census

 二维线段树裸题，单点修改，区间查询

半小时敲完不用调直接1a我也是蛮拼的

算是第一次敲二维线段树（虽然不难）；

二维线段树要注意的就是大树到小树，而小树节点也要根据大树的叶节点进行调整

好累（但是rausen大神一天切好多题啊）

type
  arr1=record
    left,right:longint;
  end;
  arr2=record
    left,right,min,max:longint;
  end;

const
  maxn=4000;

var
  tree1:array[0..maxn]of arr1;
  tree2:array[0..maxn,0..maxn]of arr2;
  a:array[0..505,0..505]of longint;
  x1,x2,y1,y2,n,m,ansmin,ansmax:longint;


function max(x,y:longint):longint;
begin
  if x<y then exit(y);
  exit(x);
end;

function min(x,y:longint):longint;
begin
  if x<y then exit(x);
  exit(y);
end;

procedure buildsmall(x0,x,l,r:longint);
var
  mid:longint;
begin
  tree2[x0][x].left:=l;
  tree2[x0][x].right:=r;
  if l=r then begin
    if tree1[x0].left=tree1[x0].right then begin
      tree2[x0][x].min:=a[tree1[x0].left][l];
      tree2[x0][x].max:=tree2[x0][x].min;
    end
    else begin
      tree2[x0][x].min:=min(tree2[x0<<1][x].min,tree2[x0<<1+1][x].min);
      tree2[x0][x].max:=max(tree2[x0<<1][x].max,tree2[x0<<1+1][x].max);
    end;
    exit;
  end;
  mid:=(l+r)>>1;
  buildsmall(x0,x<<1,l,mid);
  buildsmall(x0,x<<1+1,mid+1,r);
  tree2[x0][x].min:=min(tree2[x0][x<<1].min,tree2[x0][x<<1+1].min);
  tree2[x0][x].max:=max(tree2[x0][x<<1].max,tree2[x0][x<<1+1].max);
end;

procedure buildbig(x,l,r:longint);
var
  mid:longint;
begin
  tree1[x].left:=l;
  tree1[x].right:=r;
  if l=r then
    buildsmall(x,1,1,m)
  else begin
    mid:=(l+r)>>1;
    buildbig(x<<1,l,mid);
    buildbig(x<<1+1,mid+1,r);
    buildsmall(x,1,1,m);
  end;
end;

procedure querysmall(x0,x,l,r:longint);
var
  mid:longint;
begin
  if (tree2[x0][x].left=l) and (tree2[x0][x].right=r) then begin
    ansmin:=min(ansmin,tree2[x0][x].min);
    ansmax:=max(ansmax,tree2[x0][x].max);
    exit;
  end;
  mid:=(tree2[x0][x].left+tree2[x0][x].right)>>1;
  if l>mid then querysmall(x0,x<<1+1,l,r)
    else
      if r<=mid then querysmall(x0,x<<1,l,r)
      else begin
        querysmall(x0,x<<1,l,mid);
        querysmall(x0,x<<1+1,mid+1,r);
      end;
end;

procedure querybig(x,l,r:longint);
var
  mid:longint;
begin
  if (tree1[x].left=l) and (tree1[x].right=r) then begin
    querysmall(x,1,y1,y2);
    exit;
  end;
  mid:=(tree1[x].left+tree1[x].right)>>1;
  if l>mid then querybig(x<<1+1,l,r)
    else
      if r<=mid then querybig(x<<1,l,r)
      else begin
        querybig(x<<1,l,mid);
        querybig(x<<1+1,mid+1,r);
      end;
end;

procedure changesmall(x0,x:longint);
var
  mid:longint;
begin
  if tree2[x0][x].left=tree2[x0][x].right then begin
    if tree1[x0].left=tree1[x0].right then begin
      tree2[x0][x].min:=a[tree1[x0].left][tree2[x0][x].left];
      tree2[x0][x].max:=tree2[x0][x].min;
    end
    else begin
      tree2[x0][x].min:=min(tree2[x0<<1][x].min,tree2[x0<<1+1][x].min);
      tree2[x0][x].max:=max(tree2[x0<<1][x].max,tree2[x0<<1+1][x].max);
    end;
    exit;
  end;
  mid:=(tree2[x0][x].left+tree2[x0][x].right)>>1;
  if y1<=mid then changesmall(x0,x<<1)
    else changesmall(x0,x<<1+1);
  tree2[x0][x].min:=min(tree2[x0][x<<1].min,tree2[x0][x<<1+1].min);
  tree2[x0][x].max:=max(tree2[x0][x<<1].max,tree2[x0][x<<1+1].max);
end;

procedure changebig(x:longint);
var
  mid:longint;
begin
  if tree1[x].left=tree1[x].right then begin
    changesmall(x,1);
    exit;
  end;
  mid:=(tree1[x].left+tree1[x].right)>>1;
  if x1<=mid then changebig(x<<1)
    else changebig(x<<1+1);
  changesmall(x,1);
end;

procedure into;
var
  i,j:longint;
begin
  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do
      read(a[i,j]);
  readln;
  buildbig(1,1,n);
end;

procedure work;
var
  q:longint;
  ch:char;
begin
  readln(q);
  while q>0 do begin
    dec(q);
    read(ch);
    if ch='q' then begin
      readln(x1,y1,x2,y2);
      ansmax:=-maxlongint;
      ansmin:=maxlongint;
      querybig(1,x1,x2);
      writeln(ansmax,' ',ansmin);
    end
    else begin
      readln(x1,y1,a[x1,y1]);
      changebig(1);
    end;
  end;
end;

begin
  into;
  work;
  readln;
  readln
end.

（为什么我的sb线段树要记录left和right&……算了都习惯了就不改了）

脑洞大想写二维线段树区间修改加区间查询（结果不会问了iwtwiioi大神还是不会，是不是没救了）

云说是写不出的……