BZOJ3682: Phorni 后缀平衡树+线段树

题解：

终于会写后缀平衡树了0.0

首先我们要知道Treap是什么东西。Treap是一种二叉平衡树，同时是重量平衡树，也即单次插入删除期望最大影响的子树大小为$O(logn)$。

也就是说，我们可以暴力重新计算该子树的信息而不用担心复杂度爆炸。

考虑利用重量平衡树来处理动态顺序维护问题。

现在有一个序列，你可以在序列中的某个位置插入一个元素，询问就是询问两个元素的先后顺序。

直接利用平衡树可以做到插入、询问均为$O(logn)$。

考虑动态标号法，在平衡树中的每个节点都记录$[l,r]$，这个节点的值为$\lfloor\frac{l+r}{2}\rfloor$。

如比较两个元素的顺序，只需要比较两个平衡树节点的值就行了，于是是$O(1)$。

现在要插入一个元素，在旋转之后树的形态可能会发生变化，好在最大影响的子树大小为$O(logn)$，所以直接暴力计算子树内的节点的值就行了，于是单次插入复杂度依然为$O(logn)$。

由于重量平衡树深度期望为$O(logn)$，所以需要的权值的值域在long long范围就可以保证完全区分了。

后缀平衡树就是维护后缀之间字典序从小到大的有序序列的平衡树。

假如对于字符串$S[1,n]$，已经构造好$S'[i,n]$的后缀平衡树，考虑如何构造$S''[i-1,n]$的后缀平衡树。

那么只需插入后缀$i-1$就行了。

那么在平衡树中进行插入时，就需要比较两个后缀的字典序大小咯。

而我们可以做到$O(1)$，原因在：若两个后缀首字母相同，则同时去掉首字母，转化为已经存在在平衡树中的两个后缀的顺序问题，利用动态标号就能做到$O(1)$询问；如果首字母不同则显然$O(1)$完成。

维护后缀平衡树实质上就是一个动态顺序维护问题，因此可以做到$O(nlogn)$构造，$O(1)$询问两个后缀的字典序大小，并支持在串的开头插入一个字符。

关于平衡树复杂度的证明有时间再说。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef unsigned long long llu;

#define N 1000010
#define ls ch[0]
#define rs ch[1]
struct Node{
	Node*ch[2];
	llu v;
	int ins,p;
}Tnull,*null=&Tnull,mem[N],*G=mem,*get[N],*root=null;
inline Node*newnode(int _ins){
	G->ls=G->rs=null;
	G->ins=_ins;
	G->p=rand();
	return G++;
}

typedef pair<int,int> pii;
inline pii Min(pii x,pii y){
	if(x.first==-1)
		return y;
	if(y.first==-1)
		return x;
	if(get[x.first]->v!=get[y.first]->v)
		return get[x.first]->v<get[y.first]->v?x:y;
	return x.second<y.second?x:y;
}

#define mp make_pair

#define inf ((llu(-1))>>1)
int p[500010];
struct SegmentTree{
	pii A[1048675];
	int M;
	inline void init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		for(int i=0;i<(M<<1);++i)
			A[i]=mp(inf,0);
		for(int i=1;i<=_siz;++i)
			A[M+i]=mp(p[i],i);
		for(int i=M-1;i>=1;--i)
			A[i]=Min(A[i<<1],A[i<<1^1]);
	}
	inline void upd(int x,int _ins){
		for(A[x+=M].first=_ins,x>>=1;x;x>>=1)
			A[x]=Min(A[x<<1],A[x<<1^1]);
	}
	inline int query(int tl,int tr){
		pii ans=mp(-1,0);
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)
				ans=Min(ans,A[tl^1]);
			if(tr&1)
				ans=Min(ans,A[tr^1]);
		}
		return ans.second;
	}
}Seg;

char s[N];
inline bool cmp(const int&x,const int&y){
	if(s[x]!=s[y])
		return s[x]>s[y];
	return get[x-1]->v>get[y-1]->v;
}

inline void rot(Node*&p,bool d){
	Node*q=p->ch[!d];
	p->ch[!d]=q->ch[d];
	q->ch[d]=p;
	p=q;
}
inline void recalc(Node*p,llu _l,llu _r){
	p->v=(_l+_r)>>1;
	if(p->ls!=null)
		recalc(p->ls,_l,(_l+_r)>>1);
	if(p->rs!=null)
		recalc(p->rs,1+((_l+_r)>>1),_r);
}

Node*lastp;
llu lastl,lastr;
inline void insert(Node*&p,int _ins,llu _l,llu _r){
	if(p==null){
		get[_ins]=p=newnode(_ins);
		p->v=(_l+_r)>>1;
		return;
	}
	bool d=cmp(_ins,p->ins);
	if(d==0){
		insert(p->ls,_ins,_l,(_l+_r)>>1);
		if(p->ls->p<p->p){
			rot(p,1);
			lastp=p;
			lastl=_l;
			lastr=_r;
		}
	}
	else{
		insert(p->rs,_ins,1+((_l+_r)>>1),_r);
		if(p->rs->p<p->p){
			rot(p,0);
			lastp=p;
			lastl=_l;
			lastr=_r;
		}
	}
}

/*inline void dfs(Node*p){
	if(p->ls!=null)
		dfs(p->ls);
	printf("%d ",p->ins);
	if(p->rs!=null)
		dfs(p->rs);
}*/

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
	freopen("tt.out","w",stdout);
#endif
	int n,m,len,type;
	cin>>n>>m>>len>>type;
	int i;
	scanf("%s",s+1);
	for(i=1;i<=(len>>1);++i)
		swap(s[i],s[len-i+1]);
	for((get[0]=newnode(0))->v=0,i=1;i<=len;++i){
		lastp=null;
		insert(root,i,0,inf);
		if(lastp!=null)
			recalc(lastp,lastl,lastr);
	}
	
	//dfs(root);
	//puts("");

	for(i=1;i<=n;++i)
		scanf("%d",&p[i]);
	
	Seg.init(n);
	
	int lastans=0;
	
	char qte[10];
	int x,y;
	while(m--){
		scanf("%s",qte);
		if(qte[0]=='I'){
			scanf("%d",&x);
			if(type)
				x^=lastans;
			s[++len]='a'+x;
			lastp=null;
			insert(root,len,0,inf);
			if(lastp!=null)
				recalc(lastp,lastl,lastr);
		}
		else if(qte[0]=='C'){
			scanf("%d%d",&x,&y);
			Seg.upd(x,y);
		}
		else{
			scanf("%d%d",&x,&y);
			printf("%d\n",lastans=Seg.query(x,y));
		}
	}
	
	return 0;
}