好久没来这儿了，忙了好久的数据库结构，现在来除个草吧。
【BZOJ3223】【TYVJ1729】文艺平衡树
只需要一个翻转标记。华丽的nlogn复杂度。
program p3223;
type
tree=record
rev:boolean;
l,r,w,size,father:longint;
end;
var
t:array[0..110000] of tree;
i,j,n,len,k1,k2,m,k3:longint;
procedure change(k:longint);
begin
if k=0 then exit;
t[t[k].l].father:=k; t[t[k].r].father:=k;
t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
end;
procedure reversal(k:longint);
var
i:longint;
begin
if k=0 then exit;
i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i;
t[k].rev:=not t[k].rev;
end;
procedure pushdown(k:longint);
begin
if k=0 then exit;
if t[k].rev then begin
reversal(t[k].l); reversal(t[k].r); t[k].rev:=false;
end;
end;
procedure zig(k:longint);
var
i:tree;
f:longint;
begin
f:=t[k].father;
pushdown(f); pushdown(k);
i:=t[f]; t[f]:=t[k]; t[k]:=i;
t[k].l:=t[f].r; t[f].r:=k; t[f].father:=t[k].father; t[k].father:=f;
change(k); change(f);
end;
procedure zag(k:longint);
var
i:tree;
f:longint;
begin
f:=t[k].father;
pushdown(f); pushdown(k);
i:=t[f]; t[f]:=t[k]; t[k]:=i;
t[k].r:=t[f].l; t[f].l:=k; t[f].father:=t[k].father; t[k].father:=f;
change(k); change(f);
end;
procedure build(now,l,r:longint);
var
mid:longint;
begin
t[now].rev:=false;
mid:=(l+r) shr 1; t[now].w:=mid;
if mid>l then begin
t[now].l:=len+1; inc(len); build(len,l,mid-1);
end;
if mid<r then begin
t[now].r:=len+1; inc(len); build(len,mid+1,r);
end;
change(now);
end;
function find(now,k:longint):longint;
var
l,r:longint;
begin
pushdown(now);
l:=t[now].l; r:=t[now].r;
if t[l].size=k-1 then exit(now);
if t[l].size<k-1 then exit(find(r,k-t[l].size-1));
exit(find(l,k));
end;
procedure up(k1,k2:longint);
var
i,j:longint;
begin
if k1=k2 then exit;
if t[k1].father=k2 then begin
if t[k2].l=k1 then zig(k1) else zag(k1);
exit;
end;
i:=t[k1].father; j:=t[i].father;
if k1=t[i].l then begin
if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(i); end;
end else
if i=t[j].l then begin zag(k1); zig(i); end else begin zag(i); zag(k1); end;
up(j,k2);
end;
begin
readln(n,m);
len:=1;
t[0].size:=0;
build(1,0,n+1);
for i:=1 to m do begin
readln(k1,k2);
k3:=find(1,k1);
up(k3,1);
t[0].size:=0;
k3:=find(1,k2+2);
up(k3,t[1].r);
t[0].size:=0;
reversal(t[t[1].r].l);
end;
for i:=1 to n do begin
k3:=find(1,i+1);
write(t[k3].w);
if i<>n then write(' ');
end;
end.
【BZOJ1058】【ZJOI2007】报表统计
一棵线段树一棵平衡树。可惜由于PASCAL的特性我T了那么一点点。
program p1058;
const
s1='IN_SORT_GAP';
type
splay=record
l,r,father,ans,maxnum,minnum,w:longint;
end;
tree=record
l,r,ans:longint;
end;
var
t:array[0..2500000] of tree;
x:array[0..1500000] of splay;
y:array[0..500000] of longint;
i,j,n,m,len,k1,k2,k3:longint;
s:string;
ch:char;
function max(k1,k2:longint):longint;
begin
if k1<k2 then exit(k2) else exit(k1);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
procedure change(k:longint);
begin
x[x[k].l].father:=k; x[x[k].r].father:=k; x[k].maxnum:=x[k].w; x[k].minnum:=x[k].w; x[k].ans:=maxlongint;
if x[k].l<>0 then begin x[k].maxnum:=max(x[k].maxnum,x[x[k].l].maxnum);
x[k].minnum:=min(x[k].minnum,x[x[k].l].minnum); x[k].ans:=min(x[k].ans,x[x[k].l].ans);
x[k].ans:=min(x[k].ans,x[k].w-x[x[k].l].maxnum);
end;
if x[k].r<>0 then begin x[k].maxnum:=max(x[k].maxnum,x[x[k].r].maxnum);
x[k].minnum:=min(x[k].minnum,x[x[k].r].minnum); x[k].ans:=min(x[k].ans,x[x[k].r].ans);
x[k].ans:=min(x[k].ans,x[x[k].r].minnum-x[k].w);
end;
end;
procedure zig(k:longint);
var
i:splay;
f:longint;
begin
f:=x[k].father; i:=x[f]; x[f]:=x[k]; x[k]:=i;
x[f].father:=x[k].father; x[k].l:=x[f].r; x[f].r:=k;
x[k].father:=f; x[x[f].l].father:=f;
change(k);
end;
procedure zag(k:longint);
var
i:splay;
f:longint;
begin
f:=x[k].father; i:=x[f]; x[f]:=x[k]; x[k]:=i;
x[f].father:=x[k].father; x[k].r:=x[f].l; x[f].l:=k;
x[k].father:=f; x[x[f].r].father:=f;
change(k);
end;
procedure up(k:longint);
var
k1,k2:longint;
begin
if k<=1 then exit;
if x[k].father=1 then begin
if x[1].l=k then zig(k) else zag(k);
exit;
end;
k1:=x[k].father; k2:=x[k1].father;
if k=x[k1].l then begin
if k1=x[k2].l then begin zig(k1); zig(k); end else begin zig(k); zag(k1); end;
end else begin
if k1=x[k2].l then begin zag(k); zig(k1); end else begin zag(k1); zag(k); end;
end;
up(k2);
end;
procedure insert(k1,k2:longint);
var
i,j:longint;
begin
if x[k1].w<k2 then begin
if x[k1].r=0 then x[k1].r:=len else insert(x[k1].r,k2);
end else
if x[k1].l=0 then x[k1].l:=len else insert(x[k1].l,k2);
change(k1);
end;
procedure buildtree(k1,k2,k3:longint);
begin
if k2=k3 then begin
t[k1].l:=y[k2]; t[k1].r:=y[k2]; t[k1].ans:=maxlongint; exit;
end;
buildtree(k1*2,k2,(k2+k3) shr 1);
buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
t[k1].l:=t[k1*2].l; t[k1].r:=t[k1*2+1].r;
t[k1].ans:=min(min(t[k1*2].ans,t[k1*2+1].ans),abs(t[k1*2].r-t[k1*2+1].l));
end;
procedure maintain(k:longint);
begin
t[k].l:=t[k*2].l; t[k].r:=t[k*2+1].r;
t[k].ans:=min(min(t[k*2].ans,t[k*2+1].ans),abs(t[k*2].r-t[k*2+1].l));
end;
procedure rebuild(k1,k2,k3,k4,k5:longint);
begin
if (k2>k4) or (k3<k4) then exit;
if (k2=k3) and (k2=k4) then begin
t[k1].ans:=min(t[k1].ans,abs(t[k1].r-k5)); t[k1].r:=k5; exit;
end;
rebuild(k1*2,k2,(k2+k3) shr 1,k4,k5);
rebuild(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
maintain(k1);
end;
begin
readln(n,m); len:=0;
fillchar(x,sizeof(x),0);
for i:=1 to n do begin
read(y[i]);
inc(len); x[len].ans:=maxlongint; x[len].maxnum:=y[i]; x[len].minnum:=y[i]; x[len].w:=y[i];
if len<>1 then begin
insert(1,y[i]); up(len); change(1);
end;
up(len);
end;
buildtree(1,1,n);
readln;
for i:=1 to m do begin
read(ch);
if ch='I' then begin
for j:=1 to 5 do read(ch); readln(k1,k2);
rebuild(1,1,n,k1,k2);
inc(len); x[len].ans:=maxlongint; x[len].maxnum:=y[i]; x[len].minnum:=y[i]; x[len].w:=k2;
insert(1,k2);
up(len); change(1);
end else begin
readln(s);
if s=s1 then writeln(x[1].ans) else writeln(t[1].ans);
end;
end;
end.
【BZOJ1251】序列终结者
一个区间加标记一个翻转标记。
program p1251;
type
tree=record
w,add,fz,ans,f,father,l,r,size:int64;
end;
var
t:array[0..200000] of tree;
i,j,n,m,k1,k2,k3,k4,len,k5,k6,root:longint;
function max(k1,k2:int64):int64;
begin
if k1<k2 then exit(k2) else exit(k1);
end;
procedure change(k:longint);
begin
if k=0 then exit;
t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
t[k].ans:=max(t[k].w,max(t[t[k].l].ans,t[t[k].r].ans))+t[k].add;
end;
procedure fanzhuan(k:longint);
var
i,j:longint;
begin
i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i; t[k].fz:=t[k].fz xor 1;
end;
procedure pushdown(k:longint);
begin
t[k].w:=t[k].w+t[k].add;
if t[k].fz=1 then begin
fanzhuan(t[k].l); fanzhuan(t[k].r);
end;
inc(t[t[k].l].add,t[k].add); inc(t[t[k].l].ans,t[k].add);
inc(t[t[k].r].add,t[k].add); inc(t[t[k].r].ans,t[k].add);
t[k].fz:=0; t[k].add:=0;
end;
procedure zig(k:longint);
var
i:tree;
f:longint;
begin
f:=t[k].father;
pushdown(f); pushdown(k);
if t[f].father<>0 then begin
if t[t[f].father].l=f then t[t[f].father].l:=k else t[t[f].father].r:=k;
end;
t[k].father:=t[f].father; t[f].father:=k; t[f].l:=t[k].r; t[k].r:=f; t[t[f].l].father:=f;
change(f);
end;
procedure zag(k:longint);
var
i:tree;
f:longint;
begin
f:=t[k].father;
pushdown(f); pushdown(k);
if t[f].father<>0 then begin
if t[t[f].father].l=f then t[t[f].father].l:=k else t[t[f].father].r:=k;
end;
t[k].father:=t[f].father; t[f].father:=k; t[f].r:=t[k].l; t[k].l:=f; t[t[f].r].father:=f;
change(f);
end;
procedure insert(k1,k2:longint);
begin
if t[k1].f<k2 then begin
if t[k1].r=0 then begin t[k1].r:=len; t[len].father:=k1; end else insert(t[k1].r,k2);
end else if t[k1].l=0 then begin t[k1].l:=len; t[len].father:=k1; end else insert(t[k1].l,k2);
change(k1);
end;
procedure up(k1,k2:longint);
var
i,j:longint;
begin
if (k1=k2) then exit;
if t[k1].father=k2 then begin
if t[k2].l=k1 then zig(k1) else zag(k1); change(k1);
exit;
end;
i:=t[k1].father; j:=t[i].father;
if k1=t[i].l then begin
if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(k1); end;
end else
if i=t[j].l then begin zag(k1); zig(k1); end else begin zag(i); zag(k1); end;
if j=k2 then exit;
up(k1,k2);
end;
function findwhere(k1,k2:longint):longint;
begin
pushdown(k1);
if t[t[k1].l].size=k2-1 then exit(k1);
if t[t[k1].l].size<k2-1 then exit(findwhere(t[k1].r,k2-t[t[k1].l].size-1));
exit(findwhere(t[k1].l,k2));
end;
begin
readln(n,m);
fillchar(t,sizeof(t),0); len:=0; t[0].ans:=-maxlongint*1000; root:=1;
for i:=0 to n+1 do begin
inc(len); t[len].w:=0; t[len].size:=1; t[len].f:=i; t[len].ans:=i;
if len<>1 then begin
insert(root,i); up(len,root); root:=len;
end;
end;
for i:=1 to m do begin
read(k1,k2,k3);
k5:=findwhere(root,k2); up(k5,root);root:=k5; k5:=findwhere(root,k3+2); up(k5,t[root].r);
if k1=1 then begin
read(k4); inc(t[t[t[root].r].l].add,k4); change(t[t[root].r].l); change(t[root].r); change(root);
end else if k1=2 then fanzhuan(t[t[root].r].l)
else writeln(t[t[t[root].r].l].ans);
end;
end.
评论 (0)
