首页 > 代码库 > BZOJ2105: 增强型LCP

BZOJ2105: 增强型LCP

2024-08-04 23:44:16   209人阅读

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

Sample Output

2
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
代码：
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 1000000+5 26  27 #define maxm 500+100 28  29 #define eps 1e-10 30  31 #define ull unsigned long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44 #define base 13131 45  46 using namespace std; 47  48 inline int read() 49  50 { 51  52     int x=0,f=1;char ch=getchar(); 53  54     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 55  56     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 57  58     return x*f; 59  60 } 61 int n,m,q; 62 ull a[maxn],b[maxn]; 63 char ch[maxn]; 64 string s; 65 inline void rebuild() 66 { 67     n=s.length(); 68     b[n-1]=s[n-1]; 69     for3(i,n-2,0)b[i]=b[i+1]*base+(ull)s[i]; 70 } 71 inline ull get(int x,int l){return b[x]-b[x+l]*a[l];} 72  73 int main() 74  75 { 76  77     freopen("input.txt","r",stdin); 78  79     freopen("output.txt","w",stdout); 80  81     n=read();q=read(); 82     scanf("%s",ch);s=ch; 83     a[0]=1; 84     for1(i,maxn-1)a[i]=a[i-1]*(ull)base; 85     rebuild(); 86     while(q--) 87     { 88         scanf("%s",ch); 89         if(ch[0]==‘L‘) 90         { 91             int x=read()-1,y=read()-1,l=0,r=n-y; 92             while(l<=r) 93             { 94                 int mid=(l+r)>>1; 95                 if(get(x,mid)==get(y,mid))l=mid+1;else r=mid-1; 96             } 97             printf("%d\n",r); 98         } 99         else if(ch[0]==‘A‘)100         {101             int x=read()-1;102             scanf("%s",ch);103             s.insert(x,ch);104             rebuild();105         }106         else if(ch[0]==‘C‘)107         {108             int x=read()-1,y=read()-1;109             scanf("%s",ch);110             for2(i,x,y)s[i]=ch[i-x];111             rebuild();112         }113         else114         {115             int x=read()-1,y=read()-1;116             s.erase(x,y-x+1);117             rebuild();118         }119     }120 121     return 0;122 123 }
View Code

再贴一下splay的代码，sad story。。。

代码：

  1 #include<cstdio>  2    3 #include<cstdlib>  4    5 #include<cmath>  6    7 #include<cstring>  8    9 #include<algorithm> 10   11 #include<iostream> 12   13 #include<vector> 14   15 #include<map> 16   17 #include<set> 18   19 #include<queue> 20   21 #include<string> 22   23 #define inf 1000000000 24   25 #define maxn 1000000+5 26   27 #define maxm 500+100 28   29 #define eps 1e-10 30   31 #define ull unsigned long long 32   33 #define pa pair<int,int> 34   35 #define for0(i,n) for(int i=0;i<=(n);i++) 36   37 #define for1(i,n) for(int i=1;i<=(n);i++) 38   39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40   41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42   43 #define mod 1000000007 44   45 using namespace std; 46   47 inline int read() 48   49 { 50   51     int x=0,f=1;char ch=getchar(); 52   53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54   55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56   57     return x*f; 58   59 } 60 int n,m,q,xx,yy,rt,tot,id[maxn],s[maxn],c[maxn][2],fa[maxn]; 61 ull v[maxn],sum[maxn],hash[maxn]; 62 char st[maxn]; 63 inline void pushup(int x) 64 { 65     if(!x)return; 66     int l=c[x][0],r=c[x][1]; 67     s[x]=s[l]+s[r]+1; 68     sum[x]=sum[r]+v[x]*hash[s[r]]+sum[l]*hash[s[r]+1]; 69     //if(x==7)cout<<x<<‘ ‘<<l<<‘ ‘<<r<<‘ ‘<<sum[x]<<‘ ‘<<sum[r]<<‘ ‘<<s[r]<<‘ ‘<<v[x]<<endl; 70 } 71 inline void rotate(int x,int &k) 72 { 73     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 74     if(y!=k)c[z][c[z][1]==y]=x;else k=x; 75     //cout<<x<<‘ ‘<<y<<‘ ‘<<z<<endl; 76     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 77     c[y][l]=c[x][r];c[x][r]=y; 78     pushup(y);pushup(x); 79 } 80 inline void splay(int x,int &k) 81 { 82     while(x!=k) 83     { 84         int y=fa[x],z=fa[y]; 85         if(y!=k) 86         { 87             if((c[z][0]==y)^(c[y][0]==x))rotate(x,k);else rotate(y,k); 88         } 89         rotate(x,k); 90     } 91 } 92 void build(int l,int r,int f) 93 { 94     if(l>r)return; 95     int mid=(l+r)>>1,x=id[mid]=++tot,y=fa[x]=id[f]; 96     v[x]=st[mid];c[y][mid>f]=x; 97     if(l==r) 98     { 99        sum[x]=v[x];s[x]=1;100        return;101     }  102     build(l,mid-1,mid);build(mid+1,r,mid);103     pushup(x);104     //cout<<x<<‘ ‘<<c[x][0]<<‘ ‘<<c[x][1]<<‘ ‘<<sum[x]<<endl;105 }106 inline int find(int x,int k)107 {108     int l=c[x][0],r=c[x][1];109     if(s[l]+1==k)return x;110     else if(s[l]>=k)return find(l,k);111     else return find(r,k-s[l]-1);112 }113 inline void split(int l,int r)114 {115     xx=find(rt,l);yy=find(rt,r);116     splay(xx,rt);splay(yy,c[xx][1]);117 }118 inline void print(int x)119 {120     if(!x)return;121     //cout<<x<<‘ ‘<<c[x][0]<<‘ ‘<<c[x][1]<<"AAAAAAAAAAA"<<endl;122     print(c[x][0]);123     cout<<(char)v[x];124     print(c[x][1]);125 }126 inline ull query(int l,int r)127 {128     split(l,r+2);129     //cout<<l<<‘ ‘<<r<<endl;130     //cout<<l<<‘ ‘<<r<<‘ ‘<<c[y][0]<<‘ ‘<<sum[c[y][0]]<<‘ ‘<<v[c[y][0]]<<endl;131     //print(c[yy][0]);cout<<endl;132     //cout<<sum[c[yy][0]]<<endl;133     return sum[c[yy][0]];134 }135  136 int main()137  138 {139  140     n=read();q=read();141     hash[0]=1;142     for1(i,maxn-1)hash[i]=hash[i-1]*(ull)150;143     scanf("%s",st+2);m=strlen(st+2);144     st[1]=st[m+1+1]=‘a‘;145     build(1,m+2,0);rt=id[(1+m+2)>>1];146     //cout<<id[2]<<‘ ‘<<id[3]<<endl;147     while(q--)148     {149         char ch[10];scanf("%s",ch);150         //cout<<"AAAAAAAAAA"<<endl;151         if(ch[0]==‘L‘)152         {153             int a=read(),b=read(),l=0,r=s[rt]-2-b+1;154             while(l<=r)155             {156                 int mid=(l+r)>>1;157                 //cout<<l<<‘ ‘<<mid<<‘ ‘<<r<<endl;158                 if(query(a,a+mid-1)==query(b,b+mid-1))l=mid+1;else r=mid-1;159             }160             printf("%d\n",r);161         }162         else if(ch[0]==‘A‘)163         {164             int a=read();//cout<<a<<endl;165             scanf("%s",st+1);m=strlen(st+1);166             build(1,m,0);167             split(a,a+1);168             fa[c[yy][0]=id[(1+m)>>1]]=yy;169             pushup(yy);pushup(xx);170         }171         else if(ch[0]==‘C‘)172         {173             int a=read(),b=read();174             scanf("%s",st+1);m=strlen(st+1);175             build(1,m,0);176             split(a,b+2);177             fa[c[yy][0]=id[(1+m)>>1]]=yy;178             pushup(yy);pushup(xx);179         }180         else181         {182             int a=read(),b=read();183             split(a,b+2);184             c[yy][0]=0;185             pushup(yy);pushup(xx);186         }187     }188  189     return 0;190  191 }
View Code

 

 

BZOJ2105: 增强型LCP


联系
我们