2105: 增强型LCP
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 366 Solved: 86
[Submit][Status]
Description
Input
Output
对于每个Lcp(a,b)操作输出最长公共前缀
Sample Input
47
abab
L 13
A 1 ab
L 1 3
C 56 cb
L 1 3
D 1 2
L 1 3
abab
L 13
A 1 ab
L 1 3
C 56 cb
L 1 3
D 1 2
L 1 3
Sample Output
2
4
2
0
4
2
0
HINT
Source
题解：
这题。。。
原来一直以为是个splay练手题，于是昨天来写。。。
2h没调出来，今天来了发现pushup写错了。。。T_T
然后就是狂T了。。。
看题解发现我们暴力重构写hash就行了，因为修改少，我也是醉了。。。
然后终于会了字符串的hash算法
我们另b[i]=si-sn的hash值，递推式b[i]=b[i+1]*base+s[i]
然后我们要得到从i开始的len长度的hash就是 b[i]-b[i+len]*a[len] a[len]表示base^len
还有c++的字符串问题
s,insert(pos,st) 表示在pos前插入st
s.erase(pos,len)表示从pos开始删除len的字符，包括pos
代码：
这题。。。
原来一直以为是个splay练手题，于是昨天来写。。。
2h没调出来，今天来了发现pushup写错了。。。T_T
然后就是狂T了。。。
看题解发现我们暴力重构写hash就行了，因为修改少，我也是醉了。。。
然后终于会了字符串的hash算法
我们另b[i]=si-sn的hash值，递推式b[i]=b[i+1]*base+s[i]
然后我们要得到从i开始的len长度的hash就是 b[i]-b[i+len]*a[len] a[len]表示base^len
还有c++的字符串问题
s,insert(pos,st) 表示在pos前插入st
s.erase(pos,len)表示从pos开始删除len的字符，包括pos
代码：
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 1000000+5 #define maxm 500+100 #define eps 1e-10 #define ull unsigned long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007
#define base 13131 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int n,m,q;
ull a[maxn],b[maxn];
char ch[maxn];
string s;
inline void rebuild()
{
n=s.length();
b[n-]=s[n-];
for3(i,n-,)b[i]=b[i+]*base+(ull)s[i];
}
inline ull get(int x,int l){return b[x]-b[x+l]*a[l];} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();q=read();
scanf("%s",ch);s=ch;
a[]=;
for1(i,maxn-)a[i]=a[i-]*(ull)base;
rebuild();
while(q--)
{
scanf("%s",ch);
if(ch[]=='L')
{
int x=read()-,y=read()-,l=,r=n-y;
while(l<=r)
{
int mid=(l+r)>>;
if(get(x,mid)==get(y,mid))l=mid+;else r=mid-;
}
printf("%d\n",r);
}
else if(ch[]=='A')
{
int x=read()-;
scanf("%s",ch);
s.insert(x,ch);
rebuild();
}
else if(ch[]=='C')
{
int x=read()-,y=read()-;
scanf("%s",ch);
for2(i,x,y)s[i]=ch[i-x];
rebuild();
}
else
{
int x=read()-,y=read()-;
s.erase(x,y-x+);
rebuild();
}
} return ; }
再贴一下splay的代码，sad story。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1000000+5
#define maxm 500+100
#define eps 1e-10
#define ull unsigned long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,q,xx,yy,rt,tot,id[maxn],s[maxn],c[maxn][],fa[maxn];
ull v[maxn],sum[maxn],hash[maxn];
char st[maxn];
inline void pushup(int x)
{
if(!x)return;
int l=c[x][],r=c[x][];
s[x]=s[l]+s[r]+;
sum[x]=sum[r]+v[x]*hash[s[r]]+sum[l]*hash[s[r]+];
//if(x==7)cout<<x<<' '<<l<<' '<<r<<' '<<sum[x]<<' '<<sum[r]<<' '<<s[r]<<' '<<v[x]<<endl;
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y!=k)c[z][c[z][]==y]=x;else k=x;
//cout<<x<<' '<<y<<' '<<z<<endl;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((c[z][]==y)^(c[y][]==x))rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
void build(int l,int r,int f)
{
if(l>r)return;
int mid=(l+r)>>,x=id[mid]=++tot,y=fa[x]=id[f];
v[x]=st[mid];c[y][mid>f]=x;
if(l==r)
{
sum[x]=v[x];s[x]=;
return;
}
build(l,mid-,mid);build(mid+,r,mid);
pushup(x);
//cout<<x<<' '<<c[x][0]<<' '<<c[x][1]<<' '<<sum[x]<<endl;
}
inline int find(int x,int k)
{
int l=c[x][],r=c[x][];
if(s[l]+==k)return x;
else if(s[l]>=k)return find(l,k);
else return find(r,k-s[l]-);
}
inline void split(int l,int r)
{
xx=find(rt,l);yy=find(rt,r);
splay(xx,rt);splay(yy,c[xx][]);
}
inline void print(int x)
{
if(!x)return;
//cout<<x<<' '<<c[x][0]<<' '<<c[x][1]<<"AAAAAAAAAAA"<<endl;
print(c[x][]);
cout<<(char)v[x];
print(c[x][]);
}
inline ull query(int l,int r)
{
split(l,r+);
//cout<<l<<' '<<r<<endl;
//cout<<l<<' '<<r<<' '<<c[y][0]<<' '<<sum[c[y][0]]<<' '<<v[c[y][0]]<<endl;
//print(c[yy][0]);cout<<endl;
//cout<<sum[c[yy][0]]<<endl;
return sum[c[yy][]];
}
int main()
{
n=read();q=read();
hash[]=;
for1(i,maxn-)hash[i]=hash[i-]*(ull);
scanf("%s",st+);m=strlen(st+);
st[]=st[m++]='a';
build(,m+,);rt=id[(+m+)>>];
//cout<<id[2]<<' '<<id[3]<<endl;
while(q--)
{
char ch[];scanf("%s",ch);
//cout<<"AAAAAAAAAA"<<endl;
if(ch[]=='L')
{
int a=read(),b=read(),l=,r=s[rt]--b+;
while(l<=r)
{
int mid=(l+r)>>;
//cout<<l<<' '<<mid<<' '<<r<<endl;
if(query(a,a+mid-)==query(b,b+mid-))l=mid+;else r=mid-;
}
printf("%d\n",r);
}
else if(ch[]=='A')
{
int a=read();//cout<<a<<endl;
scanf("%s",st+);m=strlen(st+);
build(,m,);
split(a,a+);
fa[c[yy][]=id[(+m)>>]]=yy;
pushup(yy);pushup(xx);
}
else if(ch[]=='C')
{
int a=read(),b=read();
scanf("%s",st+);m=strlen(st+);
build(,m,);
split(a,b+);
fa[c[yy][]=id[(+m)>>]]=yy;
pushup(yy);pushup(xx);
}
else
{
int a=read(),b=read();
split(a,b+);
c[yy][]=;
pushup(yy);pushup(xx);
}
}
return ;
}