2011-0050
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
给一个初始长度小于1e5的字符串，有4个操作或询问：
1：Reverse a b： 把a到b的字符反转
2：Modify p c ： 把p字符修改为c
3：Lcp a b ： 求第a个字符开始的后缀，与第b个字符开始的后缀的最长公共前缀的长度
4：Palindrome ：求整个字符串的最长回文子串（此询问不超过10次）
首先要支持反转操作和修改操作，可以用块状链表或Spaly。
以Splay为例，每个节点除了常规的lchild指针，rchild指针，parent指针（如果写自定向下Splay可以省略），size域，
还需要储存反转标记，为了求Lcp，还要有以某节点为根的树对应的字符串的hash值，同时兼顾反转操作，还要有对应反向字符串的hash值
这样在Splay树的向下查找时，下传反转标记，对换hash值（如果有反转标记）。求Lcp可以二分长度，比较hash值是否相同。这样求Lcp复杂度就是O(log n × log n)
,修改O(log n);反转也是 O(log n)。
至于回文字串，可以取出所有字符，用O(n)的Manacher算法，因为次数不多，可以接受。
{{{
#define ULL unsigned long long
#define HashMOD 2147483647l
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef char ktype;
struct SplayNode{
SplayNode *l,*r,*p;
ktype k;
unsigned sz,hash,rhash;bool rev;
int key(){return rev?rhash: hash;}
int rkey(){return rev? hash:rhash;}
};
typedef SplayNode* node;
SplayNode NILnode;
const node NIL = &NILnode;
const int MaxOnline = 100000+ 20 ;
SplayNode T[MaxOnline];
unsigned PN[MaxOnline];//for hash
node memptr;
struct Splay{
node sroot;
static void Initialize(){//once and only once before all
NIL->sz=NIL->hash=NIL->rhash=0;
NIL->l=NIL->r=NIL->p= &*NIL;
NIL->rev= false;
memptr= &T[0];
PN[0]=1;ULL t=1;
for(int i= 1; i< MaxOnline;++i){
T[i-1].r = T + i;
t*=27;if(t>HashMOD)t%=HashMOD;
PN[i] =unsigned(t);
}
T[MaxOnline-1].r = NIL;
}
node newnode(const node &p,const ktype& kk){
node tmp=memptr;memptr=memptr->r;
if(tmp!=NIL){
tmp->p = p;
tmp->k = kk;
tmp->hash = tmp ->rhash = kk;
tmp->l=tmp->r=NIL;
tmp->sz=1;
tmp->rev= false;
return tmp;
}else perror("OUT OF MEMORY");
}
void freenode(const node& xx){if(xx!=NIL){xx->r=memptr;memptr=xx;}}
void freewhole(const node& xx){
if(xx->l!=NIL)freewhole(xx->l);
if(xx->r!=NIL)freewhole(xx->r);
freenode(xx);
}
Splay(){sroot=NIL;}
~Splay(){ if(sroot->sz>5000)shrink(sroot,8);freewhole(sroot);}
void clear(){if(sroot->sz>5000)shrink(sroot,8);freewhole(sroot);sroot=NIL;}
void revnode(const node& x){
if(x!=NIL)x->rev=!x->rev;
}
void pushdown(const node& x){
if(x->rev){
x->rev=false;
revnode(x->l);
revnode(x->r);
std::swap(x->l,x->r);
std::swap(x->hash,x->rhash);
}
}
void update(const node& x){
pushdown(x);
int lsz =x->l->sz, rsz =x->r->sz;
x->sz= lsz + rsz +1;
x-> hash =(unsigned )( (x->l-> key() * (ULL)PN[rsz+1] + x->k *(ULL)PN[rsz] + x->r-> key())% HashMOD);
x->rhash =(unsigned )( (x->r->rkey() * (ULL)PN[lsz+1] + x->k *(ULL)PN[lsz] + x->l->rkey())% HashMOD);
}
void zig(node x){
node y=x->p;
y->l=x->r;if(x->r!=NIL)x->r->p=y;
x->p=y->p;
if(x->p!=NIL){
if(x->p->l==y)x->p->l = x;
else x->p ->r=x;
}x->r=y;y->p=x;
update(y);
update(x);
}
void zag(node y){
node x = y->p;
x->r=y->l;if(y->l!=NIL)y->l->p=x;
y->p=x->p;
if(y->p!=NIL){
if(y->p->l==x)y->p->l = y;
else y->p ->r=y;
}y->l=x;x->p=y;
update(x);
update(y);
}
void splay(node x,node rt){
node xp;
while(x->p!=rt){
xp=x->p;
if(xp->p == rt){
if(x == xp->l)zig(x);
else zag(x);
}else if(xp->p->l== xp){
if(xp->l==x){ //LL
zig(xp);zig(x);
}else{ //LR
zag(x);zig(x);
}
}else{
if(xp->r==x){ // RR
zag(xp);zag(x);
}else{ //RL
zig(x);zag(x);
}
}
}
if(rt ==NIL)sroot=x;
}
node rank(int k,node t){//start from 1 2 3 .. in Splay node t
//assert(k<=t->sz);
node tr= t->p;
while(k){
pushdown(t);
if(k<=t->l->sz)
t=t->l;
else{
k-=t->l->sz;
if(--k)t=t->r;
else break;
}
}
splay(t,tr);
return t;
}
void insert(int pos,const ktype& kk){// after insert, it's in pos+1 in squence
if(sroot==NIL){sroot= newnode(NIL,kk);return;}
node t= sroot;
while(pos || t->l!=NIL){
pushdown(t);
t->sz++;//
if(pos<=t->l->sz)t=t->l;
else{
pos-=t->l->sz+1;
if(t->r!=NIL)t=t->r;
else{
t->r = newnode(t,kk);
splay(t->r,NIL);
return;
}
}
}
t->l=newnode(t,kk);
splay(t->l,NIL);
}
void modify(int pos,const ktype& kk){
rank(pos,sroot);
sroot->k = kk;
update(sroot);
}
node gather(int l,int r){//[l,r] l<=r;
if(l>r)return NIL;
if(l==1){
if(r==sroot->sz)return sroot;
else return rank(r+1,sroot)->l;
}else
if(r==sroot ->sz)return rank(l-1,sroot)->r;
else{
rank(l-1,sroot);
return rank(r-l+2,sroot->r)->l;
}
}
node join(node x,node y){
x->p=NIL;y->p=NIL;
if(x==NIL)return y;
if(y==NIL)return x;
pushdown(x);
while(x->r!=NIL){x=x->r;pushdown(x);}
splay(x,NIL);
x->r=y;
y->p=x;update(x);
return x;
}
void reverse(int l,int r){
node t=gather(l,r);if(l<r)revnode(t);pushdown(t);
splay(t,NIL);
}
void erase(int l,int r){
node t=gather(l,r);
freewhole(t);
splay(t->p,NIL);
}
void erase(int k){
rank(k,sroot);
node tmp= sroot;
sroot =join(sroot ->l,sroot->r);
freenode(tmp);
}
void shrink(node x,int h){
if(x->sz<8 || !h)return;
x=rank((x->sz+1)>>1,x);
shrink(x->l,h-1);
shrink(x->r,h-1);
}
void getwhole(node x,ktype* &p){pushdown(x);
if(x->sz>100)x=rank((x->sz+1)>>1,x);
if(x->l!=NIL)getwhole(x->l,p);
*p++= x->k /*+96*/;
*p++='#';
if(x->r!=NIL)getwhole(x->r,p);
}
};
#include<cstring>
#include<cctype>
#include<algorithm>
int getnum(){
static char c;
while(!isdigit(c=getchar()));
int t=0;
do t=t*10+c-48;while(isdigit(c=getchar()));
return t;
}
char s[MaxOnline*2],c,*p,*q;
int F[MaxOnline*2];
int M,n,i,l,r,m,a,b;
Splay sp;
int main(){
Splay::Initialize();
while(gets(s),scanf("%d",&M)==1){
getchar();
n=strlen(s);
sp.clear();
for(i=0;i<n;++i)sp.insert(i,s[i] - 96);
while(M--){
switch(getchar()){
case 'R': l= getnum();r=getnum();
sp.reverse(l,r);
break;
case 'M':a=getnum();do c= getchar();while(isspace(c));
sp.modify(a,c-96);
getchar();//skip \n
break;
case 'L':
a = getnum();
b = getnum();
l =0; r=std::min(n-a,n-b)+2;
while(l+1<r){
m = (l+r)>>1;
node t = sp.gather(a,a+m-1);
unsigned h1=t->key();
unsigned h2=t->rkey();
t= sp.gather(b,b+m-1);
if(h1==t->key()&&h2==t->rkey())l= m;
else r= m;
}
printf("%d\n",l);
break;
case 'P':
s[0]='!';s[1]='#';p=s+2;
sp.getwhole(sp.sroot,p);
*p =0;//puts(s);
F[0]=1;
r=1;m=0;l=n*2+1; a=0;
for(int i=1;i<=l;++i){
int &fi=F[i];
if(r>i)fi=std::min(F[m*2-i],r-i);else fi=1;
p=s+i-fi;q=s+i+fi;
for(;*p-- ==*q++;++fi);
if(i+fi>r){r=i+fi;m=i;}
if(a<fi)a=fi;//b=i;}
}
printf("%d\n",a-1);
while(getchar()!='\n');
break;
}
}
}
return 0;
}
}}}
[by ZhouYuChen]给一个初始长度小于1e5的字符串，有4个操作或询问：
1：Reverse a b： 把a到b的字符反转
2：Modify p c ： 把p字符修改为c
3：Lcp a b ： 求第a个字符开始的后缀，与第b个字符开始的后缀的最长公共前缀的长度
4：Palindrome ：求整个字符串的最长回文子串（此询问不超过10次）
首先要支持反转操作和修改操作，可以用块状链表或Spaly。
以Splay为例，每个节点除了常规的lchild指针，rchild指针，parent指针（如果写自定向下Splay可以省略），size域，
还需要储存反转标记，为了求Lcp，还要有以某节点为根的树对应的字符串的hash值，同时兼顾反转操作，还要有对应反向字符串的hash值
这样在Splay树的向下查找时，下传反转标记，对换hash值（如果有反转标记）。求Lcp可以二分长度，比较hash值是否相同。这样求Lcp复杂度就是O(log n × log n)
,修改O(log n);反转也是 O(log n)。
至于回文字串，可以取出所有字符，用O(n)的Manacher算法，因为次数不多，可以接受。
#define ULL unsigned long long
#define HashMOD 2147483647l
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef char ktype;
struct SplayNode{
SplayNode *l,*r,*p;
ktype k;
unsigned sz,hash,rhash;bool rev;
int key(){return rev?rhash: hash;}
int rkey(){return rev? hash:rhash;}
};
typedef SplayNode* node;
SplayNode NILnode;
const node NIL = &NILnode;
const int MaxOnline = 100000+ 20 ;
SplayNode T[MaxOnline];
unsigned PN[MaxOnline];//for hash
node memptr;
struct Splay{
node sroot;
static void Initialize(){//once and only once before all
NIL->sz=NIL->hash=NIL->rhash=0;
NIL->l=NIL->r=NIL->p= &*NIL;
NIL->rev= false;
memptr= &T[0];
PN[0]=1;ULL t=1;
for(int i= 1; i< MaxOnline;++i){
T[i-1].r = T + i;
t*=27;if(t>HashMOD)t%=HashMOD;
PN[i] =unsigned(t);
}
T[MaxOnline-1].r = NIL;
}
node newnode(const node &p,const ktype& kk){
node tmp=memptr;memptr=memptr->r;
if(tmp!=NIL){
tmp->p = p;
tmp->k = kk;
tmp->hash = tmp ->rhash = kk;
tmp->l=tmp->r=NIL;
tmp->sz=1;
tmp->rev= false;
return tmp;
}else perror("OUT OF MEMORY");
}
void freenode(const node& xx){if(xx!=NIL){xx->r=memptr;memptr=xx;}}
void freewhole(const node& xx){
if(xx->l!=NIL)freewhole(xx->l);
if(xx->r!=NIL)freewhole(xx->r);
freenode(xx);
}
Splay(){sroot=NIL;}
~Splay(){ if(sroot->sz>5000)shrink(sroot,8);freewhole(sroot);}
void clear(){if(sroot->sz>5000)shrink(sroot,8);freewhole(sroot);sroot=NIL;}
void revnode(const node& x){
if(x!=NIL)x->rev=!x->rev;
}
void pushdown(const node& x){
if(x->rev){
x->rev=false;
revnode(x->l);
revnode(x->r);
std::swap(x->l,x->r);
std::swap(x->hash,x->rhash);
}
}
void update(const node& x){
pushdown(x);
int lsz =x->l->sz, rsz =x->r->sz;
x->sz= lsz + rsz +1;
x-> hash =(unsigned )( (x->l-> key() * (ULL)PN[rsz+1] + x->k *(ULL)PN[rsz] + x->r-> key())% HashMOD);
x->rhash =(unsigned )( (x->r->rkey() * (ULL)PN[lsz+1] + x->k *(ULL)PN[lsz] + x->l->rkey())% HashMOD);
}
void zig(node x){
node y=x->p;
y->l=x->r;if(x->r!=NIL)x->r->p=y;
x->p=y->p;
if(x->p!=NIL){
if(x->p->l==y)x->p->l = x;
else x->p ->r=x;
}x->r=y;y->p=x;
update(y);
update(x);
}
void zag(node y){
node x = y->p;
x->r=y->l;if(y->l!=NIL)y->l->p=x;
y->p=x->p;
if(y->p!=NIL){
if(y->p->l==x)y->p->l = y;
else y->p ->r=y;
}y->l=x;x->p=y;
update(x);
update(y);
}
void splay(node x,node rt){
node xp;
while(x->p!=rt){
xp=x->p;
if(xp->p == rt){
if(x == xp->l)zig(x);
else zag(x);
}else if(xp->p->l== xp){
if(xp->l==x){ //LL
zig(xp);zig(x);
}else{ //LR
zag(x);zig(x);
}
}else{
if(xp->r==x){ // RR
zag(xp);zag(x);
}else{ //RL
zig(x);zag(x);
}
}
}
if(rt ==NIL)sroot=x;
}
node rank(int k,node t){//start from 1 2 3 .. in Splay node t
//assert(k<=t->sz);
node tr= t->p;
while(k){
pushdown(t);
if(k<=t->l->sz)
t=t->l;
else{
k-=t->l->sz;
if(--k)t=t->r;
else break;
}
}
splay(t,tr);
return t;
}
void insert(int pos,const ktype& kk){// after insert, it's in pos+1 in squence
if(sroot==NIL){sroot= newnode(NIL,kk);return;}
node t= sroot;
while(pos || t->l!=NIL){
pushdown(t);
t->sz++;//
if(pos<=t->l->sz)t=t->l;
else{
pos-=t->l->sz+1;
if(t->r!=NIL)t=t->r;
else{
t->r = newnode(t,kk);
splay(t->r,NIL);
return;
}
}
}
t->l=newnode(t,kk);
splay(t->l,NIL);
}
void modify(int pos,const ktype& kk){
rank(pos,sroot);
sroot->k = kk;
update(sroot);
}
node gather(int l,int r){//[l,r] l<=r;
if(l>r)return NIL;
if(l==1){
if(r==sroot->sz)return sroot;
else return rank(r+1,sroot)->l;
}else
if(r==sroot ->sz)return rank(l-1,sroot)->r;
else{
rank(l-1,sroot);
return rank(r-l+2,sroot->r)->l;
}
}
node join(node x,node y){
x->p=NIL;y->p=NIL;
if(x==NIL)return y;
if(y==NIL)return x;
pushdown(x);
while(x->r!=NIL){x=x->r;pushdown(x);}
splay(x,NIL);
x->r=y;
y->p=x;update(x);
return x;
}
void reverse(int l,int r){
node t=gather(l,r);if(l<r)revnode(t);pushdown(t);
splay(t,NIL);
}
void erase(int l,int r){
node t=gather(l,r);
freewhole(t);
splay(t->p,NIL);
}
void erase(int k){
rank(k,sroot);
node tmp= sroot;
sroot =join(sroot ->l,sroot->r);
freenode(tmp);
}
void shrink(node x,int h){
if(x->sz<8 || !h)return;
x=rank((x->sz+1)>>1,x);
shrink(x->l,h-1);
shrink(x->r,h-1);
}
void getwhole(node x,ktype* &p){pushdown(x);
if(x->sz>100)x=rank((x->sz+1)>>1,x);
if(x->l!=NIL)getwhole(x->l,p);
*p++= x->k /*+96*/;
*p++='#';
if(x->r!=NIL)getwhole(x->r,p);
}
};
#include<cstring>
#include<cctype>
#include<algorithm>
int getnum(){
static char c;
while(!isdigit(c=getchar()));
int t=0;
do t=t*10+c-48;while(isdigit(c=getchar()));
return t;
}
char s[MaxOnline*2],c,*p,*q;
int F[MaxOnline*2];
int M,n,i,l,r,m,a,b;
Splay sp;
int main(){
Splay::Initialize();
while(gets(s),scanf("%d",&M)==1){
getchar();
n=strlen(s);
sp.clear();
for(i=0;i<n;++i)sp.insert(i,s[i] - 96);
while(M--){
switch(getchar()){
case 'R': l= getnum();r=getnum();
sp.reverse(l,r);
break;
case 'M':a=getnum();do c= getchar();while(isspace(c));
sp.modify(a,c-96);
getchar();//skip \n
break;
case 'L':
a = getnum();
b = getnum();
l =0; r=std::min(n-a,n-b)+2;
while(l+1<r){
m = (l+r)>>1;
node t = sp.gather(a,a+m-1);
unsigned h1=t->key();
unsigned h2=t->rkey();
t= sp.gather(b,b+m-1);
if(h1==t->key()&&h2==t->rkey())l= m;
else r= m;
}
printf("%d\n",l);
break;
case 'P':
s[0]='!';s[1]='#';p=s+2;
sp.getwhole(sp.sroot,p);
*p =0;//puts(s);
F[0]=1;
r=1;m=0;l=n*2+1; a=0;
for(int i=1;i<=l;++i){
int &fi=F[i];
if(r>i)fi=std::min(F[m*2-i],r-i);else fi=1;
p=s+i-fi;q=s+i+fi;
for(;*p-- ==*q++;++fi);
if(i+fi>r){r=i+fi;m=i;}
if(a<fi)a=fi;//b=i;}
}
printf("%d\n",a-1);
while(getchar()!='\n');
break;
}
}
}
return 0;
}
[by ZhouYuChen]