【BZOJ 3682】Phorni

題目連結

題目描述

Phorni 是一個音之妖精,喜歡在你的打字機上跳舞。

一天,陽光映射到剛剛淋浴過小雨的城市上時,Phorni 用魔法分裂出了許多個幻影,從 1 到 n 編号。

她的每一個幻影都站在打出的字元串的一個位置上,多個幻影可以站在同一個位置上。

每一個幻影代表的字元串即為從它站立位置開始的字尾,注意站立位置是從右往左數的。

讓我們形式化地描述一下,若第 i 個幻影站在 Pi 上,那麼它所代表的字元串就是 S[L-Pi+1…L],其中 L 是字元串 S 的長度。

每一次,她會選一段編号區間 [l…r],而編号在這個區間中的幻影中,字典序最小的一個将跳一支舞,若有多個幻影字典序相同,選編号最小的。

當然由于 Phorni 還會在打字機上跳動,是以有時字元串的前面會加入一個字元。

當然這個打字機是帶加密功能的。

字典序的比較:

将兩個字元串逐位比較,長度不足的向後補 0 ( 0 小于任何字元) 。直到比出大小或判定相等。

比如 “pho” > “ph” , “pb” > “pab” 。

下标從 1 開始,保證涉及到的所有字元都為小寫字母。

Sol

字尾平衡樹闆子題。

用平衡樹動态維護 SA 數組，采用賦權值的方式達到快速比較兩個點的先後關系。

查詢就用線段樹維護并查詢就行了。

code:

#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}typedef long long ll;
typedef double db;
const int N=5e5+10;
int n,m,len,type;
char S[N];
int ls[N],rs[N],size[N],pos[N];
db val[N];
#define ls (u<<1)
#define rs (u<<1|1)
int Min[N<<2];
inline void update(int u){
	Min[u]=Min[ls];
	if(Min[rs]&&val[pos[Min[u]]]>val[pos[Min[rs]]]) Min[u]=Min[rs];
	return;
}
inline void Update(int u,int l,int r,int p){
	if(l==r) return void(Min[u]=p);
	int mid=(l+r)>>1;
	if(mid>=p) Update(ls,l,mid,p);
	else       Update(rs,mid+1,r,p);
	return update(u);
}
void Build(int u,int l,int r){
	if(l==r) return void(Min[u]=l);
	int mid=(l+r)>>1;
	Build(ls,l,mid),Build(rs,mid+1,r);
	update(u);
}
int Query(int u,int l,int r,int L,int R){
	if(l>=L&&r<=R) return Min[u];
	int mid=(l+r)>>1;
	if(mid>=R) return Query(ls,l,mid,L,R);
	if(mid< L) return Query(rs,mid+1,r,L,R);
	int LP=Query(ls,l,mid,L,mid);
	int RP=Query(rs,mid+1,r,mid+1,R);
	if(val[pos[LP]]<=val[pos[RP]]) return LP;
	return RP;
}
#undef ls
#undef rs
int rt;
inline bool cmp(int i,int j){if(S[i]!=S[j]) return S[i]<S[j];return val[i-1]<val[j-1];}
int stk[N],top;
void dfs1(int u){if(!u)return;dfs1(ls[u]);stk[++top]=u;dfs1(rs[u]);return;}
void dfs2(int&u,db l,db r,int L,int R){
	if(l>r) return;int MID=(L+R)>>1;
	u=stk[MID];size[u]=1;ls[u]=rs[u]=0;
	db mid=val[u]=(l+r)/2.00;
	dfs2(ls[u],l,mid,L,MID-1);
	dfs2(rs[u],mid,r,MID+1,R);
	size[u]+=size[ls[u]]+size[rs[u]];
	return;
}
void Rebuild(int&u,db l,db r) {top=0;dfs1(u);dfs2(u,l,r,1,top);}
const db alpha=0.75;
inline bool Check(int u){
	const db LIM=size[u]*alpha;
	if(!LIM) return 0;
	if(LIM<=size[ls[u]]||LIM<=size[rs[u]]) return 1;
	return 0;
}

void Insert(int&u,db l,db r,int p,bool reb){
	if(!u) {u=p;val[u]=(l+r)/2.0;return;}
	bool re=!Check(u);
	if(cmp(u,p)) Insert(rs[u],(l+r)/2.00,r,p,reb&re);
	else         Insert(ls[u],l,(l+r)/2.00,p,reb&re);
	if((!re)&&reb) Rebuild(u,l,r);return;
}

int main()
{
	init(n),init(m),init(len),init(type);
	scanf("%s",S+1);rt=0;reverse(S+1,S+1+len);
	for(int i=1;i<=len;++i) Insert(rt,0,1,i,1);
	for(int i=1;i<=n;++i) init(pos[i]);Build(1,1,n);
	int last=0;
	for(int i=1;i<=m;++i) {
		char sss[10];scanf("%s",sss);
		if(sss[0]=='I') {
			int c;init(c);
			if(type==1) c^=last;
			S[++len]=c+'a';
			Insert(rt,0,1,len,1);
		}else if(sss[0]=='C'){
			int x,p;init(x),init(p);
			pos[x]=p;Update(1,1,n,x);
		}else{
			int l,r;init(l),init(r);
			last=Query(1,1,n,l,r);
			printf("%d\n",last);
		}
	}
	return 0;
}