有一个长度为 \(len\) 的字符串和 \(n\) 个幻影，每个幻影站在字符串的某个字符上，代表从该位置到字符串末尾的一个后缀。要求支持以下三个操作：在字符串开头添加一个字符 改变幻影位置 询问编号在 \([l,r]\) 的幻影代表字符串字典序最小的幻影编号是多少 强制在线
Solution后缀平衡树。
注意后缀平衡树如果要判断两个后缀字典序关系的话并不需要去\(\log\)的查rk数组，直接判断Treap上对应节点的 \(tag\) 哪个更小就好了。因为根据后缀平衡树的性质保证了 \(tag\) 互不相同且中序遍历是递增的。
然后这题再拿线段树维护一下每个幻影就好了
拿替罪羊树写会跑的飞快吧.... 真的懒得写
洛谷博客太垃圾了
计划把前一阵子在洛谷写的博客搬过来
Code #pragma GCC optimize(2) #include<bits/stdc++.h> using std::min; using std::max; using std::swap; using std::vector; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) const int N=2e6+5; const db inf=1e18; const db alph=0.9; char s[N]; int n,m,cnt; int len,type,p[N]; int getint(){ int X=0,w=0;char ch=getchar(); while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } namespace treap{ #define ls ch[x][0] #define rs ch[x][1] int tot,root,cnt,ch[N][2],d[N]; int sze[N],prio[N];db tag[N]; void pushup(int x){ sze[x]=sze[ls]+sze[rs]+1; d[x]=max(d[ls],d[rs])+1; } bool cmp(int x,int y){ return s[x]<s[y] or s[x]==s[y] and tag[x-1]<tag[y-1]; } void dfs(int now,db l,db r){ if(!now) return; db mid=(l+r)/2;tag[now]=mid; dfs(ch[now][0],l,mid);dfs(ch[now][1],mid,r); pushup(now); } void rotate(int &x,int d,db l,db r){ int y=ch[x][d],z=ch[y][d^1]; ch[x][d]=z;ch[y][d^1]=x; x=y; dfs(x,l,r); } void insert(int &x,db l,db r){ if(!x){ x=++tot;tag[x]=(l+r)/2; sze[x]=1;prio[x]=rand(); return; } db mid=(l+r)/2;int d=cmp(x,len); if(!d) insert(ls,l,mid); else insert(rs,mid,r); if(prio[ch[x][d]]<prio[x]) rotate(x,d,l,r); pushup(x); } #undef ls #undef rs } namespace seg{ #define ls x<<1 #define rs x<<1|1 #define lss ls,l,mid,ql #define rss rs,mid+1,r,ql int mn[N]; void pushup(int x){ mn[x]=treap::tag[p[mn[ls]]]<=treap::tag[p[mn[rs]]]?mn[ls]:mn[rs]; } void build(int x,int l,int r){ if(l==r) return mn[x]=l,void(); int mid=l+r>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(x); } void modify(int x,int l,int r,int ql){ if(l==r) return; int mid=l+r>>1; ql<=mid?modify(lss):modify(rss); pushup(x); } int query(int x,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return mn[x]; int mid=l+r>>1; if(qr<=mid) return query(lss,qr); if(ql>mid) return query(rss,qr); int a=query(lss,qr),b=query(rss,qr); return treap::tag[p[a]]<=treap::tag[p[b]]?a:b; } #undef ls #undef rs } signed main(){ srand(20020619); n=getint(),m=getint(),len=getint(),type=getint(); scanf("%s",s+1); int mxlen=len,lasans=0; std::reverse(s+1,s+1+len); for(len=1;len<=mxlen;len++) treap::insert(treap::root,1,inf);len--; for(int i=1;i<=n;i++) p[i]=getint(); seg::build(1,1,n); while(m--){ char ch[5];scanf("%s",ch); if(ch[0]=='I'){ int x=(getint()^lasans*type)+1; s[++len]=x+'a'-1; treap::insert(treap::root,1,inf); } else if(ch[0]=='C'){ int x=getint(),pos=getint(); p[x]=pos;seg::modify(1,1,n,x); } else{ int l=getint(),r=getint(); printf("%d\n",lasans=seg::query(1,1,n,l,r)); } } return 0; }