【[AHOI2013]差异】
发布日期:2021-10-25 06:15:14 浏览次数:1 分类:技术文章

本文共 2497 字,大约阅读时间需要 8 分钟。

这个题一看就是为后缀家族设计的

我们看到我们要求的这个柿子

\[\sum_{i=1}^n\sum_{j=i+1}^nT_i+T_j-2\times lcp(T_i,T_j)\]

显然的是前面的那些东西是个定值

就是保证每一个长度都会被其他长度算到,也就是算到\(n-1\)

于是把前面那些东西拿出来就是

\[\frac{(n+1)(n-1)n}{2}\]

之后再看后面那些东西

所有后缀的\(lcp\)的长度?

先来考虑一下如何求两个后缀的\(lcp\)

哈希+二分啊\(SA\)

对于后缀\(i,j\),他们的\(lcp\)长度就是\(min(heighht[rk[i]+1]...height[rk[j]])\)

于是现在的问题转化为求出\(height\)数组所有子区间的最小值的和

我们可以考虑一个动态往序列末尾加数的过程

也就是我们往末尾加一个数都会和之前所有的数形成一个新的区间

考虑快速算出这些区间的最小值的和

我们可以对每一个数存储一个\(a_i\),表示\(i\)到当前序列末尾的最小值是多少

我们每次加入一个数可以对更新一下所有的\(a_i\),把所有比当前加入的数大的\(a_i\)变成当前数就好了

这不就\(T\)了吗

我们发现我们只需要求出所有\(a_i\)的和,并不需要关心这个\(i\)来自哪里,于是我们可以把相等的\(a_i\)放在一起计算,也就是每次新加入一个数就暴力扫一遍把那些比当前加入数大的合并到一个\(a_i\)

看起来复杂度并不科学,但是最坏情况下就相当于是一个线段树的复杂度了,\(O(n)\)的,跑的还挺快的

代码

#include
#include
#include
#define re register#define maxn 500005#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define pt putchar(1)inline int read(){ char c=getchar();int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}int n,m,top;LL ans=0,sum=0;char S[maxn];int tax[maxn],sa[maxn],rk[maxn],tp[maxn],height[maxn];int L[maxn],R[maxn],st[maxn];int a[maxn],cnt[maxn];LL pre[maxn];inline void qsort(){ for(re int i=0;i<=m;i++) tax[i]=0; for(re int i=1;i<=n;i++) tax[rk[i]]++; for(re int i=1;i<=m;i++) tax[i]+=tax[i-1]; for(re int i=n;i;--i) sa[tax[rk[tp[i]]]--]=tp[i];}int main(){ scanf("%s",S+1); n=strlen(S+1); m=75; for(re int i=1;i<=n;i++) rk[i]=S[i]-'a'+1,tp[i]=i; qsort(); for(re int w=1,p=0;p
<<=1) { p=0; for(re int i=1;i<=w;i++) tp[++p]=n-w+i; for(re int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w; qsort(); for(re int i=1;i<=n;i++) std::swap(tp[i],rk[i]); rk[sa[1]]=p=1; for(re int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p; } int k=0; for(re int i=1;i<=n;i++) { if(k) --k; int j=sa[rk[i]-1]; while(S[i+k]==S[j+k]) ++k; height[rk[i]]=k; } ans+=height[2]; a[1]=ans;cnt[1]=1,sum=ans; top=1; for(re int i=3;i<=n;i++) { int now=1; while(top&&height[i]<=a[top]) now+=cnt[top],sum-=a[top]*cnt[top],top--; cnt[++top]=now; a[top]=height[i]; sum+=cnt[top]*a[top]; ans+=sum; } printf("%lld\n",(LL)(n-1)*(LL)(n+1)*(LL)n/2ll-2ll*ans); return 0;}

转载于:https://www.cnblogs.com/asuldb/p/10205640.html

转载地址:https://blog.csdn.net/weixin_30872671/article/details/99090619 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【[CQOI2018]交错序列】
下一篇:值转换器IValueConverter

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月24日 06时21分37秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

proto 客户端 JAVA_Kubernetes官方java客户端之五:proto基本操作 2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现 2019-04-21
java ajax 修改数据库数据库数据库_AJAX 自学练习 无刷新提交并修改数据库数据并显... 2019-04-21
java并发编程指南博客_Java并发编程-synchronized指南 2019-04-21
java怎么中断阻塞状态_java并发编程()阻塞方法与中断方法 2019-04-21
java zlib 位运算_位运算入门:找出一个二进制数的最右端的第一个1;计算一个二进制数中1的个数;找出数组中唯一一个出现次数为奇数的数;找出数组中唯二两个出现次数为奇数的数... 2019-04-21
java lua热更新_lua热更新学习 2019-04-21
script执行php文件_php命令行(cli)下执行PHP脚本文件的相对路径的问题解决方法... 2019-04-21
apache 2.4 php5.4_apache2.4+php5.4+my sql 5.6,网站经常无故不能访问 2019-04-21
php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息 2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染) 2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢? 2019-04-21
php正则表达式获取图片路径,php 常用正则表达式实例(图片地址,与指定内容获取)... 2019-04-21
脚本语言php是什么意思,PHP脚本语言 2019-04-21
matlab数学规划模型,数学规划模型 2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式... 2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码 2019-04-21
在php脚本中 通过可以获取,在PHP中,可以使用Unix时间戳获取精确的脚本执行时间。... 2019-04-21