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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1014][JSOI2008]火星人prefix  

2014-11-03 10:08:06|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
感觉Splay又忘光了
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 150000+100;
const int MUL[2] = {1507,2319};
int n,m;
int scan(){int i=0;scanf("%d",&i);return i;}
char str[N];
typedef unsigned long long ll;
ll mul[2][N*10];
struct Node{
char c;ll d[2];int size;
Node *fa,*ch[2];
Node();
void count(){
size=ch[0]->size + ch[1]->size + 1;
d[0] = ch[0]->d[0]*MUL[0]+c-'a';
d[0] = mul[0][ch[1]->size]*d[0] + ch[1]->d[0];
d[1] = ch[0]->d[1]*MUL[1]+c-'a';
d[1] = mul[1][ch[1]->size]*d[1] + ch[1]->d[1];
}
short pl(){return this == fa->ch[0]?0:1;}
}*null,house[N*2];int hn;
Node *newNode(){
if(hn < N*2){house[hn]=Node();return &house[hn++];}
return new Node;
}
Node::Node(){fa = ch[0] = ch[1] = null;d[0] = d[1] =0;}
struct Splay{
Node *ROOT;
Splay(){
null = newNode();
null->size = 0;
null->ch[0] = null->ch[1] = null->fa = null;

ROOT = newNode();
ROOT->ch[1] = newNode();
ROOT->ch[1]->fa = ROOT;
ROOT->c = ROOT->ch[1]->c = 5;
ROOT->ch[1]->count();
ROOT->count();
}
Node* Build(int l,int r){
if(l>r)return null;
int mid = (l+r)/2;
Node *re = newNode();
re->c = str[mid];
if(l < r){
re->ch[0] = Build(l,mid-1);
re->ch[1] = Build(mid+1,r);
re->ch[0]->fa = re;
re->ch[1]->fa = re;
}
re->count();
return re;
}
void BUILD(){
ROOT->ch[1]->ch[0] = Build(1,n);
ROOT->ch[1]->ch[0]->fa = ROOT->ch[1];
ROOT->ch[1]->count();
ROOT->count();
}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null)return;
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null)r->fa->ch[r->pl()] = k;
else ROOT = k;
k->fa = r->fa;r->fa = k;
k->ch[x] = r;
r->count();k->count();
}
void splay(Node *r,Node *tar = null){
//if(r == null) exit(-1);
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r);
}
Node *kth(int k){
Node*r = ROOT;k++;
while(r){
if(r->ch[0]->size >= k)r = r->ch[0];
else if(r->ch[0]->size+1 >= k)break;
else k-=r->ch[0]->size+1,r=r->ch[1];
}return r;
}
void pack(int l,int r){
//l--;r++;
//if(l > r)exit(2);
if(r > n+2)exit(2);
Node *ro = kth(l);
splay(ro);
ro = kth(r);
splay(ro,ROOT);
}
void change(int i,char cc){
Node *ro = kth(i);
splay(ro);
ro->c = cc;
ro->count();
}
void insert(int i,char cc){
pack(i,i+1);
if(ROOT->ch[1]->ch[0] != null)exit(-1);
Node *ro = ROOT->ch[1]->ch[0] = newNode();
ro->fa = ROOT->ch[1];
ro->c = cc;
ro->count();
ROOT->ch[1]->count();
ROOT->count();
}
//DEBUG
void print(Node *r,int d = 0){
int i,j;
for(i=1;i<=d;i++)printf(" ");
if(r== null ){printf("null\n");return;}
printf("%c %d\n",r->c,r->size);
for(i=1;i<=d;i++)printf(" ");
printf("ch[0]:\n");
print(r->ch[0],d+1);
for(i=1;i<=d;i++)printf(" ");
printf("ch[1]:\n");
print(r->ch[1],d+1);

if(!d)printf("----end----\n");
}
}Tree;
bool check(int l,int r,int len){
Node *ro;
ll a[2],b[2];
Tree.pack(l -1, l+len-1 +1);
ro = Tree.ROOT->ch[1]->ch[0];
//if(len == 3)Tree.print(ro);
a[0] = ro->d[0];
a[1] = ro->d[1];
Tree.pack(r -1, r+len-1 +1);
ro = Tree.ROOT->ch[1]->ch[0];
//if(len == 3)Tree.print(ro);
b[0] = ro->d[0];
b[1] = ro->d[1];
return a[0] == b[0] && a[1] == b[1];
}
int main(){
int i,j,a,b;
char cc;
scanf("%s",str+1);
n = strlen(str+1);
mul[0][0] = mul[1][0] = 1;
for(i=1;i<=n*10;i++){
mul[0][i] = mul[0][i-1]*MUL[0];
mul[1][i] = mul[1][i-1]*MUL[1];
}
Tree.BUILD();
m = scan();
for(i=1;i<=m;i++){
scanf(" %c",&cc);
//printf("%d\n",i);
if(cc=='Q'){
a = scan();b = scan();
if(a > b)swap(a,b);
int l,r;
l = 0;r = n - b+1;
while(l<r){
int mid = (l+r+1)/2;
if(check(a,b,mid))l = mid;
else r = mid-1;
}
printf("%d\n",l);
}else if(cc=='R'){
a = scan();scanf(" %c",&cc);
Tree.change(a,cc);
}else{
a = scan();scanf(" %c",&cc);
Tree.insert(a,cc);
n++;
}
}
return 0;
}

题解:
用Splay维护字符串hash
我一开始的想法是相当于维护原hash数组(通过区间的加法&乘法)但是后来发现写起来异常困难(还需要逆元)
然后GTY神犇告诉我一个非常神的解决方案:
Splay每个点维护的是这个子树的hash
这样的话瞬间就好写多了……
找LCP的时候二分一下答案
  评论这张
 
阅读(34)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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