题解：P8147 [JRKSJ R4] Salieri

AeeE5x · 2026-04-25 00:38:28 · 题解

前言

数据结构大杂烩。

挺久之前写的题了，当时没写题解，现在补一个。

Solution

发现是多模匹配状物，第一步先建出来 ACAM。

考虑对询问串在 ACAM 上跑一遍，每跑到一个点记一个 \mathrm{cnt}，最后记子树和。

注意到询问串长度和不大，而在 ACAM 上走的点又和询问串的长度相关，所以考虑对过程中所有经过的点建立虚树。

虚树建出来后，先从下到上遍历一遍整棵树，处理出来 \mathrm{cnt} 的子树和信息。

此时的虚树上，父亲到儿子的一条虚树边表示原树上父亲到儿子这条链上（不包含儿子）上的所有点的 \mathrm{cnt} 都等于父亲的 \mathrm{cnt}。

至于没有访问过的那些点，\mathrm{cnt} 和贡献自然是 0。

直接维护 \operatorname{rank} k 太困难了，考虑二分答案。

现在考虑对一个 \mathrm{mid} 如何判定有多少个数是大于等于它的。

每次判定，遍历一遍整棵虚树。对虚树上的每条边 \mathrm{fa}\to x，因为这条链上的 \mathrm{cnt} 都是相同的，所以这相当于询问原树这条链上 v\times \mathrm{cnt}\ge \mathrm{mid} 的结束点的数量。

这个东西可以用一棵主席树维护。

时间复杂度 O(L\log L\log V)，因为值域很小所以空间根本不会爆。

Code

:::info[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;

class segmenttree{
    private:
        struct node{
            int v;
            node *lc,*rc;
            node(int _v=0):v(_v),lc(nullptr),rc(nullptr){}
        };
        vector<node*> roots;
        int wL,wR;

        void pushup(node *p){
            p->v=0;
            if(p->lc) p->v+=(p->lc->v);
            if(p->rc) p->v+=(p->rc->v);
        }

        node *Build(int l,int r){
            node *p=new node(0);
            if(l==r) return p;
            int mid=(l+r)>>1;
            p->lc=Build(l,mid);
            p->rc=Build(mid+1,r);
            pushup(p);
            return p;
        }

        node *Modify(int x,int v,int nowl,int nowr,node *p){
            node *new_p=new node(p->v);
            if(nowl==nowr){
                new_p->v+=v;
                return new_p;
            }
            int mid=(nowl+nowr)>>1;
            if(x<=mid){
                new_p->lc=Modify(x,v,nowl,mid,p->lc);
                new_p->rc=p->rc;
            }else{
                new_p->lc=p->lc;
                new_p->rc=Modify(x,v,mid+1,nowr,p->rc);
            }
            pushup(new_p);
            return new_p;
        }

        int Query(int l,int r,int nowl,int nowr,node *p1,node *p2){
            if(l<=nowl&&nowr<=r) return (p1->v)-(p2->v);
            int mid=(nowl+nowr)>>1;
            int res=0;
            if(l<=mid) res+=Query(l,r,nowl,mid,p1->lc,p2->lc);
            if(r>mid) res+=Query(l,r,mid+1,nowr,p1->rc,p2->rc);
            return res;
        }

        void Debug(node *p,int l,int r){
            if(!p) return;
            printf("Now at (%d,%d), Value=%d.\n",l,r,p->v);
            int mid=(l+r)>>1;
            Debug(p->lc,l,mid);
            Debug(p->rc,mid+1,r);
        }

    public:
        segmenttree():roots(0),wL(0),wR(0){}

        void build(int l,int r){roots.push_back(Build(wL=l,wR=r));}

        int modify(int x,int v,int editversion){
            roots.push_back(Modify(x,v,wL,wR,roots[editversion]));
            return roots.size()-1;
        }

        int query(int l,int r,int queryversion1,int queryversion2){
            return Query(l,r,wL,wR,roots[queryversion1],roots[queryversion2]);
        }

        void debug(int version){
            Debug(roots[version],wL,wR);
        }
}segt;

struct edge{int to,nxt;}e[500010];int head[500010],ecnt=1;
inline void addedge(int x,int y){e[ecnt]={y,head[x]},head[x]=ecnt++;}

struct node{
    int ch[4],fail;
    vector<int> v;
}t[500010];
int nodecnt;

void acam_insert(string s,int v){
    int p=0;
    for(char c:s){
        if(!t[p].ch[c-'a']) t[p].ch[c-'a']=++nodecnt;
        p=t[p].ch[c-'a'];
    }
    t[p].v.push_back(v);
}

queue<int> q;
void build_acam(){
    for(int i=0;i<4;i++) if(t[0].ch[i]) q.push(t[0].ch[i]);
    while(!q.empty()){
        int p=q.front();q.pop();
        for(int i=0;i<4;i++){
            if(t[p].ch[i]){
                t[t[p].ch[i]].fail=t[t[p].fail].ch[i];
                q.push(t[p].ch[i]);
            }else t[p].ch[i]=t[t[p].fail].ch[i];
        }
    }
}
int n,m;
int a[100010];

int fa[500010],siz[500010],dep[500010],son[500010];

void dfs1(int x,int p=0){
    fa[x]=p,siz[x]=1,dep[x]=dep[p]+1,son[x]=nodecnt+1;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]) son[x]=y;
    }
}

int top[500010],dfn[500010],rnk[500010],dfn_cnt;
void dfs2(int x,int p){
    top[x]=p,dfn[x]=++dfn_cnt,rnk[dfn_cnt]=x;
    if(son[x]!=nodecnt+1) dfs2(son[x],p);
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==son[x]) continue;
        dfs2(y,y); 
    }
}

int ver[500010];
void dfs3(int x){
    ver[x]=ver[fa[x]];
    for(int w:t[x].v) ver[x]=segt.modify(a[w],1,ver[x]);
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        dfs3(y);
    }
}

int getlca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) return x;
    return y;
}

int cnt[500010];
void get_cnt(string s,vector<int>&b){
    int p=0;
    for(char c:s){
        p=t[p].ch[c-'a'];
        cnt[p]++,b.push_back(p);
    }
}

void remove_cnt(string s){
    int p=0;
    for(char c:s){
        p=t[p].ch[c-'a'];
        cnt[p]--;
    }
}

int newfa[500010];

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;int v;cin>>s>>v;
        acam_insert(s,i);
        a[i]=v;
    }
    build_acam();
    for(int i=1;i<=nodecnt;i++) addedge(t[i].fail,i);

    segt.build(1,1000);
    dfs1(0);
    dfs2(0,0);
    dfs3(0);

    memset(head,0,sizeof head);
    ecnt=1;

    memset(newfa,-1,sizeof newfa);

    while(m--){
        string s;cin>>s;
        int k;cin>>k;

        vector<int> b;
        get_cnt(s,b);

        sort(b.begin(),b.end(),[&](const int x,const int y){return dfn[x]<dfn[y];});
        b.erase(unique(b.begin(),b.end()),b.end());

        vector<int> c;
        c.push_back(0);
        c.push_back(b[0]);
        for(int i=1;i<(int)b.size();i++){
            c.push_back(getlca(b[i-1],b[i]));
            c.push_back(b[i]);
        }
        sort(c.begin(),c.end(),[&](const int x,const int y){return dfn[x]<dfn[y];});
        c.erase(unique(c.begin(),c.end()),c.end());
        for(int i=1;i<(int)c.size();i++) newfa[c[i]]=getlca(c[i-1],c[i]);

        sort(c.begin(),c.end(),[&](const int x,const int y){return dep[x]>dep[y];});
        for(int x:c) if(newfa[x]!=x) cnt[newfa[x]]+=cnt[x];

        auto check=[&](int mid){
            int ans=0;
            for(int x:c){
                if(!cnt[x]) continue;
                if((mid+cnt[x]-1)/cnt[x]>1000) continue;
                ans+=segt.query((mid+cnt[x]-1)/cnt[x],1000,ver[x],ver[newfa[x]]);
            }
            return ans;
        };

        int l=0,r=inf;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(check(mid)>=k) l=mid;
            else r=mid-1;
        }
        cout<<l<<"\n";

        sort(c.begin(),c.end(),[&](const int x,const int y){return dep[x]<dep[y];});
        for(int x:c) if(newfa[x]!=x) cnt[newfa[x]]-=cnt[x];
        remove_cnt(s);
        for(int x:c) newfa[x]=-1;
    }

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::