BZOJ1014 Prefix
题意
动态维护字符串S要求支持
1.插入字符
2.修改字符
3.查询LCP(i,j)
N!>100000,M!>150000,3操作不超过10000次
Tag Splay
用一颗平衡树维护这个串,然后求LCP显然是二分判定
判定用RK就可以了,也就是Hash,每次看i..i+k-1,j..j+k-1构成的Hash是否相同
Hash直接把串看成一个k进制数即可,k!<26.
我一看,发挥自己的乱搞才能写了fhqtreap+双Hash.
因为vfk的HashKillerII告诉我单Hash很简单就能卡.
然后TLE.改成单Hash仍然TLE.
——fhqtreap折翼之时
之后换用Splay,本机过BZOJ还是TLE.
没办法,把Hash模大素数改成了and maxlongint,WA.然后把字符串改成了29进制才AC.
据说ZKWSplay轻松虐此题,但是会ZKWSplay的神已经退役了(泣)
这道题说明了,fhqtreap单次操作的常数的确很小,但是由于其严重依赖split和merge
有时一个操作需要6,7次Split和Merge,而Split和Merge都是严格lgn的
不同于Splay越转越快,造成本来挺快的fhqtreap败给了Splay
不过fhqtreap最大的优点便是代码短易理解不易写挫,这个是普通Splay无法比拟的.
越转越快的Splay
{$INLINE ON}
program bzoj1014;
type pnode=^tnode;
tnode=record
v,h,size:longint;
l,r,p:pnode;
end;
const mo:int64=1000000007;
base:int64=29;
maxn=100017;
var root,null:pnode;
s,e:array[0..maxn] of longint;
n,m:longint;
procedure splay_init;
begin
new(null); with null^ do begin
v:=0; h:=0; size:=0; l:=null; r:=null; p:=null;
end; root:=null;
end;
procedure rk(var i:pnode); inline; begin
i^.h:=(int64(i^.l^.h)*int64(e[i^.r^.size+1])+int64(i^.v)*e[i^.r^.size]+int64(i^.r^.h)) and maxlongint; end;
procedure lrot(var i:pnode);
var j:pnode;
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+1;
j^.size:=j^.l^.size+j^.r^.size+1;
if i=root then root:=j
else if i=j^.p^.l then j^.p^.l:=j
else j^.p^.r:=j;
rk(i); rk(j); i:=j;
end;
procedure rrot(var i:pnode);
var j:pnode;
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+1;
j^.size:=j^.l^.size+j^.r^.size+1;
if i=root then root:=j
else if i=j^.p^.l then j^.p^.l:=j
else j^.p^.r:=j;
rk(i); rk(j); i:=j;
end;
procedure dsplay(var i,j:pnode);
var k:pnode;
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;
procedure ssplay(var i,j:pnode);
var k:pnode;
begin
while i<>j do begin
k:=i^.p; if i=k^.l then rrot(k) else lrot(k);
end; rk(i);
end;
function select(i:pnode;j:longint):pnode; inline;
begin
while i<>null do
if j=i^.l^.size+1 then exit(i)
else if j<=i^.l^.size then i:=i^.l
else begin dec(j,i^.l^.size+1); i:=i^.r; end;
exit(null);
end;
procedure build(var i:pnode;l,r:longint);
var mid:longint;
begin
mid:=(l+r)>>1; new(i); i^.v:=s[mid]; i^.size:=r-l+1; i^.p:=null;
if l<mid then begin build(i^.l,l,mid-1); i^.l^.p:=i; end else i^.l:=null;
if r>mid then begin build(i^.r,mid+1,r); i^.r^.p:=i; end else i^.r:=null;
rk(i);
end;
procedure prepint(i,j:longint);
var k:pnode;
begin
k:=select(root,i); ssplay(k,root);
k:=select(root,j); ssplay(k,root^.r);
rk(root^.r^.l);
end;
function lcp(i,j:longint):longint;
var l,r,mid,h1,h2:longint;
begin
if i>j then begin l:=i; i:=j; j:=l; end;
l:=0; r:=n-j+1; while l<>r do begin
mid:=(l+r)>>1+1;
prepint(i,i+mid+1); h1:=root^.r^.l^.h;
prepint(j,j+mid+1); h2:=root^.r^.l^.h;
if h1=h2 then l:=mid else r:=mid-1;
end; exit(l);
end;
procedure init;
var i,j:longint;
ch:char;
begin
e[0]:=1; for i:=1 to maxn do e[i]:=int64(e[i-1])*base and maxlongint;
fillchar(s,sizeof(s),0);
while not seekeoln do begin
inc(n); read(ch); s[n]:=ord(ch)-97;
end; readln; build(root,0,n+1);
end;
procedure work;
var i,j,k:longint;
ch:char;
t1:pnode;
begin
readln(m); while m>0 do begin dec(m);
read(ch); case ch of
'Q':begin
readln(i,j); writeln(lcp(i,j));
end;
'I':begin
read(i,ch); readln(ch); j:=ord(ch)-97;
prepint(i+1,i+2); new(root^.r^.l); with root^.r^.l^ do begin
v:=j; h:=j; size:=1; l:=null; r:=null; p:=root^.r;
end; inc(root^.size); inc(root^.r^.size);
rk(root^.r); rk(root); inc(n);
end;
'R':begin
read(i,ch); readln(ch); j:=ord(ch)-97;
t1:=select(root,i+1); t1^.v:=j; ssplay(t1,root);
end;
end;
end;
end;
begin
splay_init;
init;
work;
end.
折翼的fhqtreap
{$INLINE ON}
program bzoj1014;
type pnode=^tnode;
tnode=record
v:byte;
h1,p,size:longint;
l,r:pnode;
end;
const maxint=longint($3f3f3f3f);
mo1=int64(1325000071);
maxn=150017;
base=int64(26);
var root,null:pnode;
e1,e2:array[0..maxn] of longint;
s:array[0..maxn] of byte;
n,m,cq:longint;
procedure treap_init;
begin
new(null); with null^ do begin
v:=0; h1:=0; p:=maxint; size:=0; l:=null; r:=null;
end; root:=null;
end;
procedure rk(var i:pnode); inline;
begin with i^ do begin
h1:=(int64(l^.h1)*int64(e1[r^.size+1])+int64(v)*int64(e1[r^.size])+int64(r^.h1)) mod mo1;
end;
end;
function merge(i,j:pnode):pnode;
begin
if i=null then begin rk(j); exit(j); end;
if j=null then begin rk(i); exit(i); end;
if i^.p<j^.p then begin
inc(i^.size,j^.size); i^.r:=merge(i^.r,j); rk(i); exit(i);
end else begin
inc(j^.size,i^.size); j^.l:=merge(i,j^.l); rk(j); exit(j);
end;
end;
procedure split(i:pnode;j:longint;var t1,t2:pnode);
begin
if i=null then begin rk(i); t1:=null; t2:=null; end
else if j<=i^.l^.size then begin
dec(i^.size,j); split(i^.l,j,t1,t2); i^.l:=t2; t2:=i;
end else begin
i^.size:=j; split(i^.r,j-i^.l^.size-1,t1,t2); i^.r:=t1; t1:=i;
end; rk(i);
end;
procedure build(var i:pnode;idf,l,r:longint);
var mid:longint;
begin
mid:=(l+r)>>1; new(i); i^.v:=s[mid]; i^.size:=r-l+1; i^.p:=idf;
if l<mid then build(i^.l,idf<<1, l,mid-1) else i^.l:=null;
if r>mid then build(i^.r,idf<<1+1,mid+1,r) else i^.r:=null;
rk(i);
end;
function lcp(i,j:longint):longint;
var k,l,r,mid,h11,h21:longint;
t1,t2,t3:pnode;
begin
if i>j then begin k:=i; i:=j; j:=k; end;
l:=0; r:=n-j+1; while l<>r do begin
mid:=(l+r)>>1+1;
split(root,i-1,t1,t2); split(t2,mid,t2,t3);
h11:=t2^.h1;
root:=merge(merge(t1,t2),t3);
split(root,j-1,t1,t2); split(t2,mid,t2,t3);
h21:=t2^.h1;
root:=merge(merge(t1,t2),t3);
if (h11=h21) then l:=mid else r:=mid-1;
end; exit(l);
end;
procedure init;
var i,j:longint;
ch:char;
begin
e1[0]:=1; e2[0]:=1; for i:=1 to maxn do
e1[i]:=int64(e1[i-1])*base mod mo1;
while not seekeoln do begin
inc(n); read(ch); s[n]:=ord(ch)-96;
end; readln; build(root,1,1,n);
end;
procedure work;
var i,j:longint;
ch:char;
t1,t2,t3:pnode;
begin
readln(m); while m>0 do begin dec(m);
read(ch); case ch of
'Q':begin
readln(i,j); writeln(lcp(i,j));
end;
'R':begin
read(i,ch); readln(ch); j:=ord(ch)-96;
split(root,i-1,t1,t2); split(t2,1,t2,t3); t2^.v:=j;
root:=merge(merge(t1,t2),t3);
end;
'I':begin
read(i,ch); readln(ch); j:=ord(ch)-96; inc(n);
split(root,i,t1,t3); new(t2); with t2^ do begin
v:=j; p:=random(maxint); size:=1; l:=null; r:=null;
end; root:=merge(merge(t1,t2),t3);
end;
end;
end;
end;
begin
treap_init;
init;
work;
end.
2021年10月30日 12:43
On this website, you may get Model Papers 2022 in pdf format for students in classes 9th, 10th, 11th, and 12th for all subjects. Below are download links for Model Paper 2022 all Indian education boards. These papers were developed by Model Papers 2022 and are hosted on their official website. These question papers will assist you in achieving higher rankings and scores on the Board test.
2022年5月04日 15:25
Recently, Bihar School Examination Board has announced to release of Bihar 11th Blueprint 2023 in the month of April. As we know that, Every student who has given the 11thulation exam in Bihar is Bihar 1st Inter Blueprint 2023 keenly waiting for Bihar Board 1st Intermediate Latest Blueprint 2023. Right Now, all of them are in the search of the BSEB 1st Intermediate Marking Scheme 2023
2023年6月27日 18:21
Our reporting team plans to provide the Education & Recruitment Update for all age groups and to present the actual picture of recent events through inside coverage. Our goal is to meet the needs of people of sample-paper.com all ages by publishing news categorised as General, Political, Crime, Sports, Entertainment, Education, and World News.