题解 P3975 【[TJOI2015]弦论】
没人发后缀数组的做法，我来发一波！
戳这里食用更佳ヾ(◍°∇°◍)ﾉﾞ
相信T=0，大家都会做，这是后缀数组的一个经典问题。
具体就是，每个子串都是一个后缀的前缀。
从头到尾扫，每个后缀都会有 n−sa[i]+1−height[i] 个本质不同的子串，即可。
重点是T=1时，怎么用后缀数组解决？
由于我比较菜，我想了一个大暴力，一位一位的枚举！
因为我们前面的字母是确定的，那么当前面的字母一样的时候，后面一个字母一定是单调不下降的。
那我们就能二分求出这个字母最后一个的位置。
我们建一个后缀长度的前缀和，那我们就能求出以这个字母开头的子串有多少个。
当个数大于k时，就确定了这个字母，否则k减去，继续枚举下一个字母。
枚举完一位继续下一位，那我们就能把范围缩小，知道求出答案。
具体看代码……
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,t,k;
long long sum[500005];
char s[500005];
struct SA{
char s[500005];
int tp[500005],rak[500005];
int tax[500005],sa[500005];
int n,m,height[500005];
void build(char str[]){
memcpy(s,str,sizeof(s));
n=strlen(s+1);
build_sa(rak,tp);
build_height();
}
void sort(int a[],int b[]){
for(int i=1;i<=m;i++)tax[i]=0;
for(int i=1;i<=n;i++)tax[a[i]]++;
for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i];
}
bool comp(int r[],int a,int b,int k){
return r[a]==r[b]&&r[a+k]==r[b+k];
}
void build_sa(int a[],int b[]){
for(int i=1;i<=n;i++)
m=max(m,a[i]=s[i]-'a'+1),b[i]=i;
sort(a,b);
for(int p=0,j=1;p<n;j<<=1,m=p){
p=0;
for(int i=1;i<=j;i++)b[++p]=n-j+i;
for(int i=1;i<=n;i++)if(sa[i]>j)b[++p]=sa[i]-j;
sort(a,b);
int *t=a;a=b;b=t;
a[sa[1]]=p=1;
for(int i=2;i<=n;i++)
a[sa[i]]=comp(b,sa[i],sa[i-1],j)?p:++p;
}
for(int i=1;i<=n;i++)rak[sa[i]]=i;
}
void build_height(){
for(int i=1,j=0;i<=n;i++){
if(j)j--;
while(s[i+j]==s[sa[rak[i]-1]+j])j++;
height[rak[i]]=j;
}
}
}a;
int main(){
scanf("%s%d%d",s+1,&t,&k);
a.build(s);
n=strlen(s+1);
if(t==0){
for(int i=1;i<=n;i++){
int c=n-a.sa[i]+1-a.height[i];
if(k<=c){
for(int j=a.sa[i];j<=a.sa[i]+a.height[i]+k-1;j++)
putchar(s[j]);
return 0;
}else k-=c;
}
printf("-1");
}else{
for(int i=1;i<=n;i++) //处理前缀和
sum[i]=sum[i-1]+n-a.sa[i]+1;
if(sum[n]<k)return printf("-1"),0; //子串不够输出-1
int L=1,R=n;
for(int i=1;i<=n;i++){
int tmp=L;
for(int j='a';j<='z';j++){ //枚举 a~z
int l=tmp,r=R;
while(l<=r){ //二分找这个字母的最后一个位置
int mid=l+r>>1;
if(s[a.sa[mid]+i-1]>j)r=mid-1;
else l=mid+1;
}
long long t=sum[r]-sum[tmp-1]-1LL*(r-tmp+1)*(i-1);
//现在枚举的区间有多少个子串
//减是因为减去前面枚举过得位置
if(k<=r-tmp+1){
//现在要查的比现在字母的个数少，说明这个字母就是结束的位置
for(int j=a.sa[tmp];j<=a.sa[tmp]+i-1;j++)
putchar(s[j]);
return 0;
}
if(t>=k){ //说明这位就是这个字母，减去字母个数
L=tmp,R=r;
k-=r-tmp+1;
break;
}
tmp=r+1,k-=t; //不是，继续枚举
}
if(n-a.sa[L]+1==i)L++; //如果下一位为空，就不用算了。
}
}
}