题解--Salieri

abruce · 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]);
    }
}