自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:36:22，当前版本为作者最后更新于2022-01-25 15:01:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话：我吹爆命运石之门！！1
这道题目主要考察了选手对于某些算法的熟悉度以及 AC 自动机的概念。这个题其实不是很难，但赛时只有和本题目名一样的那位巨佬写了正解（其它的是神秘做法），原因可能是没想到虚树一辈子都想不出来（毕竟这个 trick 我从未见过）。
数据有点水……但是肯定会加强的（但似乎卡不掉？）。

30~50pts

建完 AC 自动机后暴力得到 $cnt$，然后暴力求出第 $k$ 大。（因为数据水，所以你最高甚至可以得到 60pts）

60pts

先看 $k=1$，$k\le5$ 是类似的（这是一个口胡算法）。
我们可以建出 AC 自动机，然后把询问串在 AC 上跑，得到一堆节点，设这个可重集合为 $T$。考虑 $cnt_i$ 的意义是有多少个 $T$ 中节点在 $s_i$ 在 trie 树上的尾节点的子树中。
我们可以直接对于每个 $T$ 中节点进行到根加操作（用树剖+线段树），然后暴力求维护前 $k$ 大的值。最后直接看线段树根节点。

100pts

保留 60pts 中 $cnt_i$ 的意义，我们换一种方式去查询第 $k$ 大。
首先我们可以二分答案，问题转化为求 $cnt_i\ge k$ 的有多少个。
我们发现，对于 $T$ 中的每个点，我们可以不用直接进行到根加操作。因为 $|T|=|S|,\sum |S|\le5\times10^5$，所以我们可以把 $T$ 中的点建成一棵虚树。
接下来，你会发现，对于虚树上的 $u$ 到 $fa_u$，这一段的 $cnt$ 的值是一样的，问题转化为求这一段上面 $w_i\ge \lceil\dfrac{mid}{cnt}\rceil$ 有多少个。一段直上直下的链求上面的值大于等于一个参数有多少个，我们可以用一棵主席树维护。时间复杂度 $O(\sum|T|\log L\log ans)$。

#include<bits/stdc++.h>
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
using namespace std;
inline int reads(char s[]) {
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'z')ch=getchar();
	while(ch>='0'&&ch<='z')s[x++]=ch,ch=getchar();
	s[x]='\0';
	return x;
}
inline int read() {
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}
typedef long long ll;
const int maxn=5e5+5;
struct tree {
	int c[2],siz;
} t[maxn*30];
int tr[maxn][4],fail[maxn],siz[maxn],rt[maxn],v[maxn],n,m,tot=1,cnt,f[maxn][19],d[maxn],zc[maxn],book[maxn],st[maxn],top,p[maxn],pos,lg2[maxn];
char s[maxn];
queue<int> q;
vector<int> e[maxn],w[maxn],bj[maxn];
typedef vector<int>::iterator iter;
bool cmp(int x,int y) {
	return p[x]<p[y];
}
void insert(int u) {
	int len=strlen(s),rt=1;
	for(register int i=0; i<len; i++) {
		int y=s[i]-'a';
		if(!tr[rt][y])tr[rt][y]=++tot;
		rt=tr[rt][y];
	}
	bj[rt].push_back(u);
}
void getfail() {
	for(register int i=0; i<4; i++)tr[0][i]=1;
	q.push(1);
	while(!q.empty()) {
		int u=q.front(),f=fail[u];
		q.pop();
		for(register int i=0; i<4; i++) {
			int j=tr[u][i];
			if(!j) {
				tr[u][i]=tr[f][i];
				continue;
			}
			fail[j]=tr[f][i];
			q.push(j);
		}
	}
}
void add(int &id,int o,int l,int r,int v) {
	id=++cnt,t[id]=t[o],t[id].siz++;
	if(l==r)return;
	int mid=l+r>>1;
	v<=mid?add(lc(id),lc(o),l,mid,v):add(rc(id),rc(o),mid+1,r,v);
}
int ask(int id,int o,int l,int r,int v) {
	if(!id)return 0;
	if(l>=v)return t[id].siz-t[o].siz;
	int mid=l+r>>1,sum=ask(rc(id),rc(o),mid+1,r,v);
	if(v<=mid)sum+=ask(lc(id),lc(o),l,mid,v);
	return sum;
}
void dfs(int u,int fa) {
	rt[u]=rt[fa];
	for(register iter it=bj[u].begin(); it!=bj[u].end(); it++)add(rt[u],rt[u],1,1000,v[*it]);
	d[u]=d[fa]+1,f[u][0]=fa,p[u]=++pos;
	for(register int i=1; i<=lg2[d[u]]; i++)f[u][i]=f[f[u][i-1]][i-1];
	for(iter it=e[u].begin(); it!=e[u].end(); it++)dfs(*it,u);
}
int lca(int x,int y) {
	if(d[x]<d[y])swap(x,y);
	while(d[x]>d[y])x=f[x][lg2[d[x]-d[y]]-1];
	if(x==y)return x;
	for(register int i=lg2[d[x]]-1; i>=0; i--)
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
int check(int u,int fa,int mid) {
	int sum=0;
	siz[u]=book[u];
	for(register iter it=w[u].begin(); it!=w[u].end(); it++)sum+=check(*it,u,mid),siz[u]+=siz[*it];
	if(u!=1)sum+=(mid-1)/siz[u]+1>1000?0:ask(rt[u],rt[fa],1,1000,(mid-1)/siz[u]+1);//小细节，这里的剪枝可以大大优化常数
	return sum;
}
void clear(int u) {
	for(register iter it=w[u].begin(); it!=w[u].end(); it++)clear(*it);
	siz[u]=book[u]=0,w[u].clear();
}
int main() {
	int k,sl1=0,sl2=0;
	n=read(),m=read();
	for(register int i=1; i<=n; i++)reads(s),sl1+=strlen(s),v[i]=read(),insert(i);
	getfail();
	for(register int i=2; i<=tot; i++)e[fail[i]].push_back(i);
	for(register int i=1; i<=tot; i++)lg2[i]=lg2[i-1]+((1<<lg2[i-1])==i);
	dfs(1,0);//建 AC 自动机，fail 树
	while(m--) {
		reads(s),sl2+=strlen(s),k=read();
		int u=1,len=strlen(s);
		for(register int i=0; i<len; i++)u=tr[u][s[i]-'a'],zc[i+1]=u,book[u]++;//得到 T 的所有节点
		sort(zc+1,zc+len+1,cmp),len=unique(zc+1,zc+len+1)-zc-1;
		st[top=1]=zc[1];
		for(register int i=2; i<=len; i++) {
			int la=lca(st[top],zc[i]);
			while(top) {
				if(d[la]>=d[st[top-1]]) {
					if(la!=st[top])w[la].push_back(st[top]),la!=st[top-1]?st[top]=la:top--;
					break;
				}
				w[st[top-1]].push_back(st[top]),top--;
			}
			st[++top]=zc[i];
		}
		while(--top)w[st[top]].push_back(st[top+1]);//建出虚树
		int l=1,r=1e9,ans=0;
		while(l<=r) {
			int mid=l+r>>1;
			if(check(st[1],1,mid)>=k)l=mid+1,ans=mid;
			else r=mid-1;
		}//二分答案
		printf("%d\n",ans);
		clear(st[1]);
	}
}