【bzoj3682】phorni【后缀平衡树】

FSY的代码真tm好读，比zxy的好看多了，赏心悦目的一匹。

支持前端添加字符，维护所有后缀的排名信息。

我们使用后缀平衡树。

如果直接二哈的话，复杂度

会死掉，所以使用nb的后缀平衡树。

后缀平衡树每个节点对应一个后缀。给每个节点一个我们定义的权值来比较相对大小。

这个自定义权值实现长得像线段树。

每个节点给一个左右权值。该点权值为左右权值的平均数。

左儿子的左右权值为l，mid-1，右儿子为mid+1，r。这样可以得到一个很漂亮的平衡树结构。

但与此同时，如果树的结构发生变化，那这些权值都要重新计算。

如果在treap上魔改，那就在rotate之后重新计算权值。

如果在重量平衡树上魔改，就设一个α因子，一般在0.55左右，根据数据来定。如果太不平衡，就重构。

因为每个节点都有一个权值，所以我们比较两个后缀只需要O(1)。

现在说明怎么插入。

很明显在前端添加字符得到的字符串是c+S，原串是S。那我们只需要比较两个串的首字母，因为后面的东西都已经在平衡树里面可以O(1)比较。

原串里也可以这样干。所以每次插入一个节点的期望复杂度是O(logn）。

而根据treap的小根堆性质发现重构次数也小的很所以总复杂度期望O(nlogn)。

其实这个重新计算权值跟替罪羊很像，，暴力是最棒的。

那对于这道题，有个pos数组，只需要线段树维护一下就星。

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define ll long long
const int N=1000003;
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
long long key[N];int rt;
int ch[N][2],rnd[N],a[N],node;
int n,m,len,pos[N];char s[N];
int Rand(){
	return rand()<<15|rand();
}
struct SEG{
	int val[N<<2];
	int merge(int x,int y){return (key[pos[x]]<=key[pos[y]])?x:y;}
	void pushup(int u){val[u]=merge(val[u<<1],val[u<<1|1]);}
	void build(int u,int l,int r){//cout<<u<<endl;
		if(l==r){val[u]=l;return;}
		int mid=(l+r)>>1;
		build(u*2,l,mid);build(u*2+1,mid+1,r);
		pushup(u);
	}
	void change(int u,int l,int r,int qpos,int ri){
		if(l==r){pos[qpos]=ri;return;}
		int mid=(l+r)>>1;
		if(qpos<=mid)change(u*2,l,mid,qpos,ri);
		else change(u*2+1,mid+1,r,qpos,ri);
		pushup(u);
	}
	int query(int u,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return val[u];
		int mid=(l+r)>>1;
		if(qr<=mid)return query(u*2,l,mid,ql,qr);
		if(ql>mid)return query(u*2+1,mid+1,r,ql,qr);
		return merge(query(u*2,l,mid,ql,qr),query(u*2+1,mid+1,r,ql,qr));
	}
}SEG;
void pia(int u,ll l,ll r){
	if(!u)return;ll mid=(l+r)>>1;
	key[u]=mid;pia(ch[u][0],l,mid-1);pia(ch[u][1],mid+1,r);
	
}
void rotate(int x,int &fa,ll l,ll r){
	int k=ch[fa][1]==x;ch[fa][k]=ch[x][k^1];ch[x][k^1]=fa;
	fa=x;pia(fa,l,r);
}
bool cpr(int x,int y){
	if(a[x]!=a[y])return a[x]<a[y];
	return key[x-1]<key[y-1];
}
void insert(int &u,int pos,ll l,ll r){
	if(!u){u=node;key[node]=(l+r)>>1;return;}
	ll mid=(l+r)>>1;
	if(cpr(pos,u)){
		insert(ch[u][0],pos,l,mid-1);if(rnd[u]>rnd[ch[u][0]])rotate(ch[u][0],u,l,r);
	}else{
		insert(ch[u][1],pos,mid+1,r);if(rnd[u]>rnd[ch[u][1]])rotate(ch[u][1],u,l,r);
	}
}int last;int tp;
int main(){
	srand(time(0));
	n=in;m=in;len=in;tp=in;
	scanf("%s",s+1);
	for(int i=1;i<=len;i++){
		a[++node]=s[len-i+1]-'a'+1;rnd[node]=Rand();
		insert(rt,i,1,1ll<<61);
	}for(int i=1;i<=n;i++)pos[i]=in;
	SEG.build(1,1,n);char gu[3];int x,y;
	while(m--){
		if(tp==0)last=0;
		scanf("%s",gu+1);
		if(gu[1]=='I'){
			x=(in^last)+1;
			a[++node]=x;rnd[node]=Rand();
			insert(rt,node,1,1ll<<61);
		}
		if(gu[1]=='C'){
			x=in;y=in;SEG.change(1,1,n,x,y);
		}
		if(gu[1]=='Q'){
			x=in;y=in;
			printf("%d\n",last=SEG.query(1,1,n,x,y));
		}
	}
	return 0;
}