又来练线段树了……
poj1823题意很简单（明显的数据结构题），区间修改和统计最长连续空区间；
有了poj3468的基础，区间修改不是什么问题了，重点是求最长连续空区间；（弱弱的我纠结了好久）
在每个节点上增加3个域，lmax，rmax，maxx，分别表示从左起最长，右起最长，区间内最长，然后稍稍动点脑筋即可……
type node=record
lmax,rmax,maxx:longint;
l,r,lazy:integer; //lazy表示区间三种情况，-表示区间内有人住但未满，表示无人住，表示全住满
end;
var tree:array[..] of node;
i,n,m,a,b,c,j:longint;
procedure updata(i:longint); //更新
var p:longint;
begin
if tree[i].lazy<>- then
begin
if tree[i].lazy= then p:=tree[i].r-tree[i].l+ else p:=;
tree[i].lmax:=p;
tree[i].rmax:=p;
tree[i].maxx:=p;
end
else begin //看起来很繁琐，实际上仔细想想就明白了
tree[i].lmax:=tree[i*].lmax;
if tree[i].lmax=tree[i*].r-tree[i*].l+ then tree[i].lmax:=tree[i].lmax+tree[i*+].lmax;
tree[i].rmax:=tree[i*+].rmax;
if tree[i].rmax=tree[i*+].r-tree[i*+].l+ then tree[i].rmax:=tree[i].rmax+tree[i*].rmax;
p:=max(tree[i].lmax,tree[i].rmax);
p:=max(p,max(tree[i*].maxx,tree[i*+].maxx));
tree[i].maxx:=max(p,tree[i*].rmax+tree[i*+].lmax);
end;
end; procedure pushdown(i:longint); //lazy思想，注意标记下移的时候不忘更新，因为某个子区间不一定会被访问
begin
tree[i*].lazy:=tree[i].lazy;
updata(i*);
tree[i*+].lazy:=tree[i].lazy;
updata(i*+);
tree[i].lazy:=-; //需要标记下移的时候当前区间一定不会是全满或全空（想想为什么）
end; procedure build(i,l,r:longint); //初始化线段树
var m:longint;
begin
tree[i].l:=l; tree[i].r:=r;
tree[i].lazy:=;
updata(i);
if l<>r then
begin
m:=(l+r) div ;
build(i*,l,m);
build(i*+,m+,r);
end;
end; procedure work(i,l,r,t:longint);
var m:longint;
begin
if (l>=a) and (r<=b) then
begin
tree[i].lazy:=t;
updata(i);
end
else if l<>r then begin
if tree[i].lazy<>- then pushdown(i);
m:=(l+r) div ;
if (a<=m) then work(i*,l,m,t);
if (b>=m+) then work(i*+,m+,r,t);
updata(i); // 左右子区间访问过后更新当前区间
end;
end;
begin
readln(n,m);
build(,,n);
for i:= to m do
begin
read(c);
if c<> then
begin
readln(a,b);
b:=a+b-;
if c= then work(,,n,) else work(,,n,); //代表入住，代表退房
end
else if c= then writeln(tree[].maxx);
end;
end.
poj1823
话说线段树查起来真累（难道还是我太渣了？），耗了5次才AC
poj3667在poj1823基础上多了个查找但并不难，对于当前区间，按照从左区间到右区间的优先顺序找即可，一次AC
type node=record
l,r,lmax,rmax,maxx:longint;
lazy:integer;
end; var tree:array[..] of node;
i,n,m,a,b,c,j,l:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end; function min(a,b:longint):longint;
begin
if a= then exit(b);
if b= then exit(a);
if a>b then exit(b) else exit(a);
end;
procedure updata(i:longint);
var p:longint;
begin
if tree[i].lazy<>- then
begin
if tree[i].lazy= then p:=tree[i].r-tree[i].l+ else p:=;
tree[i].lmax:=p;
tree[i].rmax:=p;
tree[i].maxx:=p;
end
else begin
tree[i].lmax:=tree[i*].lmax;
if tree[i].lmax=tree[i*].r-tree[i*].l+ then tree[i].lmax:=tree[i].lmax+tree[i*+].lmax;
tree[i].rmax:=tree[i*+].rmax;
if tree[i].rmax=tree[i*+].r-tree[i*+].l+ then tree[i].rmax:=tree[i].rmax+tree[i*].rmax;
p:=max(tree[i].lmax,tree[i].rmax);
p:=max(p,max(tree[i*].maxx,tree[i*+].maxx));
tree[i].maxx:=max(p,tree[i*].rmax+tree[i*+].lmax);
end;
end; procedure pushdown(i:longint);
begin
tree[i*].lazy:=tree[i].lazy;
updata(i*);
tree[i*+].lazy:=tree[i].lazy;
updata(i*+);
tree[i].lazy:=-;
end; procedure find(i:longint);
begin
if tree[i].maxx<l then exit;
if (tree[i].lmax>=l) then a:=tree[i].l
else if tree[*i].maxx>=l then
find(*i)
else if tree[i*].rmax+tree[i*+].lmax>=l then
begin
a:=tree[i*].r-tree[i*].rmax+;
end
else if tree[i*+].maxx>=l then find(*i+);
if tree[i].rmax>=l then a:=min(a,tree[i].r-tree[i].rmax+);
end; procedure build(i,l,r:longint);
var m:longint;
begin
tree[i].l:=l; tree[i].r:=r;
tree[i].lazy:=;
updata(i);
if l<>r then
begin
m:=(l+r) div ;
build(i*,l,m);
build(i*+,m+,r);
end;
end; procedure work(i,l,r,t:longint);
var m:longint;
begin
if (l>=a) and (r<=b) then
begin
tree[i].lazy:=t;
updata(i);
end
else if l<>r then begin
if tree[i].lazy<>- then pushdown(i);
m:=(l+r) div ;
if (a<=m) then work(i*,l,m,t);
if (b>=m+) then work(i*+,m+,r,t);
updata(i);
end;
end; begin
readln(n,m);
build(,,n);
for i:= to m do
begin
read(c);
if c= then
begin
readln(l);
a:=;
find();
writeln(a);
b:=a+l-;
if a<> then work(,,n,);
end
else if c= then
begin
readln(a,b);
b:=a+b-;
work(,,n,);
end;
end;
end.
poj3667