看了下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 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
       
        >1].x;  repeat    while line[i].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
         
          >1;    if long[mid]=x then exit(mid);    if long[mid]
          
           >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;  endend.
          
         
        
       
      

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

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

 

bzoj 3306: 树

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

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

后来拿3083的程序（当时的题解）交&……发现速度差不多……我的树链这么快么？

不说了竟然弱到这个地步

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
      
       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]
       
        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]
       
      

 

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
      
       >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;  readlnend.
      

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

 

 

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

云说是写不出的……