BruceJay's Blog

BZOJ1014 火星人prefix

| Comments

To start with

这是一道绝世好题,Splay与二分,hash的结合。

Problem

Solution

Splay可以神奇地维护区间哈希值(具体怎么维护看代码咯)。。。
询问时二分区间长度,查询哈希值是否相等。

Code

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

const int N = 200100;
const int Mod = 9875321;
typedef long long ll;
int a[N]; int tr[N][2];
int val[N]; int h[N];
int size[N]; int fa[N];
int n,root=0,sz;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Update(int &k)
{
    int l=tr[k][0],r=tr[k][1];
    size[k]=size[l]+size[r]+1;
    h[k]=h[l]+(ll)a[k]*val[size[l]]%Mod+(ll)val[size[l]+1]*h[r]%Mod;
    h[k]%=Mod;
}

void Rotate(int x,int &k)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(y==k) k=x;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Update(y); Update(x);
}

void Splay(int x,int &k)
{
    while(x!=k){
        int y=fa[x];
        if(y!=k){
            int z=fa[y];
            if(tr[z][0]==y^tr[y][0]==x) Rotate(x,k);
            else Rotate(y,k);
        }
        Rotate(x,k);
    }
}

void Build(int &k,int l,int r,int pre)
{
    int mid=(l+r)>>1;
    k=mid; fa[k]=pre;
    if(l<mid) Build(tr[k][0],l,mid-1,k);
    if(mid<r) Build(tr[k][1],mid+1,r,k);
    Update(k);
}

int Find(int x,int &k)
{
    int t=size[tr[k][0]]+1;
    if(t==x) return k;
    else if(t<x) return Find(x-t,tr[k][1]);
    else return Find(x,tr[k][0]);
}

void Insert(int x,int y)
{
    int l=Find(x,root),r=Find(x+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    tr[r][0]=++sz; fa[sz]=r; a[sz]=y;
    Update(sz); Update(r); Update(l);
}

void Rewrite(int x,int y)
{
    x=Find(x,root);
    Splay(x,root);
    a[x]=y; Update(x);
}

ll H(int l,int r)
{
    l=Find(l-1,root); r=Find(r+1,root);
    Splay(l,root); Splay(r,tr[l][1]);
    return h[tr[r][0]];
}

int Query(int x,int y)
{
    if(x>y) swap(x,y);
    int l=1,r=sz-1-y,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(H(x+1,x+mid)==H(y+1,y+mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}

int main()
{
    char s[N]; int x,y;
    char ch[1],ch2[1];
    freopen("1014.in","r",stdin);
    freopen("1014.out","w",stdout);
    val[0]=1; for(int i=1;i<=200000;i++) val[i]=val[i-1]*27%Mod;
    scanf("%s",s); int len=strlen(s); n=read();
    for(int i=0;i<len;i++) a[i+2]=s[i]-'a'+1;
    sz=len+2; Build(root,1,sz,0);
    for(int i=1;i<=n;i++){
        scanf("%s",ch); x=read();
        if(ch[0]=='Q') y=read(),printf("%d\n",Query(x,y));
        else if(ch[0]=='R') scanf("%s",ch2),Rewrite(x+1,ch2[0]-'a'+1);
        else if(ch[0]=='I') scanf("%s",ch2),Insert(x+1,ch2[0]-'a'+1);
    }
    return 0;
}

Last but not least

Bruce的代码跑得很慢(哈希取long long还TLE)。
Splay的运用还是很广泛的。

Comments

comments powered by Disqus