字尾平衡樹
考慮如果可以離線，隻需構出字尾數組套上線段樹。線上的話我們需要一個線上的字尾數組，結合題意中字尾的含義，用字尾平衡樹即可。
#include<set>
#include<cstdio>
#include<algorithm>
#define N 800005
using namespace std;
namespace runzhe200
{
typedef double db;
db alpha = ., badl, badr; char s[N];
int n, m, len, code, tail, in[N];
struct node
{
node *ch[], *fa;
db v; int siz, id;
}mem[N], *tot, *null, *root, *pos[N], *bad, *q[N];
node *newnode(){node *p = ++tot; *p = *null;return p;}
int type(node *x){return x->fa->v < x->v ? : ;}
void init()
{
bad = null = tot = mem;
null->fa = null->ch[] = null->ch[] = null;
null->v = null->siz = ;
pos[] = root = newnode();
pos[]->v = .; pos[]->siz = ; pos[]->id = ;
}
node* insert(node *fa, node *x, db l, db r, int id)
{
if(x == null){pos[id] = x = newnode(); x->fa = fa; x->id = id; x->siz = ; x->v = (l+r)/; return x;}
if(s[id] < s[x->id] || (s[id] == s[x->id] && pos[id-]->v < pos[x->id-]->v)) x->ch[] = insert(x, x->ch[], l, (l+r)/, id);
else x->ch[] = insert(x, x->ch[], (l+r)/, r, id);
x->siz++; if(x->siz * alpha < max(x->ch[]->siz, x->ch[]->siz)) bad = x, badl = l, badr = r;
return x;
}
void fetch(node *x)
{
if(x == null) return; q[++tail] = x;
fetch(x->ch[]); fetch(x->ch[]);
}
bool cmp(node *x, node *y){return x->v < y->v;}
node* rebuild(int L, int R, db l, db r, node *fa)
{
if(L > R) return null;
int mid = (L+R)>>;
q[mid]->fa = fa;
q[mid]->v = (l+r)/;
q[mid]->ch[] = rebuild(L,mid-,l,(l+r)/,q[mid]);
q[mid]->ch[] = rebuild(mid+,R,(l+r)/,r,q[mid]);
q[mid]->siz = q[mid]->ch[]->siz + q[mid]->ch[]->siz + ;
return q[mid];
}
void check_bad()
{
if(bad == null) return;
tail = ; node *badfa = bad->fa; fetch(bad);
sort(q+, q++tail, cmp);
node *p = rebuild(,tail,badl,badr,badfa);
if(badfa != null) badfa->ch[type(p)] = p; else root = p;
bad = null;
}
struct seg{int v;}t[N*5];
void build(int x, int l, int r)
{
t[x].v = ; if(l == r) return; int mid = (l+r)>>;
build(x<<,l,mid); build(x<<|,mid+,r);
}
void modi(int x, int l, int r, int p, int v)
{
if(l == r){t[x].v = v; return;} int mid = (l+r)>>;
p <= mid ? modi(x<<,l,mid,p,v) : modi(x<<|,mid+,r,p,v);
if(!t[x<<].v) t[x].v = t[x<<|].v;
else if(!t[x<<|].v) t[x].v = t[x<<].v;
else t[x].v = pos[in[t[x<<].v]]->v > pos[in[t[x<<|].v]]->v ? t[x<<|].v : t[x<<].v;
}
int query(int x, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr) return t[x].v;
int mid = (l+r)>>, p1 = , p2 = ;
if(ql <= mid) p1 = query(x<<,l,mid,ql,qr);
if(mid < qr) p2 = query(x<<|,mid+,r,ql,qr);
if(!p1)return p2; if(!p2) return p1; return pos[in[p1]]->v > pos[in[p2]]->v ? p2 : p1;
}
void main()
{
scanf("%d%d%d%d%s",&n,&m,&len,&code,s+);
for(int i = , ii = len>>; i <= ii; i++) swap(s[i], s[len-i+]);
build(,,n); init();
for(int i = ; i <= len; i++)
insert(root, root, , , i), check_bad();
for(int i = ; i <= n; i++)
{
int p; scanf("%d",&p);
in[i] = p; modi(,,n,i,i);
}
char opt[]; int ans = ;
for(int i = ; i <= m; i++)
{
scanf("%s",opt);
if(opt[] == 'I')
{
int c; scanf("%d",&c);
code ? (c ^= ans) : ;
s[++len] = c + 'a';
insert(root, root, , , len), check_bad();
}
else if(opt[] == 'C')
{
int x, to; scanf("%d%d",&x,&to);
in[x] = to;
modi(,,n,x,x);
}
else
{
int l, r; scanf("%d%d",&l,&r);
ans = query(,,n,l,r);
printf("%d\n",ans);
}
}
}
}
int main()
{
runzhe200::main();
}