RT

写的是类似数列分块入门 6的分块解法，貌似有插入就会寄。

求调

Code：

#include<iostream>
#include<cmath>
#include<cstdio> 
#include<vector>
#include<algorithm>
#define int ull
using namespace std;
typedef unsigned long long ll;
typedef long long ull;
typedef pair<ull,ull> pr;
const ll jz=1e9+7;
struct node{
	ll val;
	int sz;
}hs[405];
string s;
int blo,n,m,l,r,mid;
string opt,tmp;
ll pows[100005];
ull ms,x,d,c[100005],cnt,N;
vector<ll> vc[405];
node merge(node x,node y){
	node ret;
	ret.val=x.val*pows[y.sz]+y.val;
	ret.sz=x.sz+y.sz;
	return ret;
}
node mknode(ll x){
	node ret;
	ret.sz=1;
	ret.val=x;
	return ret;
}
void gethash(int x){
	if(vc[x].empty()){
		return ;
	}
	node ret=mknode(vc[x][0]);
	for(int i=1;i<(ull)vc[x].size();i++){
		ret=merge(ret,mknode(vc[x][i]));
	}
	hs[x]=ret;
}
pr qry(ull x){
	int k=1ll;
	while(x>(ull)vc[k].size()){
		x-=vc[k].size();
		k++;
	}
	return {k,x-1};
}
void change(){
	N=0;
	for(int i=1;i<=ms;i++){
		for(int j=0;j<(ull)vc[i].size();j++){
			c[++N]=vc[i][j];
		}
		vc[i].clear();
	}
}
void rebuild(int f){
	if(f){
		change();
	}
	blo=int(sqrt(N));
	for(int i=1;i<=N;i++){
		vc[(i-1)/blo+1].push_back(c[i]);
	}
	ms=(N-1)/blo+1;
	for(int i=1;i<=ms;i++){
		gethash(i);
	}
}
void ins(){
	N++;
	if(!x){
		reverse(vc[1].begin(),vc[1].end());
		vc[1].push_back(d);
		reverse(vc[1].begin(),vc[1].end());
		gethash(1);
		if((ull)vc[1].size()>7*ms){
			rebuild(1);
		}
		return ;
	}
	pr ts=qry(x);
	vc[ts.first].insert(vc[ts.first].begin()+ts.second,d);
	gethash(ts.first);
	if((ull)vc[ts.first].size()>7*ms){
		rebuild(1);
	}
}
void modify(){
	pr ts=qry(x);
	vc[ts.first][ts.second]=d;
	gethash(ts.first);
}
node gethasher(ull l,ull r){
	node ret;
	ret.val=ret.sz=0;
	if(r-l==-1){
		return ret;
	}
	pr ts=qry(l),ts2=qry(r);
	ret=mknode(vc[ts.first][ts.second]);
	if(ts.first==ts2.first){
		for(int i=ts.second+1;i<=ts2.second;i++){
			ret=merge(ret,mknode(vc[ts.first][i]));
		}
		return ret;
	}
	for(int i=ts.second+1;i<(ull)vc[ts.first].size();i++){
		ret=merge(ret,mknode(vc[ts.first][i]));
	}
	for(int i=ts.first+1;i<ts2.first;i++){
		ret=merge(ret,hs[i]);
	}
	for(int i=0;i<=ts2.second;i++){
		ret=merge(ret,mknode(vc[ts2.first][i]));
	}
	return ret;
}
signed main(){
	//freopen("9.in","r",stdin);
	//freopen("9.out","w",stdout);
	cin>>s;
	cnt=N=n=s.length();
	pows[0]=1ll;
	for(int i=1;i<=100000;i++){
		pows[i]=pows[i-1ll]*jz;
	}
	for(int i=1;i<=n;i++){
		c[i]=s[i-1ll]-'a'+1ll;
	}
	rebuild(0);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>opt;
		if(opt=="Q"){
			cin>>x>>d;
			l=0;
			r=min(cnt-x+1,cnt-d+1);
			while(l<r){
				mid=(l+r+1ll)>>1ll;
				if(gethasher(x,x+mid-1ll).val==gethasher(d,d+mid-1ll).val){
					l=mid;
				}
				else{
					r=mid-1ll;
				}
			}
			cout<<l<<endl;
		}
		if(opt=="R"){
			cin>>x>>tmp;
			d=tmp[0]-'a'+1ll;
			modify();
		}
		if(opt=="I"){
			cnt++;
			cin>>x>>tmp;
			d=tmp[0]-'a'+1ll;
			ins();
		//	cout<<vc[qry(28101).first][qry(28101).second]<<endl; 
		}
	}
	return 0;
}