如果需要动态维护后缀数组，支持在字符串前端插入一个字符，询问后缀的大小关系，如何做呢？
这是一个不断插入的问题，可以从增量的角度考虑。我们在前端插入一个字符，其实就是插入了一个新的后缀。我们的问题其实就是这个后缀排名多少。我们可以用平衡树维护一下后缀数组，从根节点开始二分比较这个后缀的大小，看看它应该被插到哪里。现在问题就变成了快速比较一个新的后缀和一个已有的后缀。
如果这个新的后缀和当前比较的后缀的首字符不同，那么比较结果是显然的；如果新的后缀和当前比较的后缀的首字符相同，那么问题就转化成了比较原来已有的两个后缀的大小关系。我们在平衡树的每个节点上维护一个值\(x\in [0,1]\)，代表它的大小，左儿子为的关键值为\([l,mid]\)，右儿子的关键值为\([mid,r]\)，那么只要直接比较这个值就可以啦。
然而如果平衡树的深度过大，那么这个值会爆实数的精度。所以我们采用深度为\(O(logn)\)的平衡树。但如果平衡树需要旋转，那么它的子树需要全部重新计算关键值。所以我们需要使用重量平衡树，其子树大小均摊\(O(logn)\)，所以每次插入旋转后整个子树重算一下。
代码：
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long giant;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=3e5+1;
const int P=1e9+7;
char start[maxn];
int ans=0,Len,type,ansh=0;
int convert(int x) {
if (!type) return x; else
return (x^ans)%Len+1;
}
struct node {
int hp,ch[2],fa;
int thef,nexp;
double lx,rx,x;
void val(double _x,double _y) {
lx=_x,rx=_y;
x=(lx+rx)/2;
}
};
struct SAT {
node t[maxn];
int tot,s[maxn],n,root,where[maxn];
SAT () {
n=0;
root=tot=1;
t[root].hp=-1;
t[root].val(0,1);
}
int newnode() {
t[++tot].hp=rand();
return tot;
}
void revalue(int x,double lx,double rx) {
if (!x) return;
t[x].val(lx,rx);
revalue(t[x].ch[0],t[x].lx,t[x].x);
revalue(t[x].ch[1],t[x].x,t[x].rx);
}
bool rson(int x) {
return t[t[x].fa].ch[1]==x;
}
void getval(int x) {
int f=t[x].fa;
if (rson(x)) t[x].val(t[f].x,t[f].rx); else t[x].val(t[f].lx,t[f].x);
}
void rotate(int x) {
int f=t[x].fa,d=rson(x),c=t[x].ch[d^1];
if (t[f].fa) t[t[f].fa].ch[rson(f)]=x;
if (c) t[c].fa=f;
t[x].fa=t[f].fa,t[f].fa=x;
t[x].ch[d^1]=f,t[f].ch[d]=c;
getval(x);
getval(f);
}
bool compare(int x,int y) {
if (t[x].thef!=t[y].thef) return t[x].thef<t[y].thef;
return t[t[x].nexp].x<t[t[y].nexp].x;
}
void insert(int c) {
s[++n]=c;
int now=root,lsize=0;
int nw=newnode();
where[n]=nw;
t[nw].thef=c;
t[nw].nexp=tot-1;
while (true) {
bool cmp=compare(now,nw);
int &tmp=t[now].ch[cmp];
if (tmp) now=tmp; else {
t[tmp=nw].fa=now;
if (cmp) t[nw].val(t[now].x,t[now].rx); else t[nw].val(t[now].lx,t[now].x);
break;
}
}
while (t[t[nw].fa].hp>t[nw].hp) rotate(nw);
revalue(nw,t[nw].lx,t[nw].rx);
}
int query(int x,int y) {
int fx=where[Len-x+1],fy=where[Len-y+1];
return t[fx].x<t[fy].x;
}
} Sat;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
srand(time(0));
scanf("%s",start+1);
Len=strlen(start+1);
for (int i=Len;i>0;--i) Sat.insert(start[i]-'a'+1);
int m=read();
type=read();
while (m--) {
char op[3];
scanf("%s",op);
if (op[0]=='I') {
char c[3];
scanf("%s",c);
++Len;
Sat.insert(c[0]-'a'+1);
} else if (op[0]=='Q') {
int x=read(),y=read();
x=convert(x),y=convert(y);
ans=Sat.query(Len-x+1,Len-y+1)?x:y;
ansh=((giant)ansh*23ll+(giant)ans)%P;
}
}
printf("%d\n",ansh);
return 0;
}