Tag: splay, dichotomy, hash
subject
Description
Martians recently studied an operation: finding a common prefix for a string with two suffixes. For example, there is a string: madamimadam,
We label each character of this string: ordinal number: 1 234 567 899 1011 character m a d a m i m a d a m m m now,
The Martians define a function LCQ(x, y) to represent a string that begins with the Xth character in the string and the YTH character in the string.
The length of the common prefix of two strings. For example, LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 are studying the process of LCQ function.
In this connection, the Martians found that if all suffixes of the string were ordered, the LCQ function could be quickly calculated; similarly,
If the value of LCQ function is obtained, the suffix of the string can also be arranged quickly. Although the Martians have cleverly found a fast way to find LCQ functions
Algorithms, but reluctant to give up the Earth gave the Martians a difficult problem: while calculating LCQ functions, you can also change the string itself. speak specifically
You can change the value of a character in a string or insert a character at a certain position in the string. Earth people want to test, in this case
In the complex problem, whether Martians can get LCQ function value quickly.
Input
The first line gives the initial string. The second line is a non-negative integer M, representing the number of operations. The next M lines describe one operation per line. exercise
There are three kinds, as follows
1. Inquiry. Grammar: Qxy, x,y are all positive integers. Function: Calculate LCQ(x,y) limit: 1 <= x,y <= current string length.
2. Modification. Syntax: Rxd, x is a positive integer, d is a character. Function: Change the number x in the string to character d. Limitation: X does not exceed the current word
String length.
3. Insert: Grammar: Ixd, x is a non-negative integer, D is a character. Function: Insert the character d after the X character of the string, if x=0, then the word
Insert at the beginning of the string. Limitation: x does not exceed the current string length
Output
For each inquiry operation in the input file, you should output the corresponding answer. One answer, one line.
Sample Input
madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11
Sample Output
5
1
0
2
1
HINT
1. All strings are composed of lowercase letters from beginning to end.
2,M<=150,000
3. String length L satisfies L<=100,000 from beginning to end.
4. The number of inquiry operations should not exceed 10,000.
For data 1 and 2, the string length is not more than 1,000 from start to finish.
For data 3, 4, 5, there is no insertion operation.
Analysis
The first time I wrote splay balance tree, I debugged the code of Xuechang Huang for a long time. What should I do when the food dies?
Maintain strings with splay (assuming, of course, hash is spicy and everything can clam). Use dichotomy to find the answer when inquiring.
Each p value of hash is preprocessed, and the specific value of each character is written in the update function.
It's still very ether for equilibrium trees.
code
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define mod 19260817
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=150006;
int c[maxn][2],fa[maxn],id[maxn],size[maxn],v[maxn],h[maxn],p[maxn];
int n,m,root,sz;
char ch[maxn];
void update(int k)
{
int l=c[k][0],r=c[k][1];
size[k]=size[l]+size[r]+1;
h[k]=h[l]+(ll)v[k]*p[size[l]]%mod+(ll)p[size[l]+1]*h[r]%mod;
h[k]%=mod;
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;r=l^1;
if(y==k)k=x;
else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(y);update(x);
}
void splay(int x,int &k)
{
while(x!=k){
int y=fa[x],z=fa[y];
if(y!=k){
if(c[y][0]==x^c[z][0]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int k,int rank)//Searching rank in k's subtree
{
int l=c[k][0],r=c[k][1];
if(size[l]+1==rank)return k;
else if(size[l]>=rank)return find(l,rank);
else return find(r,rank-size[l]-1);
}
void insert(int k,int val)//Insert new nodes
{
int x=find(root,k+1),y=find(root,k+2);
splay(x,root);splay(y,c[x][1]);
int z=++sz;c[y][0]=z;fa[z]=y;v[z]=val;
update(z);update(y);update(x);
}
int query(int k,int val)//Suffixes denoting k
{
int x=find(root,k),y=find(root,k+val+1);
splay(x,root);splay(y,c[x][1]);
int z=c[y][0];
return h[z];
}
int solve(int x,int y)//Binary search for answers
{
int l=1,r=min(sz-x,sz-y)-1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(query(x,mid)==query(y,mid))l=mid+1,ans=mid;else r=mid-1;
}
return ans;
}
void build(int l,int r,int f)
{
if(l>r)return;
int now=id[l],last=id[f];
if(l==r){
v[now]=h[now]=ch[l]-'a'+1;
fa[now]=last;size[now]=1;
if(l<f)c[last][0]=now;else c[last][1]=now;
return;
}
int mid=(l+r)>>1;now=id[mid];
build(l,mid-1,mid);build(mid+1,r,mid);
v[now]=ch[mid]-'a'+1;fa[now]=last;update(now);
if(mid<f)c[last][0]=now;else c[last][1]=now;
}
int main()
{
scanf("%s",ch+2);
n=strlen(ch+2);
p[0]=1;
rep(i,1,maxn-2)p[i]=p[i-1]*37%mod;
rep(i,1,n+2)id[i]=i;
build(1,n+2,0);sz=n+2;root=(n+3)>>1;
m=read();
char s[2],d[2];
rep(i,1,m){
scanf("%s",s+1);
int x=read();
if(s[1]=='Q'){int y=read();printf("%d\n",solve(x,y));}
if(s[1]=='R'){
scanf("%s",d+1);
x=find(root,x+1);
splay(x,root);
v[root]=d[1]-'a'+1;
update(root);
}
if(s[1]=='I'){scanf("%s",d+1);insert(x,d[1]-'a'+1);}
}
return 0;
}