BZOJ3238 [Ahoi2013]差异 SA+单调栈
2024-08-26 06:15:18
题面
题解
考虑把要求的那个东西拆开算,前面一个东西像想怎么算怎么算,后面那个东西在建出\(height\)数组后相当于是求所有区间\(min\)的和*2,单调栈维护一波即可。
#include<bits/stdc++.h>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define cross(i,k) for (int i=first[k];i;i=last[i])
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int N = 500010;
int n;
ll ans;
char c[N];
int cnt[N],x[N],y[N],SA[N],Rank[N],height[N];
inline void Radix_Sort(){
int Max=0;
For(i,1,n) cnt[x[i]]++,Max=max(Max,x[i]);
For(i,1,Max) cnt[i]+=cnt[i-1];
Dow(i,n,1) SA[cnt[x[y[i]]]--]=y[i];
For(i,1,Max) cnt[i]=0;
}
inline void GetSA(){
For(i,1,n) x[i]=c[i],y[i]=i;
Radix_Sort();
for (int i=1,p=1;p<n;i<<=1){
p=0;
For(j,n-i+1,n) y[++p]=j;
For(j,1,n) if (SA[j]>i) y[++p]=SA[j]-i;
Radix_Sort(),swap(x,y),x[SA[1]]=p=1;
For(j,2,n) x[SA[j]]=(y[SA[j]]==y[SA[j-1]]&&y[SA[j]+i]==y[SA[j-1]+i])?p:++p;
}
For(i,1,n) Rank[SA[i]]=i;
int k=0;
For(i,1,n){
if (Rank[i]==1) continue;k=max(0,k-1);
for (int j=SA[Rank[i]-1];j+k<=n&&i+k<=n&&c[j+k]==c[i+k];k++);
height[Rank[i]]=k;
}
}
int top,q[N],l[N],r[N];
inline ll SumLcp(){
For(i,1,n){
while (top&&height[i]<height[q[top]]) r[q[top--]]=i-1;
q[++top]=i,l[i]=q[top-1]+1;
}
while (top) r[q[top--]]=n;
ll ans=0;
For(i,1,n) ans+=1ll*(r[i]-i+1)*(i-l[i]+1)*height[i];
return ans;
}
int main(){
scanf("%s",c+1),n=strlen(c+1);
GetSA();
For(i,1,n) ans+=1ll*(n-i+1)*(n-i)+1ll*(n-i)*(n-i+1)/2;
printf("%lld",ans-SumLcp()*2);
}
最新文章
- 学习笔记 :DrawText
- TFS二次开发、C#知识点、SQL知识总结目录
- java5 CountDownLatch同步工具
- mybatis热加载的实现
- 【CodeForces 606A】A -特别水的题1-Magic Spheres
- sdut 2416:Fruit Ninja II(第三届山东省省赛原题,数学题)
- struct{0}二
- iOS学习笔记之Category
- [转载+原创]Emgu CV on C# (六) —— Emgu CV on Canny边缘检测
- Ejabberd源码解析前奏--配置
- PostgreSQL的prepare 和 execute 动作背后
- WEB 开发异常:java.lang.ClassNotFoundException
- 11g Rac 切换
- hdu 2066 一个人的旅行 最短路径
- Sublime的Package Control的安装
- struts2.1.6教程十一、注解配置
- poj 2492 a bug&#39;s life 简单带权并查集
- linux操作系统基础篇(二)
- 公牛与状压dp
- python多进程web爬虫-提升性能利器
热门文章
- 阿里云 配置FTP 无法连接问题,2017年7月后
- An impassioned circulation of affection(尺取+预处理)
- NYOJ 202 红黑树 (二叉树)
- python初步学习-python文件操作
- 小程序_请求封装network
- win10-idea2018
- 对RSA的认识
- BZOJ 3958 Mummy Madness
- ftp--pureftpd1.0.46
- pip安装模块时:error: command &#39;gcc&#39; failed with exit status 1