BZOJ2105: 增强型LCP

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
",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         else
114         {
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
",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         else
181         {
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