题解:用平衡树维护hash 二分答案即可
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll unsigned long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
ll sum[MAXN],key[MAXN],tag[MAXN];
int ch[MAXN][2],pre[MAXN],rt,cnt,sz[MAXN],n;
char s[MAXN];
void Treavel(int x)
{
if(x)
{
// cout<<x<<endl;
Treavel(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d key=%2llu sum=%2llu
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x],sum[x]);
Treavel(ch[x][1]);
}
}
void debug(int rp)
{
printf("root:%d
",rp);
Treavel(rp);
}
ll ksm(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;b=b>>1;
}
return ans;
}
void newnode(int &x,ll vul,int fa){
x=++cnt;
ch[x][0]=ch[x][1]=0;pre[x]=fa;
sum[x]=key[x]=vul;tag[x]=1;sz[x]=1;
}
void cheng(int x,ll t){
key[x]*=t;sum[x]*=t;tag[x]*=t;
}
void push(int x){
if(tag[x]==1)return ;
cheng(ch[x][0],tag[x]);
cheng(ch[x][1],tag[x]);
tag[x]=1;
}
void up(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
}
void P(int x){
if(pre[x])P(pre[x]);
push(x);
}
void rotate(int x,int kind){
int y=pre[x];
pre[ch[x][kind]]=y;ch[y][!kind]=ch[x][kind];
if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
up(y);up(x);
}
void splay(int x,int goal){
P(x);
while(pre[x]!=goal){
if(pre[pre[x]]==goal)rotate(x,ch[pre[x]][0]==x);
else{
int y=pre[x];int kind=ch[pre[y]][0]==y;
if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);
else rotate(y,kind),rotate(x,kind);
}
}
if(goal==0)rt=x;
up(x);
}
int find1(int x,int t){
push(x);
if(sz[ch[x][0]]+1==t)return x;
else if(sz[ch[x][0]]>=t)return find1(ch[x][0],t);
else return find1(ch[x][1],t-sz[ch[x][0]]-1);
}
ll operator1(int x,int y){
splay(find1(rt,x),0);
splay(find1(rt,y+2),rt);
return sum[ch[ch[rt][1]][0]];
}
bool check(int x,int y,int t){
ll t1=operator1(x,x+t-1);
t1*=ksm(131,y-x);
ll t2=operator1(y,y+t-1);
return (t1==t2);
}
int slove(int x,int y){
if(x>y)swap(x,y);
int t=sz[rt]-2;
int l=1;int r=min(t-x+1,t-y+1);int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(x,y,mid))ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
void operator2(int x,ll t){
splay(find1(rt,x+1),0);
key[rt]=ksm(131,x)*t;
up(rt);
}
void operator3(int x,ll t){
splay(find1(rt,x+1),0);splay(find1(rt,x+2),rt);
newnode(ch[ch[rt][1]][0],ksm(131,x+1)*t,ch[rt][1]);
up(ch[rt][1]);up(rt);
splay(cnt,0);
cheng(ch[rt][1],131);
}
void built(int &x,int l,int r,int fa){
if(l>r)return ;
int mid=(l+r)>>1;
newnode(x,ksm(131,mid)*s[mid],fa);
built(ch[x][0],l,mid-1,x);
built(ch[x][1],mid+1,r,x);
up(x);
}
void inte(){
newnode(rt,0,0);
newnode(ch[rt][1],0,rt);
built(ch[ch[rt][1]][0],1,n,ch[rt][1]);
up(ch[rt][1]);up(rt);
// debug(rt);
//cout<<rt<<" "<<sz[rt]<<endl;
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
inte();char ch,ct;
int m=read();int x,y;
while(m--){
scanf(" %c",&ch);x=read();
if(ch=='Q')y=read(),printf("%d
",slove(x,y));
else if(ch=='R')scanf(" %c",&ct),operator2(x,ct);
else scanf(" %c",&ct),operator3(x,ct);
}
return 0;
}
1014: [JSOI2008]火星人prefix
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 9352 Solved: 3020
[Submit][Status][Discuss]
Description
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串
，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。
Input
第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操
作有3种，如下所示
1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。
2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字
符串长度。
3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字
符串开头插入。限制：x不超过当前字符串长度
Output
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
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
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
1
0
2
1