题解 CF204E 【Little Elephant and Strings】
Crabby_Maskiv
2020-02-01 22:05:15
## SA+单调队列
首先转化成$SA$可以解决的问题：对于每一个字符串的每一个后缀，我们找出来自 $k$ 个不同字符串的后缀，使得它们的 $LCP$ 最大，然后这个字符串的答案加上 $LCP$的大小
相当于在统计答案 $(l,r)$ 的个数时，对于每个字符串的每一个 $l$ ，求出 $r$ 最大是多少，然后该字符串的答案加上 $r-l+1$
因此按照套路，我们把这 $n$ 个字符串首尾相接，并且为了防止跨越字符串的子串影响答案，需要在每两个字符中间插入一个间隔符，并且需要**两两不同**
我们发现$LCP$有一个很好的性质：对于两个后缀$i$、$j$，它们在 $SA$ 中的距离越远，$LCP$就越短（结合 “ $LCP$ 是由 $Height$ 数组取区间最小值求得的 ” 可以形象理解）
所以，我们找到的 $k$ 个后缀在SA数组中的排名必须尽可能与该后缀 “近”
如何量化这个 “近” 呢？
我们找出SA数组上所有 “ 包含**恰好** $k$ 个不同字符串中的后缀 ” 的区间，求出这个区间的$LCP$ 作为它的 “价值” ，这样一个后缀的答案就一定在所有包含它的区间中（因为如果包含了大于k个，那么这些后缀一定离它 “ 不够近 ” ），取max即可
用双指针维护，并把这些区间塞到一个vector里，结合维护过程可以得知这样的区间只有$O(N)$个（$N$表示字符串长度和）
然后对于SA数组中的每一个位置求出对应的答案，由于vector里的区间满足左右端点都随着下标递增而单调不降（因为是双指针维护出来的），所以可以抽象成一个区间求max，单调队列维护即可
复杂度$O(N\log N)+O(N)+O(N)=O(N\log N)$
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,k;
int sa[N],rk[N],tmp[N<<1],cnt[N],h[N];
int a[N];
int st[N][20],lg[N];
void SA(){
int i,j,num=m+200;
for(i=1;i<=n;i++) cnt[rk[i]=a[i]]++;
for(i=2;i<=num;i++) cnt[i]+=cnt[i-1];
for(i=1;i<=n;i++) sa[++cnt[rk[i]-1]]=i;
for(j=1;j<n;j<<=1){
for(i=0;i<=num;i++) cnt[i]=0;
for(i=1;i<=n;i++) cnt[rk[i]]++;
for(i=2;i<=num;i++) cnt[i]+=cnt[i-1];
for(i=n-j+1;i<=n;i++) tmp[++cnt[rk[i]-1]]=i;
for(i=1;i<=n;i++)
if(sa[i]>j) tmp[++cnt[rk[sa[i]-j]-1]]=sa[i]-j;
for(i=1;i<=n;i++) sa[i]=tmp[i];
for(i=1;i<=n;i++) tmp[i]=rk[i];
num=0;
for(i=1;i<=n;i++)
rk[sa[i]]=((tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+j]==tmp[sa[i-1]+j])?num:++num);
}
for(i=1;i<=n;i++){
if(rk[i]==1) continue;
h[rk[i]]=max(h[rk[i-1]]-1,0);
int x=sa[rk[i]-1];
while(i+h[rk[i]]<=n&&a[i+h[rk[i]]]==a[x+h[rk[i]]]) h[rk[i]]++;
}
for(i=1;i<=n;i++) st[i][0]=h[i];
for(j=1;(1<<j)<n;j++){
for(i=1;i+(1<<j)-1<=n;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
string s[N];
int len[N];
int pos[N];
ll ans[N];
inline int qmin(int l,int r){
if(l>r) return len[sa[r]];
int len=lg[r-l+1];
return min(st[l][len],st[r-(1<<len)+1][len]);
}
int q[N],hd,tl;
struct seg{
int l,r,w;
inline seg(int l,int r,int w):l(l),r(r),w(w){}
};
vector<seg> v;
int main(){
int i,j;
cin>>m>>k;//我设n为字符串总长，m为字符串个数
lg[1]=0;for(i=2;i<N;i++) lg[i]=lg[i-1]+(1<<lg[i-1]+1==i);
for(i=1;i<=m;i++){
cin>>s[i];int l=s[i].length();
for(j=0;j<l;j++){
a[++n]=s[i][j]-'a'+m;
pos[n]=i;len[n]=l-j;
}
a[++n]=i;
}
a[n--]=0;
SA();//求SA,Height
memset(cnt,0,sizeof(cnt));
int p=m,ck=0;
//循环变量从m开始是因为前m-1个一定是分隔符打头，没有意义
for(i=m;i<=n;i++){//预处理区间以及价值
int x=pos[sa[i]];//注意枚举顺序是sa[1]~sa[n]，而不是1~n
if(!cnt[x]) ck++;
cnt[x]++;
while(ck>=k){
if(ck==k) v.push_back(seg(p,i,qmin(p+1,i)));
if(cnt[pos[sa[p]]]==1){
if(ck==k) break;
ck--;
}
cnt[pos[sa[p]]]--;p++;
}
}
// for(auto x:v) cout<<x.l<<" "<<x.r<<" "<<x.w<<endl;
p=0;
for(i=m;i<=n;i++){//单调队列统计答案
while(hd<tl&&v[q[hd]].r<i) hd++;
while(p<v.size()&&v[p].l<=i){
while(hd<tl&&v[p].w>=v[q[tl-1]].w) tl--;
q[tl++]=p;
p++;
}
if(hd==tl) continue;
ans[pos[sa[i]]]+=v[q[hd]].w;
}
for(i=1;i<=m;i++) cout<<ans[i]<<" ";
return 0;
}
```