6
9
2015
0

重量平衡树与后缀平衡树

膜了陈老师的论文  

简单来说就是:

重量平衡树就是每次涉及的操作,子树大小都是$O(logn)$的。

所以一些复杂的信息我们就可以暴力重新维护。

论文指出替罪羊树和$treap$都是重量平衡的。

在证明过程中用了一个比较显然的结论就是$n$个随机元素,某个是最大的概率是$\frac{1}{n}$(这不废话!)

然后在UOJ Round8 B题中更是用到了一个结论:

一个随机序列$a_{1-n}$,从$a_1$开始不断跳向比目前大的值,期望跳的次数只有$O(logn)$。

感觉十分不可思议?

其实我们考虑每个数对$ans$的贡献,$a_i$对$ans$有贡献当且仅当$a_i$是$a_{1-i}$的最大值,这个概率是$\frac{1}{n}$.

所以总的期望就是$\sum_{i=1}^{n}\frac{1}{i}=logn$ (其实严格来说这里是$ln n$)

所以也就是说期望跳的此时就是$logn$的。

然后因为重量平衡,所以我们可以用$treap$+线段树来做BZOJ3065.

然后后缀平衡树呢?就是动态维护后缀数组,也就是用一棵$treap$来维护$sa$。具体实现

就是给每个节点$x$一个$tag$以及对应区间$[l,r]$,那么$tag=l+r$,然后它的左儿子的对应区间为$[l,mid]$,右儿子对应区间为$[mid+1,r]$。

这样tag的大小反映的就是后缀的大小。

然后每次旋转的时候就暴力维护子树的对应区间以及$tag$。

BZOJ3682: Phorni

后缀平衡树+线段树就好了。

主要是$get$了一份模板:

int n,m,rt,len,type,tot,h[maxn],a[maxn],b[maxn],ls[maxn],rs[maxn];
ll rk[maxn];
char s[maxn],ch[10];
struct seg{int mi;}t[4*maxn];
inline void rebuild(int k,ll l,ll r)
{
	if(!k)return; 
    rk[k]=l+r;
    rebuild(ls[k],l,mid);rebuild(rs[k],mid,r);
}
inline void rturn(int &k,ll l,ll r)
{
    int t=ls[k];ls[k]=rs[t];rs[t]=k;k=t;rebuild(k,l,r);
}
inline void lturn(int &k,ll l,ll r)
{  
    int t=rs[k];rs[k]=ls[t];ls[t]=k;k=t;rebuild(k,l,r);
}
inline bool cmp(int x,int y){return a[x]<a[y]||(a[x]==a[y]&&rk[x-1]<rk[y-1]);}
inline void insert(int &k,ll l,ll r)
{
	if(!k){k=tot;rk[k]=l+r;return;}
	if(cmp(tot,k)){insert(ls[k],l,mid);if(h[ls[k]]>h[k])rturn(k,l,r);}
	else {insert(rs[k],mid,r);if(h[rs[k]]>h[k])lturn(k,l,r);}
}
inline void insert(int x)
{
    a[++tot]=x;h[tot]=rand()*rand();
	insert(rt,1,(ll)1<<61);
}
inline void pushup(int k)
{
    t[k].mi=rk[b[t[k<<1].mi]]<=rk[b[t[k<<1|1].mi]]?t[k<<1].mi:t[k<<1|1].mi;
}
inline void build(int k,int l,int r)
{
	if(l==r){b[l]=read();t[k].mi=l;return;}
	build(lch);build(rch);
	pushup(k);
}
inline void change(int k,int l,int r,int x)
{
	if(l==r)return;
	if(x<=mid)change(lch,x);else change(rch,x);
	pushup(k);
}
inline int query(int k,int l,int r,int x,int y)
{
	if(l==x&&r==y)return t[k].mi;
	if(y<=mid)return query(lch,x,y);
	else if(x>mid)return query(rch,x,y);
	else 
	{
	     int t1=query(lch,x,mid),t2=query(rch,mid+1,y);
	     return rk[b[t1]]<=rk[b[t2]]?t1:t2;
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    n=read();m=read();len=read();type=read();
    scanf("%s",s);
    for1(i,len)insert(s[len-i]-'a'+1);
    build(1,1,n);int ans=0;
    while(m--)
    {
    	scanf("%s",ch);
    	if(!type)ans=0;
    	if(ch[0]=='I')insert((read()^ans)+1);
    	else if(ch[0]=='C'){int x=read(),y=read();b[x]=y;change(1,1,n,x);}
    	else {int x=read(),y=read();printf("%d\n",ans=query(1,1,n,x,y));}
    }
    return 0;
}

BZOJ2555: SubString  

小火车加强了数据之后暴力就挂了,于是想真正过了这题。

想用后缀平衡树来爽爽。

写完之后调了好久终于过了大样例(别问我大样例哪来的)

然后T了。

仔细看了下这数据范围根本不允许带log的算法过啊

char s[maxm];
int tot,rt,a[maxn],size[maxn],ls[maxn],rs[maxn],h[maxn];
ll rk[maxn];
int mask;
inline void pushup(int k)
{
	size[k]=size[ls[k]]+size[rs[k]]+1;
}
inline void rebuild(int k,ll l,ll r)
{
	if(!k)return;
	rk[k]=l+r;
	rebuild(ls[k],l,mid);rebuild(rs[k],mid,r);
	pushup(k);
}
inline void lturn(int &k,ll l,ll r)
{
	int t=rs[k];rs[k]=ls[t];ls[t]=k;k=t;rebuild(k,l,r);
}
inline void rturn(int &k,ll l,ll r)
{
	int t=ls[k];ls[k]=rs[t];rs[t]=k;k=t;rebuild(k,l,r);
}
inline bool cmp(int x,int y){return a[x]<a[y]||(a[x]==a[y]&&rk[x-1]<rk[y-1]);}
inline void insert(int &k,ll l,ll r)
{
	if(!k){k=tot;rk[k]=l+r;size[k]=1;return;}
	size[k]++;
	if(cmp(tot,k)){insert(ls[k],l,mid);if(h[ls[k]]>h[k])rturn(k,l,r);}
	else {insert(rs[k],mid,r);if(h[rs[k]]>h[k])lturn(k,l,r);}
}
inline void insert(int x)
{
	a[++tot]=x;h[tot]=rand()*rand();
	insert(rt,1,(ll)1<<61);
}
inline void getstr(int mask)
{
	scanf("%s",s);int n=strlen(s);
	for0(i,n-1)
	{
		mask=(mask*131+i)%n;
		swap(s[i],s[mask]);
	}
}
inline int cmp(int l1,int r1,int l2,int r2)
{
	int i=l1,j=l2;
	for(;i>=r1&&j>=r2;i--,j--)
	{
		if(i==-1||s[i]-'A'+1>a[j])return 1;
		else if(s[i]-'A'+1<a[j])return -1;
	
	}
	if(i>=r1)return 1;
	else if(j>=r2)return -1;
	else return 0;
}
inline int rank(int k,int l,int r)
{
	if(!k)return 0;
	int t=cmp(l,r,k,1);
	if(t==0)return size[ls[k]];
	else if(t>0)return size[ls[k]]+1+rank(rs[k],l,r);
	else return rank(ls[k],l,r);
}
int cnt=0;
inline void dfs(int x)
{
	if(!x)return;
	dfs(ls[x]);
	dfs(rs[x]);
}
inline int query()
{
	int n=strlen(s),t1=rank(rt,n-1,-1),t2=rank(rt,n-1,0);
    return t1-t2;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int Q=read();
    scanf("%s",s);int n=strlen(s);for0(i,n-1)insert(s[i]-'A'+1);
    while(Q--)
    {
    	memset(s,0,sizeof(s));
        scanf("%s",s);
        if(s[0]=='A'){getstr(mask);int n=strlen(s);for0(i,n-1)insert(s[i]-'A'+1);}
        else {getstr(mask);int ans=query();mask^=ans;printf("%d\n",ans);}
    }
    return 0;
}
Category: 涨姿势 | Tags: | Read Count: 854

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com