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

ydc的博客

 
 
 

日志

 
 

bzoj 2534  

2013-11-28 19:55:38|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上学期苏雨翔找我问这题
我想了想发现我不会……
后来我发现集训队作业有一堆这道题的题解
然后我就丢给了他让他自己看

于是今天考试考了这道题
我就吐血了
本着总该比去年厉害一点点的想法想了一下
发现还是只能想到去年想到的
于是只好怒敲暴力了T_T

另外吐槽苏雨翔竟然也只有暴力分!!!(“我当时没去管这道题了,然后把这题跟天哥讲了”——by “颓狗”苏雨翔)


这题应该是有很多做法的
所以在很古老的集训队作业里能找到很多题解
我就不考古了……我猜那个时候这题应该是个比较有意思的题目吧,不然也就不会备受集训队作业青睐了
但我今天在这里讲的,是来自翱犇的另一个比较现代化做法

后缀数组有这么一个经典模型
你按照height排序,从大到小依此扫,就相当于在不断合并两个东西,最后将n个后缀全部合并
所以我们经常用一个可以支持合并的数据结构,合并的时候每次统计分别在两边的数对对答案的贡献
比如翱犇在bzoj出的str这道题

支持合并的数据结构?
众所周知splay是有启发式合并的
但是更加现代化的是今年冬令营上主席讲的线段树合并
非常优美而神奇的小技巧,让这个模型的威力大大加强

好吧,我们来看看这道题
化一下式子是ΣLCP(i,j)>=j-i-g j-i>g
利用那个经典思路,我们枚举LCP(i,j),这是O(n)个的。每次将两个区间合并成一个区间也很容易做到
现在要做的就是,我们有区间[L1,R1][L2,R2],统计i∈[L1,R1],j∈[L2,R2],他们能对答案造成贡献
于是我们用主席树,以Sa[i]为权值建值域线段树,维护size信息
就可以统计对于i有多少配对的j或者对于j有多少配对的i了
主席树的合并是n log n的
统计显然可以用启发式合并
所以复杂度是n log^2 n

在主席树这个现代化的数据结构以及线段树合并这个现代化的做法(其实相对于信息学的发展已经很古老了),我们有了新的武器处理字符串问题
听lyy说其实正解还是比较神的……有时间去看看前辈们的做法吧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 50010
using namespace std;
typedef long long LL;
LL ans;
char str[maxn];
int n,g;
int Sa[maxn],rank[maxn],height[maxn];
int father[maxn];
struct Node
{
Node *lc,*rc;
int size;
}*Root[maxn];
Node* Insert(int l,int r,int p)
{
Node* it=new Node;
it->size=1;
if(l==r)
return it;
int mid=(l+r)>>1;
if(p<=mid)
it->lc=Insert(l,mid,p);
else
it->rc=Insert(mid+1,r,p);
return it;
}
int Query(Node *p,int l,int r,int x,int y)
{
if(p==0)
return 0;
if(l==x&&r==y)
return p->size;
int mid=(l+r)>>1;
if(y<=mid)
return Query(p->lc,l,mid,x,y);
else if(mid<x)
return Query(p->rc,mid+1,r,x,y);
else
return Query(p->lc,l,mid,x,mid)+Query(p->rc,mid+1,r,mid+1,y);
}
Node* merge(Node* a,Node* b)
{
if(a==0)
return b;
if(b==0)
return a;
Node* c=new Node;
c->size=a->size+b->size;
c->lc=merge(a->lc,b->lc),c->rc=merge(a->rc,b->rc);
return c;
}
int Find(int p)
{
if(father[p]!=p)
father[p]=Find(father[p]);
return father[p];
}
void sort(int *a,int *b,int *c,int n,int m)
{
static int sum[maxn];
for(int i=1;i<=m;++i)
sum[i]=0;
for(int i=1;i<=n;++i)
++sum[c[i]];
for(int i=1;i<=m;++i)
sum[i]+=sum[i-1];
for(int i=n;i>=1;--i)
b[sum[c[a[i]]]--]=a[i];
}
void make_Sa()
{
n=strlen(str+1);
static int x[maxn],y[maxn];
for(int i=1;i<=n;++i)
x[i]=str[i],rank[i]=i;
sort(rank,Sa,x,n,256);
rank[Sa[1]]=1;
for(int i=2;i<=n;++i)
rank[Sa[i]]=rank[Sa[i-1]]+(x[Sa[i]]!=x[Sa[i-1]]);
for(int i=1;i<=n;i<<=1)
{
for(int j=1;j<=n;++j)
x[j]=rank[j],y[j]=i+j<=n?rank[i+j]:0,Sa[j]=j;
sort(Sa,rank,y,n,n),sort(rank,Sa,x,n,n);
rank[Sa[1]]=1;
for(int j=2;j<=n;++j)
rank[Sa[j]]=rank[Sa[j-1]]+(x[Sa[j]]!=x[Sa[j-1]]||y[Sa[j]]!=y[Sa[j-1]]);
if(rank[Sa[n]]==n)
return ;
}
}
void debug()
{
for(int i=1;i<=n;++i)
{
printf("(");
for(int j=Sa[i];j<=n;++j)
printf("%d ",str[j]);
printf(") %d\n",height[i]);
}
}
void make_height()
{
for(int i=1,j=0;i<=n;++i)
{
if(j>0)
--j;
if(rank[i]!=1)
while(str[i+j]==str[Sa[rank[i]-1]+j])
++j;
height[rank[i]]=j;
}
}
int calc(int lcp,int L1,int R1,int L2,int R2,Node *p1,Node *p2)
{
if(R1-L1>R2-L2)
swap(L1,L2),swap(R1,R2),swap(p1,p2);
int tot=0;
for(int i=L1;i<=R1;++i)
{
int p=Sa[i];
if(p-g-1>=1)
tot+=Query(p2,1,n,max(1,p-g-lcp),p-g-1);
if(p+g+1<=n)
tot+=Query(p2,1,n,p+g+1,min(p+g+lcp,n));
}
return tot;
}
void work()
{
//debug();
static pair<int,int> pos[maxn];
static int R[maxn];
for(int i=1;i<=n;++i)
pos[i]=make_pair(height[i],i),father[i]=i,R[i]=i;
sort(pos+1,pos+n+1),reverse(pos+1,pos+n+1);
for(int i=1;i<=n;++i)
Root[i]=Insert(1,n,Sa[i]);
for(int j=n,i=1;j>=1;--j)
for(;pos[i].first==j;++i)
{
int a=pos[i].second,b=Find(a-1);
ans+=calc(j,a,R[a],b,R[b],Root[a],Root[b]);
father[a]=b,R[b]=R[a],Root[b]=merge(Root[a],Root[b]);
}
}
int main()
{
scanf("%d %s",&g,str+1);
make_Sa();
make_height();
work();
cout<<ans<<endl;
return 0;
}

  评论这张
 
阅读(494)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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