Sol
Splay+Hash+二分答案.
用Splay维护Hash,二分答案判断.
复杂度 \(O(nlog^2n)\)
PS:这题调了两个晚上因为没开long long.许久不写数据结构题感觉写完整个人都不好了...
感觉还是应该经常开几道数据结构题来毒自己.
Code
/**************************************************************
Problem: 1014
User: BeiYu
Language: C++
Result: Accepted
Time:6580 ms
Memory:9320 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std; typedef unsigned long long LL;
const int N = 200050;
#define lc(o) d[o].ch[0]
#define rc(o) d[o].ch[1]
#define f(o) d[o].f
#define h(o) d[o].h
#define v(o) d[o].v
#define s(o) d[o].s
#define mid ((l+r)>>1) //char *ps=(char *)malloc(N<<3);
inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; } LL p[N];char ch[N];
struct SplayTree{
struct Node{
int ch[2],f;
LL h,v;int s;
void Init(LL hh,LL vv,int ss){ h=hh,v=vv,s=ss,ch[0]=ch[1]=f=0; }
}d[N];
int rt,cnt; void PushUp(int o){
if(!o) return;
d[o].h=0;d[o].s=d[lc(o)].s+d[rc(o)].s+1;
h(o)=(LL)h(lc(o))+v(o)*p[s(lc(o))]+h(rc(o))*p[s(lc(o))+1];
// if(rc(o)!=0) h(o)=h(o)+h(rc(o));
// h(o)=h(o)+v(o)*p[d[rc(o)].s];
// if(lc(o)!=0) h(o)=h(o)+h(lc(o))*p[d[rc(o)].s+1];
}
void Build(int &o,int fa,int l,int r){
if(l>r) return;
o=++cnt;
d[o].Init(0,0,0);
if(ch[mid]>='a') d[o].v=ch[mid]-'a'+13;
f(o)=fa;
Build(lc(o),o,l,mid-1);
Build(rc(o),o,mid+1,r);
PushUp(o);
}
// int Build(int l,int r,int fa){
// if(l==r){
// d[l].Init(0,0,0);
// if(ch[l]>='a') d[l].v=d[l].h=ch[l]-'a'+1;
// d[l].s=1,f(l)=fa,PushUp(l);return l;
// }
// d[mid].Init(0,0,0);
// if(ch[mid]>='a') v(mid)=ch[mid]-'a'+1;f(mid)=fa;
// if(l<mid) lc(mid)=Build(l,mid-1,mid);
// if(r>mid) rc(mid)=Build(mid+1,r,mid);
// PushUp(mid);return mid;
// }
void Rot(int o){
int p=f(o),k=f(p),r=rc(p)==o;
if(k) d[k].ch[rc(k)==p]=o;
d[d[o].ch[r^1]].f=p,d[o].f=k;
d[p].ch[r]=d[o].ch[r^1],d[o].ch[r^1]=p,d[p].f=o;
PushUp(p),PushUp(o);
}
void DFS(int o){
if(lc(o)) DFS(lc(o));
cout<<o<<" "<<d[o].v<<" "<<d[o].h<<" "<<d[o].s<<endl;
cout<<" lc="<<lc(o)<<" rc="<<rc(o)<<" f="<<f(o)<<endl;
if(rc(o)) DFS(rc(o));
}
void Splay(int o,int g){
for(;f(o)!=g;){
int p=f(o),k=f(p);
if(k!=g) Rot((rc(p)==o)==(rc(k)==p)?p:o);
// cout<<"Ok Rot"<<endl;
Rot(o);
}if(!g) rt=o;
// cout<<"rt="<<rt<<endl;
// DFS(rt);
}
int findkth(int o,int k){
if(d[lc(o)].s>=k) return findkth(lc(o),k);
else if(d[lc(o)].s+1<k) return findkth(rc(o),k-d[lc(o)].s-1);
else return o;
}
void Insert(int x,LL v){
int p=findkth(rt,x),q=findkth(rt,x+1);
Splay(p,0),Splay(q,p);
// d[++cnt].Init(0,v,0);rt=cnt;
// rc(p)=0,f(p)=f(q)=rt,lc(rt)=p,rc(rt)=q;
// PushUp(p),PushUp(q),PushUp(rt);
d[++cnt].Init(0,v,0);
f(cnt)=q,lc(q)=cnt;
PushUp(cnt),PushUp(q),PushUp(p);
}
void Change(int x,LL v){
int o=findkth(rt,x);
Splay(o,0),d[o].v=v,PushUp(o);
}
void init(){
// fread(ps,1,N<<3,stdin);
p[0]=1;for(int i=1;i<N;i++) p[i]=(LL)p[i-1]*197;
d[0].Init(0,0,0);
scanf("%s",ch+2);int n=strlen(ch+2);
Build(rt,0,1,n+2);
// rt=Build(1,n+2,0);
// cout<<rt<<" "<<cnt<<endl;
}
LL Query(int u,int v){
// if(u>v) return -1;
u--,v++;
u=findkth(rt,u),v=findkth(rt,v);
// cout<<"Ok find "<<u<<" "<<v<<endl;
Splay(u,0),Splay(v,u);
// cout<<"Ok Splay"<<endl;
return h(lc(v));
}
void sol(){
char opt[5],c[5];int u,v;
for(int m=in();m--;){
scanf("%s",opt);
// cout<<opt<<"********"<<endl;
if(opt[0]=='R') scanf("%d%s",&u,c),Change(u+1,c[0]-'a'+13);
else if(opt[0]=='I') scanf("%d%s",&u,c),Insert(u+1,c[0]-'a'+13);
else {
u=in()+1,v=in()+1;
int l=0,r=min(cnt-v,cnt-u);
// cout<<"Start Q"<<endl<<"*********"<<endl;
while(l<=r){
// cout<<"***\ncs mid="<<mid<<endl;
// cout<<u<<" "<<mid<<" "<<Query(u,u+mid-1)<<endl;
// cout<<v<<" "<<mid<<" "<<Query(v,v+mid-1)<<endl;
if((LL)Query(u,u+mid-1)==Query(v,v+mid-1)) l=mid+1;
else r=mid-1;
}printf("%d\n",r);
}
// cout<<opt<<" is ok"<<endl;
}
}
}spl; int main(){
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
spl.init();
// cout<<"Finish init()"<<endl;
// spl.DFS(spl.rt);
// cout<<"Finish DFS()"<<endl;
spl.sol();
// cout<<"Finish sol()"<<endl;
return 0;
}