线段树维护狭长网格图上的信息

一 适用问题

1.基本前提

给定是网格图,并且具有狭长的特性,长宽中一维不应超过10
维护信息需要满足线段树可维护性,换言结合律

2.连通性

例 BZOJ 1018

3.最短路

例 BZOJ 2459

   "六乘N最短路" (资料暂缺)

二 基本思想

1.基本思想

把狭长的网格图用线段树维护,把狭长的区间类似序列处理地分割成小区间

对于每个小区间记录它的端点之间的信息并维护,有时候需要维护边界

然后修改的时候再更新一下即可,查询的时候合并一下即可

例

BZOJ 1018 2*N网格图动态维护连通性

我们对于每个区间维护bool c[2][2],bool col[2]表示左右共4个顶点之间的连通性以及左上左下,右上右下顶点的连通性

BZOJ 2459 2*n网格图动态维护最短路

我们对于每个区间维护int d[2][2],int d[2]表示左右4个顶点的最短路和左上左下,右上右下顶点的最短路

BZOJ 2325 ZJOI 2011 Fight

从题意到叙述到解法的神题,第一次看汉语题上网搜题意,不剧透了

三 模版

1.模版

此类问题主要以2*N网格图形式出现,下叙述2*N网格图的处理方法

对于每个区间记录datatype d[3][2],下标从1开始

d[0][1]表示左边两个顶点的维护信息

d[0][2]表示右边两个的

d[1][1]表示左上右上的

d[1][2]表示左上右下的

d[2][1]表示左下右上的

d[2][2]表示左下右下的

之后我们需要函数datatype merge(datatype a,b)

其中a的右边两个顶点正好是b的左边两个顶点

函数返回a代表区间和b代表区间的信息合并

即返回值的左边两个顶点是a左边的两个顶点

返回至的右边两个顶点是b右边的两个顶点

之后我们需要数组datatype map[maxN],lnk[maxN]

map[i]存放{(1,i),(2,i),(1,i+1),(2,i+1)}单位区间的原原本本的信息

lnk[i]存放{(1,i),(2,i),(1,i+1),(2,i+1)}单位区间的用于计算的信息

举例 连通性问题中 对于下面区间

O ----- O

|

|

|

O ----- O

其map为(1,0,1,0,0,1) 这个例子里就是记录连边没有

但是lnk为(1,1,1,1,1,1) 这个例子里他们全部连通

然后线段树的每个叶子只代表一列,即叶子代表区间的左边两个顶点等于右边两个

之后给出线段树过程

Segtree.Init;

Segtree.Edit(NODE,Position,NewInfo)

if NODE.L=NODE.R

Update NODE.info with NewInfo

Update map and lnk if necessary

else 

if Position in [NODE.L,NODE.MID]

 Edit(NODE.lc,Position,NewInfo)

else Edit(NODE.rc,Position,NewInfo);

NODE.info=merge(merge(NODE.lc.info,lnk[NODE.MID]),NODE.rc.info)

Segtree.Query(NODE,Interval)

if [NODE.L,NODE.R]=Interval

return NODE.info

else

if Interval in [NODE.L,NODE.MID]

return Query(NODE.lc,Interval)

elseif Interval in (NODE.MID,NODE.R]

return Query(NODE.rc,Interval)

else return merge(

merge(Query(NODE.lc,Interval I [NODE.L,NODE.MID]),

   ,lnk[NODE.MID]),

Query(NODE.rc,Interval I (NODE.MID,NODE.R]))

);

但是具体给出答案的时候要分类讨论

假设当前询问的是(r1,c1),(r2,c2)的答案(连通性最短路等),r1<r2

不妨设答案是一条路径(连通路,最短路etc)

1.这条路径在c1列到c2列间

2.这条路径经过了1.1列,到达了(3-r1,c1)再通过c1列到达(r1,c1)

3.这条路径经过了c2..N列,到达了(3-r2,c2)再通过c2列到达(r2,c2)

4.这条路经过了1.1,c1.2,c2..N列,到达了

(3-r1,c1)和(3-r2,c2)再通过c1,c2列到达(r1,c1),(r2,c2)

如果信息是有向的那么我们需要多个线段树

四 应用

1.ZJOI 2011 道馆之战

神题

2.BZOJ 1018 Traffic

写这题代码时候还没有这么抽象理论所以不太符合本文理论

线段树结点

连通性:

(左上,右上)

(左上,右下)

(左下,右上)

(左下,右下)

(左上,左下)

(右上,右下)

注意如下情况

O ---- O      O

|             |

|             |

O ---- O ---- O,询问(1,2),(1,3)连通性

3.BZOJ 2459 bdcxq
线段树结点如上,连通性换成最短路

fhq给出的标程的merge是Floyd搞的,不过我们能做到更好

数据良心不卡int,maxint=$2a2a2a2a就能A

附2459 Pascal Rank 1 代码

由于我的叙述太烂的没看懂的看代码吧,虽然和我的叙述一样烂

{$INLINE ON}
program bzoj2459;
 
type tnode=array[0..2,1..2] of longint;
     pnode=^tsegn;
     tsegn=record
        v:tnode;
        l,r:pnode;
     end;
 
const maxn=100017;
      maxint=longint($2a2a2a2a);
      void:tnode=((maxint,maxint),(maxint,maxint),(maxint,maxint));
 
var root,null:pnode;
    map,lnk:array[0..maxn] of tnode;
    n,m:longint;
 
function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;
 
procedure getmin(var i:longint;j:longint); inline;      begin
if j<i then i:=j;                                       end;
 
procedure segtree_init;
begin
new(null); with null^ do begin
        fillchar(v,sizeof(v),$2a); l:=null; r:=null;
end; root:=null;
end;
 
function state(a,b,c,d,e,f:longint):tnode;  inline;                                             begin
state[0,1]:=a; state[0,2]:=b; state[1,1]:=c; state[1,2]:=d; state[2,1]:=e; state[2,2]:=f;       end;
 
function merge(a,b:tnode):tnode; inline;
var i,j,k:longint;
begin
merge[1,1]:=min(a[1,1]+b[1,1],a[1,2]+b[2,1]);   merge[1,2]:=min(a[1,1]+b[1,2],a[1,2]+b[2,2]);
merge[2,1]:=min(a[2,1]+b[1,1],a[2,2]+b[2,1]);   merge[2,2]:=min(a[2,1]+b[1,2],a[2,2]+b[2,2]);
merge[0,1]:=min(a[0,1],a[1,1]+b[0,1]+a[2,2]);   merge[0,2]:=min(b[0,2],b[1,1]+a[0,2]+b[2,2]);
end;
 
procedure recompute(a:tnode;var b:tnode);
begin
b[1,1]:=min(a[1,1],a[0,1]+a[2,2]+a[0,2]);       b[1,2]:=min(a[1,1]+a[0,2],a[0,1]+a[2,2]);
b[2,1]:=min(a[1,1]+a[0,1],a[0,2]+a[2,2]);       b[2,2]:=min(a[2,2],a[0,1]+a[1,1]+a[0,2]);
b[0,1]:=min(a[0,1],a[1,1]+a[0,2]+a[2,2]);       b[0,2]:=min(a[0,2],a[1,1]+a[0,1]+a[2,2]);
end;
 
procedure build(var i:pnode;l,r:longint);
var mid:longint;
begin
new(i); if l=r then begin
        mid:=map[l][0,1]; i^.v:=state(mid,mid,0,mid,mid,0);
end else begin
        mid:=(l+r)>>1; build(i^.l,l,mid); build(i^.r,mid+1,r);
        i^.v:=merge(merge(i^.l^.v,lnk[mid]),i^.r^.v);
end;
end;
 
procedure baseedit(var i:pnode;idf,j,k:longint);
begin
case idf of
        1:begin
                map[j-1][0,2]:=k; map[j][0,1]:=k;
                recompute(map[j-1],lnk[j-1]);
                recompute(map[j],lnk[j]);
                i^.v:=state(k,k,0,k,k,0);
        end;
        0:begin
                map[j][1,1]:=k; recompute(map[j],lnk[j]);
        end;
        2:begin
                map[j][2,2]:=k; recompute(map[j],lnk[j]);
        end;
end;
end;
 
 
procedure edit(var i:pnode;l,r,  idf,j,k:longint);
var mid:longint;
begin
if (l=r) then baseedit(i,idf,j,k) else begin
        mid:=(l+r)>>1;
        if j<=mid then edit(i^.l,l,mid,         idf,j,k)
                  else edit(i^.r,mid+1,r,       idf,j,k);
        i^.v:=merge(merge(i^.l^.v,lnk[mid]),i^.r^.v);
end;
end;
 
function get(var i:pnode;l,r,  il,ir:longint):tnode;
var mid:longint;
begin
if il>ir then exit(void);
if (l=il)and(r=ir) then exit(i^.v);
mid:=(l+r)>>1;
if ir<=mid then exit(get(i^.l,l,mid,  il,ir));
if il>mid then exit(get(i^.r,mid+1,r,  il,ir));
exit(merge(merge(get(i^.l,l,mid,  il,mid),lnk[mid]),get(i^.r,mid+1,r,  mid+1,ir)));
end;
 
function getsp(r1,c1,r2,c2:longint):longint;
var t1:longint;
    l,r,m:tnode;
begin
if c1>c2 then begin
        t1:=r1; r1:=r2; r2:=t1; t1:=c1; c1:=c2; c2:=t1;
end; l:=get(root,1,n,  1,c1);
m:=get(root,1,n,  c1,c2);
r:=get(root,1,n,  c2,n);
exit(min(
        min(
                m[r1,r2],
                l[0,2]+m[3-r1,r2]
        ),min(
                r[0,1]+m[r1,3-r2],
                l[0,2]+m[3-r1,3-r2]+r[0,1]
        )
 
));
end;
 
procedure init;
var i,j:longint;
begin
readln(n); fillchar(map,sizeof(map),$2a);
for i:=1 to n-1 do read(map[i][1,1]); readln;
for i:=1 to n do begin read(map[i][0,1]); map[i-1][0,2]:=map[i][0,1]; end; readln;
for i:=1 to n-1 do read(map[i][2,2]); readln;
for i:=1 to n do recompute(map[i],lnk[i]);
build(root,1,n);
end;
 
procedure work;
var i,j,op,ai,bi,ci,r1,c1,r2,c2:longint;
begin
readln(m); while m>0 do begin dec(m);
        read(op); case op of
                0:begin
                        readln(ai,bi,ci);
                        edit(root,1,n,  ai,bi,ci);
                end;
                1:begin
                        readln(ai,bi);
                        r1:=((ai and 1)xor 1)+1; c1:=(ai+1)>>1;
                        r2:=((bi and 1)xor 1)+1; c2:=(bi+1)>>1;
                        writeln(getsp(r1,c1,r2,c2));
                end;
        end;
end;
end;
 
begin
segtree_init;
init;
work;
end.