BZOJ3595 SCOI2014 Onlinejudge
考场上Splay写挫Treap写挫滚写线性表...
题意 维护队列,要求支持
(1).找到队列中元素值为x的位置,把其位置上的元素值改为y
(2).找到队列中元素值为x的位置,把该位置提到队首
提到队首之前在其前面的顺位后移1位
(3).找到队列中元素值为x的位置,把该位置降到队尾
降到队尾之前在其之后的顺位前移1位
(4).查询队列某位置的元素值
队列长度为N,初始时候队列为{1,2,..N},(1)操作中x一定存在于队列中,y in [1..2e8]且不在队列中,输入合法.
N<=1e8 M<=1e5
Tag Splay Treap
代码题 本来是2小时1A,对拍写错了调一晚上...
思考N不大的情况
把所有元素值用平衡树维护,队列用Splay维护
平衡树每个结点存<键值:元素值;卫星:指针指向该元素值在Splay中的位置>
Splay就是维护动态序列的情况,每个结点存元素值
操作处理
1.修改元素值
在平衡树里面找到那个元素值,在其指向的Splay结点修改元素值.
修改平衡树.其中再记录一下该元素值在Splay中的rank.
2.提升/下降元素值
在平衡树里面找到那个元素值,把其指向的Splay结点提升/下降.
3.查询序列某位置元素值
直接Splay上面搞
N更大了
显然有问题稀疏性==>
Splay每个节点代表一段元素值的区间,Splay中区间互不相交
显然实际的序列中Splay中的某结点代表区间一定是连续的.最开始有[1..N]
区间A小于区间B的定义是A.R<B.L,平衡树维护这些区间
存储<键值:区间;卫星:指针>
之后修改某个点的时候把其所在区间Split即可
比如要split一个i,i在区间[L,R]中(暂时不考虑边界)
我们只需要把[L,R]拆成[L,i-1],[i],[i+1,R].Splay和Treap里面都要拆.
之后注意Splay的size怎么搞就是了,再自己搞搞边界即可
这道题可恶的是可持久化Treap不好搞..
比如[1,2,3,4,5, 6,7,8,9,10], 不妨写成[1..10]
1.把元素值为5位的元素值改为27 [1..4][27][5..10]
2.提升元素值为27的位 [27][1..4][6..10]
3.下降元素值为3的位 [27][1..2][4][6..10][3]
比如[1..1e8]
1.提升元素值为233的位 [233][1..232][234..1e8]
2.把元素值为234的位的元素值改为 100000001
[233][1..232][100000001][235..1e8]
代码(Release ver)
只是程序头有点凶残罢了,程序要写只需要3小时不到.
{$INLINE ON}
program bzoj3595;
const maxint=longint($3f3f3f3f);
minint=longint($c0c0c0c0);
type int=record l,r:longint; end;
psplay=^tsplay;
tsplay=record
v:int;
w,size:longint;
l,r,p:psplay;
end;
ptreap=^ttreap;
ttreap=record
v:int;
p:longint;
img:psplay;
l,r:ptreap;
end;
const empty:int=(l:0;r:0);
var rspl,nspl:psplay;
rtrp,ntrp:ptreap;
n,m,la:longint;
procedure splay_init;
begin
new(nspl); with nspl^ do begin
v:=empty; w:=0; size:=0; l:=nspl; r:=nspl; p:=nspl;
end; rspl:=nspl;
end;
procedure lrot(var i:psplay);
var j:psplay;
begin
j:=i^.r; i^.r:=j^.l; j^.l:=i;
j^.p:=i^.p; i^.p:=j; i^.r^.p:=i;
i^.size:=i^.l^.size+i^.r^.size+i^.w;
j^.size:=j^.l^.size+j^.r^.size+j^.w;
if i=rspl then rspl:=j
else if i=j^.p^.l then j^.p^.l:=j
else if i=j^.p^.r then j^.p^.r:=j;
i:=j;
end;
procedure rrot(var i:psplay);
var j:psplay;
begin
j:=i^.l; i^.l:=j^.r; j^.r:=i;
j^.p:=i^.p; i^.p:=j; i^.l^.p:=i;
i^.size:=i^.l^.size+i^.r^.size+i^.w;
j^.size:=j^.l^.size+j^.r^.size+j^.w;
if i=rspl then rspl:=j
else if i=j^.p^.l then j^.p^.l:=j
else if i=j^.p^.r then j^.p^.r:=j;
i:=j;
end;
procedure splay(var i,j:psplay);
var k:psplay;
begin
while i<>j do
if i^.p=j then
if i=j^.l then rrot(j)
else lrot(j)
else if i=i^.p^.l then
if i^.p=i^.p^.p^.l then begin
k:=i^.p^.p; rrot(k);
k:=i^.p; rrot(k);
end else begin
k:=i^.p; rrot(k);
k:=i^.p; lrot(k);
end
else if i^.p=i^.p^.p^.l then begin
k:=i^.p; lrot(k);
k:=i^.p; rrot(k);
end else begin
k:=i^.p^.p; lrot(k);
k:=i^.p; lrot(k);
end;
end;
function select(i:psplay;j:longint):psplay;
begin
while i<>nspl do begin
if (j>i^.l^.size)and(j<=i^.l^.size+i^.w) then exit(i)
else if j<=i^.l^.size then i:=i^.l
else begin dec(j,i^.l^.size+i^.w); i:=i^.r; end;
end; exit(nspl);
end;
function rank(i:psplay):longint; inline;
begin
splay(i,rspl); exit(i^.l^.size);
end;
function merge(i,j:psplay):psplay;
var k,t:psplay;
begin
if i=nspl then begin rspl:=j; exit(rspl); end;
if j=nspl then begin rspl:=i; exit(rspl); end;
j^.p:=nspl; k:=j; while k^.l<>nspl do k:=k^.l;
i^.p:=k; k^.l:=i; while k<>nspl do begin
inc(k^.size,i^.size); k:=k^.p;
end; rspl:=j; splay(i,rspl); exit(rspl);
end;
procedure treap_init;
begin
new(ntrp); with ntrp^ do begin
v:=empty; p:=maxint; img:=nspl; l:=ntrp; r:=ntrp;
end; rtrp:=ntrp;
end;
procedure lrot(var i:ptreap); inline;
var j:ptreap;
begin
j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j;
end;
procedure rrot(var i:ptreap); inline;
var j:ptreap;
begin
j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j;
end;
function insert(var i:ptreap;j:int):ptreap;
begin
if i=ntrp then begin
new(i); with i^ do begin
v:=j; p:=random(maxint); img:=nspl; l:=ntrp; r:=ntrp;
end; exit(i);
end else if j.r<i^.v.l then begin
insert:=insert(i^.l,j); if i^.l^.p<i^.p then rrot(i);
end else begin
insert:=insert(i^.r,j); if i^.r^.p<i^.p then lrot(i);
end;
end;
function delete(var i:ptreap;j:int):psplay;
begin
if (j.l=i^.v.l)and(j.r=i^.v.r) then
if i^.l=ntrp then begin
delete:=i^.img; i:=i^.r;
end else if i^.r=ntrp then begin
delete:=i^.img; i:=i^.l;
end else if i^.l^.p<i^.r^.p then begin
rrot(i); exit(delete(i^.r,j));
end else begin
lrot(i); exit(delete(i^.l,j));
end
else if j.r<i^.v.l then exit(delete(i^.l,j))
else exit(delete(i^.r,j));
end;
function search(i:ptreap;j:longint):ptreap;
begin
while i<>ntrp do
if (j>=i^.v.l)and(j<=i^.v.r) then exit(i)
else if j<i^.v.l then i:=i^.l
else i:=i^.r;
exit(ntrp);
end;
procedure img_init(n:longint);
begin
new(rtrp); new(rspl);
with rtrp^ do begin
v.l:=1; v.r:=n; p:=random(maxint); img:=rspl; l:=ntrp; r:=ntrp;
end; with rspl^ do begin
v.l:=1; v.r:=n; w:=n; size:=n; l:=nspl; r:=nspl;
end;
end;
function breakofint(i:longint):ptreap;
var il,ir:longint;
s1,s2,s3:psplay;
t1,t2,t3:ptreap;
i1:int;
begin
t1:=search(rtrp,i); s1:=t1^.img; splay(s1,rspl); s1^.w:=1;
il:=t1^.v.l; ir:=t1^.v.r; if il<i then begin
s1^.v.l:=i; s2:=s1^.l; new(s1^.l); with s1^.l^ do begin
v.l:=il; v.r:=i-1; w:=i-il; l:=s2; r:=nspl; p:=s1;
end; s2^.p:=s1^.l; with s1^.l^ do size:=l^.size+w;
i1.l:=il; i1.r:=i-1; t1^.v.l:=i; t2:=insert(rtrp,i1); t2^.img:=s1^.l;
end;
if ir>i then begin
s1^.v.r:=i; s3:=s1^.r; new(s1^.r); with s1^.r^ do begin
v.l:=i+1; v.r:=ir; w:=ir-i; l:=nspl; r:=s3; p:=s1;
end; s3^.p:=s1^.r; with s1^.r^ do size:=r^.size+w;
i1.l:=i+1; i1.r:=ir; t1^.v.r:=i; t3:=insert(rtrp,i1); t3^.img:=s1^.r;
end; exit(t1);
end;
procedure edit(i:ptreap;j:longint);
var s1:psplay;
begin
s1:=i^.img; s1^.v.l:=j; s1^.v.r:=j;
delete(rtrp,i^.v); i:=insert(rtrp,s1^.v); i^.img:=s1;
end;
procedure lift(i:psplay);
var s1,s2,s3:psplay;
begin
splay(i,rspl); if i^.l=nspl then exit;
s1:=i; s1^.size:=s1^.w; s2:=i^.l; s3:=i^.r;
i^.l:=nspl; i^.r:=nspl; rspl:=merge(s1,merge(s2,s3));
end;
procedure deft(i:psplay);
var s1,s2,s3:psplay;
begin
splay(i,rspl); if i^.r=nspl then exit;
s1:=i; s1^.size:=s1^.w; s2:=i^.l; s3:=i^.r;
s1^.l:=nspl; s1^.r:=nspl; rspl:=merge(merge(s2,s3),s1);
end;
function getnum(i:longint):longint;
var j:psplay;
begin
j:=rspl; while j<>nspl do begin
if (i>j^.l^.size)and(i<=j^.l^.size+j^.w) then break
else if i<=j^.l^.size then j:=j^.l
else begin dec(i,j^.l^.size+j^.w); j:=j^.r; end;
end; dec(i,j^.l^.size); splay(j,rspl); exit(j^.v.l+i-1);
end;
procedure work;
var i,j,op,il,ir:longint;
t1,t2,t3:ptreap;
s1,s2,s3,s4,s5:psplay;
i1:int;
begin
readln(n,m); img_init(n); la:=0;
while m>0 do begin dec(m);
read(op); case op of
1:begin
readln(i,j); dec(i,la); dec(j,la);
t1:=breakofint(i); la:=rank(t1^.img)+1; writeln(la);
edit(t1,j);
end;
2:begin
readln(i); dec(i,la);
t1:=breakofint(i); la:=rank(t1^.img)+1; writeln(la);
lift(t1^.img);
end;
3:begin
readln(i); dec(i,la);
t1:=breakofint(i); la:=rank(t1^.img)+1; writeln(la);
deft(t1^.img);
end;
4:begin
readln(i); dec(i,la);
la:=getnum(i); writeln(la);
end;
end;
end;
end;
begin
treap_init;
splay_init;
work;
end.
2021年11月17日 16:02
Model Papers 2022 in pdf format for students in grades 1-10, 11th, and 12th for all subjects are available on this website. Download links for all Model Paper 2022 Indian education boards are provided here. Model Papers 2022 created these papers, which may be seen on their official website. These Model papers will aid you in getting higher Board test ranks and scores.