[BZOJ3998][TJOI2015]弦论
Description
对于一个给定长度为N的字符串，求它的第K小子串是什么。
Input
第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output
输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1
Sample Input
aabc0 3
Sample Output
aab
HINT
N<=5*10^5
T<2
K<=10^9
试题分析
既然大家都写后缀自动机写法，那我就来口胡一下后缀数组解法。
虽然后缀数组写法比较麻烦，但是好像写法优秀可以爆踩后缀自动机，否则就要卡卡才能过。
首先第一问本质不同的字串只需要去掉Hei就可以了。
关键在于第二问，我们把后缀数组的Hei求出来，并且得到一个串与下一个串的Hei，然后进行考虑。
显然，一个完整的区间肯定是在它的最左边计算，然后被最小值分成两半，继续计算。
那么我们就分治模拟这个过程，每次RMQ得出区间最小值，然后将区间分成两半就可以了。
细节比较多，有可能是我写丑了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 2147483600;
const int MAXN = 500010;
char str[MAXN+1]; int T,K,N,M;
int tax[MAXN+1],rnk[MAXN+1],tp[MAXN+1],SA[MAXN+1];
int a[MAXN+1]; int Hei[MAXN+1]; int pre[MAXN+1][20],g[MAXN+1][20];
inline void Rsort(){
for(int i=1;i<=M;i++) tax[i]=0;
for(int i=1;i<=N;i++) tax[rnk[tp[i]]]++;
for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
for(int i=N;i>=1;i--) SA[tax[rnk[tp[i]]]--]=tp[i];
return ;
}
inline bool CMP(int x,int y,int w){return tp[x]==tp[y]&&tp[x+w]==tp[y+w];}
inline void Suffix(){
for(int i=1;i<=N;i++) rnk[i]=(int)str[i],tp[i]=i; M=127; Rsort(); int p=1;
for(int w=1;p<N;){
p=0; for(int i=N-w+1;i<=N;i++) tp[++p]=i;
for(int i=1;i<=N;i++) if(SA[i]>w) tp[++p]=SA[i]-w;
Rsort(); swap(rnk,tp); rnk[SA[1]]=p=1;
for(int i=2;i<=N;i++) rnk[SA[i]]=CMP(SA[i],SA[i-1],w)?p:++p;
w<<=1; M=p;
} int las=0;
for(int i=1;i<=N;i++){
int j=SA[rnk[i]-1]; if(las) --las;
while(str[j+las]==str[i+las]) ++las;
Hei[rnk[i]]=las;
}
return ;
}
struct node{int l,r,val; node(int ll=0,int rr=0,int vv=0){l=ll; r=rr; val=vv;}};
int Log[MAXN<<1];
inline int Querymn(int l,int r){
int Lg=Log[r-l+1]; return min(pre[l][Lg],pre[r-(1<<Lg)+1][Lg]);
}
inline int Querylow(int l,int r){
int Lg=Log[r-l+1]; if(pre[l][Lg]<=pre[r-(1<<Lg)+1][Lg]) return g[l][Lg];
else return g[r-(1<<Lg)+1][Lg];
}
int cnt[MAXN+1]; vector<node> vec[MAXN+1];
inline void init(int l,int r,int fa,int low){
if(l>r) return ; if(l==r) {if(Hei[l]<low+1) return ;cnt[fa]+=(Hei[l]-low); vec[fa].push_back(node(low+1,Hei[l],1)); return ;}
int Mn = Querymn(l,r) , pos = Querylow(l,r); cnt[fa]+=(r-l+1)*(Mn-low);
if(Mn>=low+1) vec[fa].push_back(node(low+1,Mn,(r-l+1)));
init(l,pos-1,l,Mn); init(pos+1,r,pos+1,Mn);
}
int main(){
scanf("%s",str+1); N=strlen(str+1);
for(int i=1;i<=N;i++) a[i]=str[i]-'a';
for(int i=2;i<=N;i++) Log[i]=Log[i>>1]+1;
Suffix();
T=read(),K=read();
if(K>N*(N+1)>>1) {
puts("-1"); return 0;
}
if(!T){
for(int i=1;i<=N;i++){
if(K<=N-SA[i]+1-Hei[i]) {
for(int j=SA[i];j<=SA[i]+Hei[i]+K-1;j++)
putchar(str[j]);
return 0;
} else K-=(N-SA[i]+1-Hei[i]);
} puts("-1");
} else{
for(int i=1;i<=N;i++) Hei[i]=Hei[i+1],pre[i][0]=Hei[i],g[i][0]=i;
for(int j=1;j<=19;j++){
for(int i=1;i+(1<<j)-1<=N;i++){
if(pre[i][j-1]<=pre[i+(1<<(j-1))][j-1]) pre[i][j]=pre[i][j-1],g[i][j]=g[i][j-1];
else pre[i][j]=pre[i+(1<<(j-1))][j-1],g[i][j]=g[i+(1<<(j-1))][j-1];
}
} init(1,N,1,0);
for(int i=1;i<=N;i++){
if(K<=cnt[i]+N-SA[i]+1-Hei[i-1]){
int num=0;
for(int j=0;j<vec[i].size();j++){
if(K>(vec[i][j].val+1)*(vec[i][j].r-vec[i][j].l+1))
K-=(vec[i][j].val+1)*(vec[i][j].r-vec[i][j].l+1),num+=vec[i][j].r-vec[i][j].l+1;
else{
int G=K/(vec[i][j].val+1);
for(int k=SA[i];k<=SA[i]+num+G;k++)
putchar(str[k]);
return 0;
}
}
for(int j=SA[i];j<=SA[i]+num+Hei[i-1]+K-1;j++)
putchar(str[j]); return 0;
} else K-=cnt[i]+N-SA[i]+1-Hei[i-1];
}
}
return 0;
}