s是c的后缀,倒过来,s就是c的前缀。
之后建trie树,所有c就是s的子树。
所以问题就转化了求子树k大。
由于可以离线,所以可以把询问挂在节点上。
dfs一遍,用直接转移重儿子,暴力轻儿子的方法维护当前的权值线段树,时间O(nlog^2)。
有了权值线段树,询问时只用O(log)。
感觉会比主席树快,没试过。
加了fread,fwrite后拿了rank1
#include<bits/stdc++.h>
#define gc getchar()
int read()
{
char ch;
while((ch=gc)<'0');
int x=ch-'0';
while((ch=gc)>='0')x=x*10+ch-'0';
return x;
}
const int N=100005,T=300005;
int dy[N],j;
int ch[T][26],tot=1;
int cnt[T],t[T],next[N];
int sz[T],dfn[T],out[T],q[N],son[T];
int k[N],ans[N];
int a[N*3],d;
void clear(int i)
{
for(i+=d;i;i>>=1)--a[i];
}
void add(int i)
{
for(i+=d;i;i>>=1)++a[i];
}
#define L (i<<1)
int qiu(int k)
{
if(k>a[1]) return -1;
int i=1;
while(i<=d)
if(k<=a[L])i=L;
else { k-=a[L];i=L+1; }
return i-d;
}
char s[T];int len;
int to(int &x)
{
if(!x)x=++tot;
return x;
}
void dfs(int x)
{
dfn[x]=tot+1;
int i,y;
for(i=t[x];i;i=next[i]) q[++tot]=i;
for(i=0;i<26;++i)
if(y=ch[x][i])
{
dfs(y);
if(sz[y]>sz[son[x]]) son[x]=y;
}
sz[x]=(out[x]=tot)-dfn[x]+1;
}
void solve(int x)
{
int i,y,c=son[x];
if(sz[c])
{
for(i=0;i<26;++i)
if((y=ch[x][i])!=c&&sz[y])
{solve(y);
for(j=dfn[y];j<=out[y];++j) clear(q[j]);
}
solve(c);
for(j=dfn[x];j<dfn[c];++j) add(q[j]);
for(j=out[x];j>out[c];--j) add(q[j]);
}
else
for(j=dfn[x];j<=out[x];++j) add(q[j]);
for(j=0;j<cnt[x];++j)
{
i=q[dfn[x]+j];
ans[i]=qiu(k[i]);
}
}
int main()
{
int n=read(),i,now,x;
for(i=1;i<=n;++i)
{
scanf("%s",s+1);len=strlen(s+1);
now=1;
for(j=len;j;--j) now=to(ch[now][s[j]-'a']);
++cnt[dy[i]=now];
next[i]=t[now];t[now]=i;
}
for(i=1;i<=n;++i) k[i]=read();
for(d=1;d<n;d*=2);d-=1;
tot=0;
dfs(1);
solve(1);
for(i=1;i<=n;++i) printf("%d\n",ans[i]);
}