三字典树+离线差分树状数组
这波不抢最优解(喵呜?本喵log时间复杂度跟人家线性的怎么比?)
那就说说为什么要切这道看似毫无吊用的蓝色字符串吧(其实就是毫无吊用)
因为这是我参加S组以来T3T4考场骗分最高的一题,考场代码足足拿了50分,紫题(后来降的蓝)能骗到50分,代码甚至sub1500B,祖坟都要冒青烟了喵,这波直接助力我拿到S组国一。再加上我对字典树的情有独钟,就在备赛NOIP的时候顺手切了嘿嘿
足足花了我10个小时喵呜……

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,an[200005],cn=0;
struct T
{
    vector<int>h,t,x;
    vector<unsigned char>c;
    T()
    {
        h.push_back(-1);
    }
    void rv(int s)
    {
        h.reserve(s);
        if(s>1)
        {
            t.reserve(s-1);
            x.reserve(s-1);
            c.reserve(s-1);
        }
    }
    int ad(const string&s)
    {
        int u=0;
        for(char ch:s)
        {
            int cc=ch-'a',e=h[u],v=-1;
            while(e!=-1)
            {
                if(c[e]==cc)
                {
                    v=t[e];break;
                }
                e=x[e];
            }
            if(v==-1)
            {
                v=h.size();
                h.push_back(-1);
                int d=t.size();
                t.push_back(v);
                c.push_back(cc);
                x.push_back(h[u]);
                h[u]=d;
            }
            u=v;
        }
        return u;
    }
    int go(const string&s)
    {
        int u=0;
        for(char ch:s)
        {
            int cc=ch-'a',e=h[u],v=-1;
            while(e!=-1)
            {
                if(c[e]==cc)
                {
                    v=t[e];break;
                }
                e=x[e];
            }
            if(v==-1) break;
            u=v;
        }
        return u;
    }
};
struct F
{
    int n;
    vector<int>t;
    F(int m=0)
    {
        n=m;
        t.assign(m+2,0);
    }
    void ad(int p,int v)
    {
        for(int i=p+1;i<(int)t.size();i+=i&-i)
            t[i]+=v;
    }
    void rg(int l,int r,int v)
    {
        ad(l,v);
        ad(r,-v);
    }
    int sm(int p)
    {
        int s=0;
        for(int i=p+1;i>0;i-=i&-i)
            s+=t[i];
        return s;
    }
};
void eu(const T&r,vector<int>&a,vector<int>&b)
{
    int m=r.h.size();
    a.assign(m,0);
    b.assign(m,0);
    vector<int>it=r.h,st;
    st.reserve(m);
    st.push_back(0);
    int tm=0;
    a[0]=tm++;
    while(!st.empty())
    {
        int u=st.back(),&e=it[u];
        if(e!=-1)
        {
            int v=r.t[e];
            e=r.x[e];
            a[v]=tm++;
            st.push_back(v);
        }
        else
        {
            b[u]=tm;
            st.pop_back();
        }
    }
}
struct R
{
    string p,e;
};
struct Q
{
    string p,e;
    int id;
};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    unordered_map<string,int>mp;
    mp.reserve((n+q)*2+10);
    mp.max_load_factor(0.7);
    vector<vector<int>>gr(n+1),gq(n+1);
    vector<R>rs;
    vector<Q>qs;
    rs.reserve(n);
    qs.reserve(q);
    for(int i=1;i<=n;i++)
    {
        string a,b;
        cin>>a>>b;
        int L=a.size(),u=0;
        while(u<L&&a[u]==b[u])u++;
        if(u==L) continue;
        int v=L-1;
        while(v>=u&&a[v]==b[v])v--;
        string p;
        for(int j=u-1;j>=0;j--)p+=a[j];
        string e;
        for(int j=v+1;j<L;j++)e+=a[j];
        int m=v-u+1;
        string k=a.substr(u,m)+b.substr(u,m);
        auto it=mp.find(k);
        int g;
        if(it==mp.end())
        {
            g=++cn;
            mp.emplace(k,g);
        }
        else g=it->second;
        rs.push_back({p,e});
        gr[g].push_back(rs.size()-1);
    }
    for(int id=0;id<q;id++)
    {
        string a,b;
        cin>>a>>b;
        an[id]=0;
        if(a.size()!=b.size()) continue;
        int L=a.size(),u=0;
        while(u<L&&a[u]==b[u])u++;
        if(u==L) continue;
        int v=L-1;
        while(v>=u&&a[v]==b[v])v--;
        string p;
        for(int j=u-1;j>=0;j--)p+=a[j];
        string e;
        for(int j=v+1;j<L;j++)e+=a[j];
        int m=v-u+1;
        string k=a.substr(u,m)+b.substr(u,m);
        auto it=mp.find(k);
        if(it==mp.end()) continue;
        int g=it->second;
        qs.push_back({p,e,id});
        gq[g].push_back(qs.size()-1);
    }
    for(int g=1;g<=cn;g++)
    {
        if(gq[g].empty()) continue;
        auto&ri=gr[g];
        auto&qi=gq[g];
        int nr=ri.size(),nq=qi.size();
        int sp=0,se=0;
        for(int i:ri)
        {
            sp+=rs[i].p.size();
            se+=rs[i].e.size();
        }
        T tp,te;
        tp.rv(sp+1);
        te.rv(se+1);
        vector<int>pn(nr),en(nr);
        for(int i=0;i<nr;i++)
        {
            pn[i]=tp.ad(rs[ri[i]].p);
            en[i]=te.ad(rs[ri[i]].e);
        }
        int M=te.h.size();
        vector<int>ti,to;
        eu(te,ti,to);
        int P=tp.h.size();
        vector<int>rh(P,-1),rn(nr);
        for(int i=0;i<nr;i++)
        {
            int u=pn[i];
            rn[i]=rh[u];
            rh[u]=i;
        }
        vector<int>qh(P,-1),qn(nq),qe(nq),qq(nq);
        for(int j=0;j<nq;j++)
        {
            Q&x=qs[qi[j]];
            int u=tp.go(x.p),v=te.go(x.e);
            qe[j]=v;
            qq[j]=x.id;
            qn[j]=qh[u];
            qh[u]=j;
        }
        F f(M);
        vector<pair<int,int>>st;
        st.push_back({0,0});
        while(!st.empty())
        {
            int u=st.back().first,s=st.back().second;
            st.pop_back();
            if(s==0)
            {
                for(int e=rh[u];e!=-1;e=rn[e])
                {
                    int v=en[e];
                    f.rg(ti[v],to[v],1);
                }
                for(int j=qh[u];j!=-1;j=qn[j])
                {
                    int v=qe[j];
                    an[qq[j]]=f.sm(ti[v]);
                }
                st.push_back({u,1});
                for(int e=tp.h[u];e!=-1;e=tp.x[e])
                    st.push_back({tp.t[e],0});
            }
            else
            {
                for(int e=rh[u];e!=-1;e=rn[e])
                {
                    int v=en[e];
                    f.rg(ti[v],to[v],-1);
                }
            }
        }
    }
    for(int i=0;i<q;i++)cout<<an[i]<<'\n';
    return 0;
}

0 条评论

目前还没有评论...