bzoj 4516: 生成魔咒 后缀数组
2024-09-04 16:21:10
题目大意
在结尾动态插入字符,每次插入结束后输出当前串中本质不同的字串个数
题解
注意一开始是空串,然后我们我们可以打表观察规律
我们发现一直在开头插入字符和一直在结尾插入字符得到的答案是一样的
所以我们从开头插入字符
那么每次我们相于插入了一个后缀
这样就多了n-sa[i]个前缀
但是这些前缀中有重复的
所以我们要在已经插入的后缀中找出与之最长的lcp长度
减去这个长度就是我们得到的不同的字串个数了
由于求lcp时是对height一直取min
所以我们找最长的lcp是只需要找所有已经计算的了后缀中,rank最接近当前加入的后缀的rank的两个后缀即可
复杂度\(O(nlogn)\)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
const ll maxn = 100010;
ll wa[maxn],wb[maxn],ws[maxn];
ll rank[maxn],height[maxn],sa[maxn];
inline bool cmp(ll *r,ll i,ll j,ll k){
return r[i] == r[j] && r[i+k] == r[j+k];
}
void da(ll *r,ll n,ll m){
ll i,j,p,*x = wa,*y = wb;
for(i=0;i<m;++i) ws[i] = 0;
for(i=0;i<n;++i) ws[x[i] = r[i]]++;
for(i=1;i<m;++i) ws[i] += ws[i-1];
for(i=n-1;i>=0;--i) sa[--ws[x[i]]] = i;
for(j=1,p=1;p<n;j<<=1,m=p){
for(p=0,i=n-j;i<n;++i) y[p++] = i;
for(i=0;i<n;++i) if(sa[i] >= j) y[p++] = sa[i] - j;
for(i=0;i<m;++i) ws[i] = 0;
for(i=0;i<n;++i) ws[x[y[i]]]++;
for(i=1;i<m;++i) ws[i] += ws[i-1];
for(i=n-1;i>=0;--i) sa[--ws[x[y[i]]]] = y[i];
for(swap(x,y),p=1,i=1,x[sa[0]] = 0;i<n;++i)
x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
}
}
inline void get_h(ll *r,ll n){
ll i,j,k=0;for(i=1;i<=n;++i) rank[sa[i]] = i;
for(i=0;i<n;height[rank[i++]] = k)
for(k ? --k : 0,j = sa[rank[i]-1];r[i+k] == r[j+k];++k);
}
ll loger[maxn],minn[maxn][22],n;
inline void pre(){
loger[1] = 0;
for(ll i=2;i<=n;++i){
loger[i] = loger[i-1];
if( (1 << loger[i]+1) == i) ++loger[i];
}
for(ll i=n;i>=1;--i){
minn[i][0] = height[i];
for(ll j=1;i+(1<<j)-1<=n;++j){
minn[i][j] = min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
}
}
}
inline ll lcp(ll x,ll y){
if(x+1 > y) swap(x,y);++x;
ll k = loger[y-x+1];
return min(minn[x][k],minn[y-(1<<k)+1][k]);
}
ll a[maxn],b[maxn];
ll pos_min[maxn<<2],pos_max[maxn<<2],M;
inline void modify(ll x,ll y){
for(pos_min[x+=M]=y,pos_max[x]=y,x>>=1;x;x>>=1){
pos_min[x] = min(pos_min[x<<1],pos_min[x<<1|1]);
pos_max[x] = max(pos_max[x<<1],pos_max[x<<1|1]);
}
}
inline ll query_min(ll s,ll t){
if(s > t) return -1;
ll ret = pos_min[0];
for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
if(~s&1) ret = min(ret,pos_min[s^1]);
if( t&1) ret = min(ret,pos_min[t^1]);
}return ret == pos_min[0] ? -1 : ret;
}
inline ll query_max(ll s,ll t){
if(s > t) return -1;
ll ret = pos_max[0];
for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
if(~s&1) ret = max(ret,pos_max[s^1]);
if( t&1) ret = max(ret,pos_max[t^1]);
}return ret == pos_max[0] ? -1 : ret;
}
int main(){
read(n);for(M=1;M<(n+1);M<<=1);
memset(pos_min, 0x3f,sizeof pos_min);
memset(pos_max,-0x3f,sizeof pos_max);
for(ll i=0;i<n;++i){
read(a[n-i-1]);b[i] = a[n-i-1];
}
sort(b,b+n);
for(ll i=0;i<n;++i){
a[i] = lower_bound(b,b+n,a[i]) - b + 1;
}a[n] = 0;
da(a,n+1,n+1);get_h(a,n);pre();
ll ans = 0;
for(ll i=n-1;i>=0;--i){
ans += n-i;
ll x = query_max(1,rank[i]-1);
ll y = query_min(rank[i]+1,n);
if(x != -1 && y != -1) ans -= max(lcp(rank[i],x),lcp(rank[i],y));
else if(x == -1 && y != -1) ans -= lcp(rank[i],y);
else if(x != -1 && y == -1) ans -= lcp(rank[i],x);
printf("%lld\n",ans);
modify(rank[i],rank[i]);
}
getchar();getchar();
return 0;
}
最新文章
- JAVA中SERIALVERSIONUID的解释
- COCOS2D-X中UI动画导致闪退与UI动画浅析
- [手机取证] Apple正在行动起来封堵后门?
- 45个非常有用的oracle语句(摘自尚学堂)
- 软件工程 speedsnail 冲刺8
- ros的源码阅读
- linux内核中的get_user和put_user
- hdu 5432 Pyramid Split 二分
- Could not find action or result 导致 页面出现404错误
- oracle EBS 基于Host并发程序的开发(转)
- 记录创建企业Wiki的几个开源项目
- Unreal Engine4 蓝图入门
- linux 下ffmpeg和mencoder安装
- 向openwrt 源码添加ap143支持
- HTTP协议分析
- 利用 :before :after伪类实现鼠标悬浮动画效果
- vue安装使用
- PPT设计宝典!十招教你做出拿手的PPT
- GDI基础(3):绘制图片
- 安装和配置Apache服务器(上)
热门文章
- Spring 中StreamUtils教程
- 安装WordPress
- XTUOJ 1176 I Love Military Chess(模拟)
- hdu1316
- mybatis的两种分页方式:RowBounds和PageHelper
- java操作pdf
- 每门课由平时成绩和考试成绩组成,满分为r。现在他知道每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话,小v要花bi 的时间复习,不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金,小v至少要花多少时间复习。
- android 底部菜单栏实现(转)
- OpenCV 中的三大数据类型:CvMat 类型
- 1_Jsp标签_简单自定义