AcWing 2572. 生成魔咒(详细注释)
原题链接
困难
作者:
师附真香王
,
2021-01-13 17:51:07
,
所有人可见
,
阅读 472
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 1e6+5;
typedef long long LL;
LL ans[N];
int n,m;
int w[N];
int u[N],d[N];
int x[N],y[N],sa[N],height[N],rk[N],c[N];
unordered_map<int,int>hs;//离散化,求出c数组桶中最多需要的下标m
int get(int x){
if(hs.count(x)==0)hs[x]=++m;
return hs[x];
}
void get_sa(){
//基数排序:先按第一关键字排序
for(int i = 1;i <= n;i++)c[x[i] = w[i]]++;
for(int i = 1;i <= n;i++)c[i]+=c[i-1];
for(int i = n;i;i--)sa[c[x[i]]--] = i;
for(int k = 1;k <= n;k <<= 1){
//按第二关键字排序
int num = 0;
for(int i = n - k + 1;i <= n;i++)y[++num] = i;//从n-k+1到n都没有第二关键字,字典序最小,放在前面
for(int i = 1;i <= n;i++)
if(sa[i]>k)y[++num] = sa[i] - k;//sa[i]>k说明可以当做前面某个的第二关键字,这里的i是按顺序排好之后的i,比如排序前为3 1 2 4 5,排好序后为 5 3 2 1 4,sa[4]就是第四位1对应的排序前排名2,即sa[4]=2
for(int i = 1;i <= m;i++)c[i] = 0;
for(int i = 1;i <= n;i++)c[x[i]]++;
for(int i = 1;i <= n;i++)c[i]+=c[i-1];
for(int i = n;i;i--)sa[c[x[y[i]]]--] = y[i],y[i] = 0;
//在第二关键字排好的基础上排第一关键字
swap(x,y);
x[sa[1]] = 1,num = 1;
//num为离散化的下标。如果num=n就说明都排好了,不存在num一直小于n的情况,因为后缀一定长度不同。
for(int i = 2;i <= n;i++)x[sa[i]] = (y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num == n)break;
m = num;
}
}
void get_height(){
//h[i]>=h[i-1]-1的应用
for(int i = 1;i <= n;i++)rk[sa[i]] = i;
for(int i = 1,k = 0;i <= n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j = sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&w[i+k]==w[j+k])k++;
height[rk[i]] = k;
}
}
int main(){
scanf("%d",&n);
for(int i = n;i;i--)scanf("%d",&w[i]),w[i] = get(w[i]);//细节:从后往前读入
get_sa();
get_height();
LL res = 0;
for(int i = 1;i <= n;i++){
res+=n-sa[i]+1-height[i];//res的初始化,完全状态下的res
u[i] = i-1,d[i] = i+1;
}//双链表,u存向下的下标,d存向上的下标
d[0] = 1,u[n+1] = n;//边界
for(int i = 1;i <= n;i++){//细节:从前往后删掉。如果60行选择1到n读入,这里就要从n到i删掉元素.
ans[i] = res;
int k = rk[i],j = d[k];
res-=n - sa[k] + 1 - height[k];//删掉该元素的贡献(k和k-1之间的height)
res-=n - sa[j] + 1 - height[j];//删掉该元素的贡献(k+1和k之间的height)
height[j] = min(height[j],height[k]);
res+=n-sa[j]+1-height[j];//加上k-1和k+1之间的贡献
d[u[k]] = d[k],u[d[k]] = u[k];//更新双链表
}
for(int i = n;i;i--)printf("%lld\n",ans[i]);
return 0;
}