膜了陈老师的论文
简单来说就是：
重量平衡树就是每次涉及的操作，子树大小都是$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$。
后缀平衡树+线段树就好了。
主要是$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;
}
小火车加强了数据之后暴力就挂了，于是想真正过了这题。
想用后缀平衡树来爽爽。
写完之后调了好久终于过了大样例（别问我大样例哪来的）
然后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;
}
评论 (0)
