注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj1014  

2013-01-23 18:11:52|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

第三题splay+hash。

传说这种hash的出错概率很低,所以就可以用了

我们可以开一个unsigned long long 来记录hash变量,然后什么都不做,就相当于在Mod 2^64了吧

然后通过左右子树hash值可以维护这棵子树的hash值。

再二分答案,就是n logn logn了。

这是一道很经典的题目。

非常巧的是,我在这之前做《算法竞赛入门经典》那本书上的题目的时候,看到了UVa11996。这道题就是那道题的弱化版,因为那道题有反转操作。

第一天做了那道题,第二天就看到这道题了我就无语了……

大家可以想想那道题怎么做。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 250010
using namespace std;
typedef unsigned long long LL;
char start[MAXN];
int digit[MAXN];
LL power[MAXN]={1};
struct node
{
    int v[MAXN],father[MAXN],son[MAXN][2],sum[MAXN],root;
    LL hash[MAXN];
    inline void update(int p)
    {
        sum[p]=sum[son[p][0]]+sum[son[p][1]]+1;
        hash[p]=hash[son[p][0]]*power[sum[son[p][1]]+1]+v[p]*power[sum[son[p][1]]]+hash[son[p][1]];
    }
    inline void Build(int l,int r)
    {
        int mid=(l+r)>>1;
        if(l<mid)  Build(l,mid-1),father[(l+mid-1)>>1]=mid,son[mid][0]=(l+mid-1)>>1;
        if(mid<r)  Build(mid+1,r),father[(mid+1+r)>>1]=mid,son[mid][1]=(mid+1+r)>>1;
        v[mid]=digit[mid],update(mid);
    }
    inline void Rotate(int p,int x)
    {
        int mark=p==son[x][1],y=son[p][mark^1],z=father[x];
        if(y!=0)  father[y]=x;
        if(x==son[z][0])  son[z][0]=p;
        if(x==son[z][1])  son[z][1]=p;
        father[x]=p,son[x][mark]=y,father[p]=z,son[p][mark^1]=x,update(x);
    }
    inline void Splay(int p,int k)
    {
        while(father[p]!=k)
        {
            int x=father[p],y=father[x];
            if(y==k)  Rotate(p,x);
            else if((p==son[x][0])^(x==son[y][0]))  Rotate(p,x),Rotate(p,y);
            else Rotate(x,y),Rotate(p,x); 
        }
        update(p);
        if(k==0)  root=p;
    }
    inline int Select(int rank,int k)
    {
        if(sum[root]<rank)  return -1;
        int p=root;
        while(sum[son[p][0]]+1!=rank)
        {
            if(sum[son[p][0]]+1>rank)  p=son[p][0];
            else rank=rank-sum[son[p][0]]-1,p=son[p][1];
        }
        Splay(p,k);
        return p;
    }
    inline void Insert(int a,int p,int k)
    {
        int l=Select(a,0),r=Select(a+1,l);
        son[r][0]=k,father[k]=r,v[k]=p,Splay(k,0);
    }
    inline void Change(int a,int p){  a=Select(a,0),v[a]=p,Splay(a,0);  }
    inline bool check(int p,int q,int L)
    {
        int x;
        LL hash1,hash2;
        Select(p,0),x=Select(p+L+1,root);
        if(x==-1)  return false;
        hash1=hash[son[x][0]];
        Select(q,0),x=Select(q+L+1,root);
        if(x==-1)  return false;
        hash2=hash[son[x][0]];
        return hash1==hash2;
    }
}tree;
inline int Two_Find(int p,int q,int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(tree.check(p,q,mid)==true)  l=mid+1;
        else r=mid;
    }
    return l-1;
}
void Ask()
{
    for(int i=1;i<MAXN;i++)
        power[i]=power[i-1]*53;
    scanf("%s",start);
    int n=strlen(start),m,l,r;
    char a[5],b[5];
    n+=2;
    for(int i=2;i<=n-1;i++)
        digit[i]=start[i-2]-'a'+1;
    tree.root=(1+n)>>1,tree.Build(1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",a);
        if(a[0]=='Q')
        {
            scanf("%d %d",&l,&r);
            printf("%d\n",Two_Find(l,r,0,n));
        }
        if(a[0]=='R')
        {
            scanf("%d %s",&l,b);
            tree.Change(l+1,b[0]-'a'+1);
        }
        if(a[0]=='I')
        {
            scanf("%d %s",&l,b);
            tree.Insert(l+1,b[0]-'a'+1,++n);    
        }
    }
}
int main()
{
    Ask();
    return 0;
}
  评论这张
 
阅读(801)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017