Description
给出一个仅含小写字母的字符串\(s(|s|\leq10^5)\)，正整数\(k\)和每种字母的权值\(c_i(c_i\leq100)\)。一个字符串的权值定义为每个字符的权值之和，求\(s\)的第\(k\)小的子串的权值，不存在输出-1。
Solution
二分答案，然后使用任意一种后缀数据结构 check 即可。这里使用SAM。
check(x)统计所有权值小于\(x\)的子串数目。SAM的每一个状态都代表一系列后缀相同的子串，具体来说，状态\(p\)代表的子串是右端点属于\(right(p)\)，长度为\([len(prt[p])+1,len(p)]\)?的子串。由于权值都是正的所以这些子串的权值随左端点增大而减小，于是可以二分出使得权值小于\(x\)的左端点数目（二分长度也可）。
有的同学可能要说啊\(right(p)\)求不出来啊！实际上只要记录\(right(p)\)的一个元素即可，由于插入第\(i\)个字符时一定有\(i\in right(last)\)，那么构建完SAM之后DFS一遍SAM或者parent树，即可将\(i\)传递到每个状态。
Code
//Display Substring
#include <cstdio>
#include <algorithm>
using std::upper_bound;
typedef long long lint;
const int N=2e5+10;
int n,c[256]; lint k; char s[N];
int sum[N];
int rt,ndCnt,last;
int ch[N][26],prt[N],len[N];
void ins(int x)
{
int p=last,np=++ndCnt;
last=np,len[np]=len[p]+1;
for(p;!ch[p][x]&&p;p=prt[p]) ch[p][x]=np;
if(!p) {prt[np]=rt; return;}
int q=ch[p][x];
if(len[p]+1==len[q]) {prt[np]=q; return;}
int nq=++ndCnt; len[nq]=len[p]+1;
for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
prt[nq]=prt[q]; prt[q]=prt[np]=nq;
for(p;ch[p][x]==q;p=prt[p]) ch[p][x]=nq;
}
int right[N];
void dfs(int p)
{
if(right[p]) return;
for(int i=0;i<26;i++)
{
int q=ch[p][i]; if(!q) continue;
dfs(q);
if(!right[p]) right[p]=right[q]-1;
}
}
lint check(int x)
{
lint r=0;
for(int p=2;p<=ndCnt;p++)
{
int L=right[p]-len[p],R=right[p]-len[prt[p]];
int t=upper_bound(sum+L,sum+R,sum[right[p]]-x)-sum;
r+=R-t;
}
return r;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&k);
scanf("%s",s+1);
for(int i=‘a‘;i<=‘z‘;i++) scanf("%d",&c[i]);
sum[0]=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+c[s[i]];
rt=last=++ndCnt;
for(int i=1;i<=n;i++) ins(s[i]-‘a‘),right[last]=i;
for(int p=rt+1;p<=ndCnt;p++) if(!right[p]) dfs(p);
int L=1,R=n*200;
while(L<=R)
{
int mid=L+R>>1;
if(check(mid)<k) L=mid+1;
else R=mid-1;
check(mid+1);
}
if(R==n*200) puts("-1");
else printf("%d\n",R);
for(int p=1;p<=ndCnt;p++)
{
for(int i=0;i<26;i++) ch[p][i]=0;
prt[p]=len[p]=right[p]=0;
}
rt=last=ndCnt=0;
}
return 0;
}