如果需要动态维护后缀数组，支持在字符串前端插入一个字符，询问后缀的大小关系，如何做呢？
这是一个不断插入的问题，可以从增量的角度考虑。我们在前端插入一个字符，其实就是插入了一个新的后缀。我们的问题其实就是这个后缀排名多少。我们可以用平衡树维护一下后缀数组，从根节点开始二分比较这个后缀的大小，看看它应该被插到哪里。现在问题就变成了快速比较一个新的后缀和一个已有的后缀。
如果这个新的后缀和当前比较的后缀的首字符不同，那么比较结果是显然的；如果新的后缀和当前比较的后缀的首字符相同，那么问题就转化成了比较原来已有的两个后缀的大小关系。我们在平衡树的每个节点上维护一个值\(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; }转载于:https://www.cnblogs.com/owenyu/p/6724597.html
