C++(clang++11) 解法, 执行用时: 815ms, 内存消耗: 310648K, 提交时间: 2020-11-28 20:03:08

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid (l+r>>1)

using namespace std;
const int N=500005;
typedef long long LL;
char s[N];
LL n,m,x,tot,lst,trf[N<<1][26],len[N<<1],fa[N<<1],son[N<<1][26],vt[N<<1],bin[N],p[N<<1],rk[N<<1];
LL k,siz[N<<1],c[N<<1];

int ins(int c)
{
	int x=++tot,u=lst,v;
	lst=tot,len[x]=len[u]+1;
	for(; u && !trf[u][c]; trf[u][c]=x,u=fa[u]);
	if(!u) fa[x]=1;
	else if(len[u]+1==len[v=trf[u][c]]) fa[x]=v;
	else
	{
		int w=++tot;
		len[w]=len[u]+1,fa[w]=fa[v];
		memcpy(trf[w],trf[v],sizeof(trf[v]));
		for(fa[v]=fa[x]=w; u && trf[u][c]==v; trf[u][c]=w,u=fa[u]);
	}
	::c[x]=1;
	return x;
}

LL query(LL a,LL b)
{
	return (a+b)*(b-a+1)/2;
}

void dfs(int x)
{
	++tot;
	vt[tot]=x;
	siz[tot]=siz[tot-1]+c[x]*query(len[fa[x]]+1,len[x]);
	rep(i,0,25) if(son[x][i]) dfs(son[x][i]);
}

int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	tot=lst=1;
	repd(i,n,1) p[ins(s[i]-'a')]=i;
	rep(i,1,tot) ++bin[len[i]];
	rep(i,1,n) bin[i]+=bin[i-1];
	rep(i,1,tot) rk[bin[len[i]]--]=i;
	repd(i,tot,2)
	{
		int x=rk[i];
		p[fa[x]]=p[x],c[fa[x]]+=c[x];
		int L=len[fa[x]];
		son[fa[x]][s[p[x]+L]-'a']=x;
	}
	tot=0;
	dfs(1);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%lld",&k);
		int l=1,r=tot;
		while(l<=r)
			siz[mid]>=k?r=mid-1:l=mid+1;
		k-=siz[r],x=vt[r+1];
		int Lf=len[fa[x]],L=len[x];
		l=Lf+1,r=L;
		while(l<=r)
		{
			LL tmp=c[x]*query(l,mid);
			if(tmp<k) k-=tmp,l=mid+1;
			else r=mid-1;
		}
		k=(k-1)%l+1;
		putchar(s[p[x]+k-1]);
	}
	puts("");
	return 0;
}