后缀平衡树+线段树。

$O(1)$比较大小的标号法真是强大。

 

#include
     
      #include
      
       #define N 300010#define M 500010using namespace std;typedef unsigned long long ll;const ll inf=1ULL<<63;const double A=0.8;ll tl[N],tr[N],tm[N];int size[N],son[N][2],f[N],v[N],tot,root,id[N],cnt;char s[N],ch;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline bool cmp(int a,int b){return s[a]==s[b]?tm[a-1]>tm[b-1]:s[a]>s[b];}int ins(int x,int p){  int b=cmp(p,v[x]);  if(!son[x][b]){    son[x][b]=++tot;f[tot]=x;v[tot]=p;    if(!b)tl[tot]=tl[x],tr[tot]=tm[x];else tl[tot]=tm[x],tr[tot]=tr[x];    tm[tot]=(tl[tot]+tr[tot])>>1;    return tot;  }else return ins(son[x][b],p);}void dfs(int x){  if(son[x][0])dfs(son[x][0]);  id[++cnt]=x;  if(son[x][1])dfs(son[x][1]);}int build(int fa,int l,int r,ll a,ll b){  int mid=(l+r)>>1,x=id[mid];  f[x]=fa;son[x][0]=son[x][1]=0;size[x]=1;tl[x]=a;tr[x]=b;tm[x]=(a+b)>>1;  if(l==r)return x;  if(l
       
        mid)size[x]+=size[son[x][1]=build(x,mid+1,r,tm[x],b)];  return x;}inline int rebuild(int x){  cnt=0;dfs(x);return build(f[x],1,cnt,tl[x],tr[x]);}inline void insert(int p){  if(!root){root=tot=size[1]=1;v[1]=p;tr[1]=inf,tm[1]=inf>>1;return;}  int x=ins(root,p);  int deep=0,z=x;while(z)size[z]++,z=f[z],deep++;  if(deep
        
         >1;  l[x]=TOT+1;build(a,mid);  r[x]=TOT+1;build(mid+1,b);  min[x]=tm[seq[min[l[x]]]]<=tm[seq[min[r[x]]]]?min[l[x]]:min[r[x]];}void change(int x,int a,int b,int c){  if(a==b)return;  int mid=(a+b)>>1;  if(c<=mid)change(l[x],a,mid,c);else change(r[x],mid+1,b,c);  min[x]=tm[seq[min[l[x]]]]<=tm[seq[min[r[x]]]]?min[l[x]]:min[r[x]];}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d)return min[x];  int mid=(a+b)>>1,i,j;  if(d<=mid)return ask(l[x],a,mid,c,d);  if(c>mid)return ask(r[x],mid+1,b,c,d);  i=ask(l[x],a,mid,c,d),j=ask(r[x],mid+1,b,c,d);  return tm[seq[i]]<=tm[seq[j]]?i:j;}int n,m,i,x,y,len,type,ans;int main(){  read(n);read(m);read(len);read(type);  for(getchar(),i=1;i<=len;i++)s[len-i+1]=getchar();  for(i=1;i<=len;i++)insert(i);  for(i=1;i<=n;i++)read(seq[i]);  build(1,n);  while(m--){    while(!(((ch=getchar())=='I')||(ch=='C')||(ch=='Q')));read(x);    if(ch=='I')s[++len]=(x^ans*type)+'a',insert(len);    if(ch=='C')read(seq[x]),change(1,1,n,x);    if(ch=='Q')read(y),printf("%d\n",ans=ask(1,1,n,x,y));  }  return 0;}