专栏文章

题解：P4947 PION后缀自动机

aa_small_penguin
P4947题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipav8yd
此快照首次捕获于
2025/12/03 09:00
3 个月前
此快照最后确认于
2025/12/03 09:00
3 个月前
查看原文
这道题好像基本上没什么难的？

思路

先对每个文件后缀名进行离散化。
再开 5×1055 \times 10^5 棵能够实现区间赋值、区间和的线段树。每棵树用于对每种离散化后的后缀名进行维护。
当然，直接开显然会 MLE，所以要用动态开点。
接下来分操作分析：
  1. 就是 xx 到 yy 之间的点的数量 −1-1。如果你为了求点数再开一个线段树也没人拦你。
  2. 就是重链剖分求区间和。
  3. 就是重链剖分求区间和后再区间赋值。
然后……没然后了，结束了。做完这些后就可以获得 AC 的好成绩。

code

CPP
#include <bits/stdc++.h>
using namespace std;
#define N 100009
#define sp(i,j)i^=j,j^=i,i^=j
#define pd tree[tree[i].ls].d=tree[tree[i].rs].d=0,tree[tree[i].ls].lazy=tree[tree[i].rs].lazy=1
int n,m,res,rk[N],sum;
struct V{
    vector<int> e;
    int size,top,h,d,id,fa,son;
}v[N];
namespace xds{
    int cnt;
    int rt[5*N];
    struct TREE_V{
        int ls,rs,d,lazy;
    }tree[10000009];
    inline void add(int &i,int l,int r,int x,int y){
        if(!i)i=++cnt;
        if(l==r){
            tree[i].d+=y;
            return;
        }
        int mid=(l+r)>> 1;
        if(x<=mid)add(tree[i].ls,l,mid,x,y);
        else add(tree[i].rs,mid+1,r,x,y);
        tree[i].d=tree[tree[i].ls].d+tree[tree[i].rs].d;
    }
    inline void change(int i,int l,int r,int x,int y){
        if(!i)return;
        if(x<=l&&r<=y){
            tree[i].d=0;
            tree[i].lazy=1;
            return;
        }
        if(tree[i].lazy)pd;
        int mid=(l+r)>> 1;
        if(x<=mid)change(tree[i].ls,l,mid,x,y);
        if(mid<y)change(tree[i].rs,mid+1,r,x,y);
        tree[i].d=tree[tree[i].ls].d+tree[tree[i].rs].d;
    }
    inline int ask(int i,int l,int r,int x,int y){
        if(!i)return 0;
        if(x<=l&&r<=y)return tree[i].d;
        if(tree[i].lazy)pd;
        int mid=(l+r)>> 1,t=0;
        if(x<=mid)t+=ask(tree[i].ls,l,mid,x,y);
        if(mid<y)t+=ask(tree[i].rs,mid+1,r,x,y);
        return t;
    }
}
inline void dfs(int u,int fa,int h){
    v[u].h=h,v[u].fa=fa, v[u].size=1,sum=-1;
    for(auto to:v[u].e){
        if(to==fa)continue;
        dfs(to,u,h+1);
        v[u].size+=v[to].size;
        if(sum<v[to].size)v[u].son=to,sum=v[to].size;
    }
}
inline void dfs2(int u,int top){
    v[u].top=top,v[u].id=++res,rk[res]=u;
    if(!v[u].son)return;
    dfs2(v[u].son,top);
    for(auto to:v[u].e){
        if(to==v[u].fa)continue;
        if(to==v[u].son)continue;
        dfs2(to,to);
    }
}
vector<pair<string,int> > _;
unordered_set<string> __;
map<string,int> mp;
inline void slh(){
    res=0;
    for(auto it:__) mp[it]=++res;
    for(auto it:_)xds::add(xds::rt[mp[it.first]],1,n,v[it.second].id,1);
}
inline int dis(int x,int y){
    int ans=0;
    while(v[x].top^v[y].top){
        if(v[v[x].top].h<v[v[y].top].h)sp(x,y);
        ans+=v[x].id-v[v[x].top].id+1,x=v[v[x].top].fa;
    }
    if(v[x].id>v[y].id)sp(x,y);
    ans+=v[y].id-v[x].id+1;
    return ans;
}
inline int ask(int x,int y,int c){
    int ans=0;
    while(v[x].top^v[y].top){
        if(v[v[x].top].h<v[v[y].top].h)sp(x,y);
        ans+=xds::ask(xds::rt[c],1,n,v[v[x].top].id,v[x].id);
        x=v[v[x].top].fa;
    }
    if(v[x].id>v[y].id)sp(x,y);
    ans+=xds::ask(xds::rt[c],1,n,v[x].id,v[y].id);
    return ans;
}
inline void change(int x,int y,int c){
    while(v[x].top^v[y].top){
        if(v[v[x].top].h<v[v[y].top].h)sp(x,y);
        xds::change(xds::rt[c],1,n,v[v[x].top].id,v[x].id);
        x=v[v[x].top].fa;
    }
    if(v[x].id>v[y].id)sp(x,y);
    xds::change(xds::rt[c],1,n,v[x].id,v[y].id);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1,_u,_v;i<n;i++){
        cin>>_u>>_v;
        v[_u].e.push_back(_v),v[_v].e.push_back(_u);
    }
    for(int i=1,k;i<=n;i++){
        cin>>k;
        for(int j=1;j<=k;j++){
            string s;
            cin>>s;
            _.push_back({s,i});
            __.insert(s);
        }
    }
    dfs(1,0,1),dfs2(1,1),slh();
    for(int i=1;i<=m;i++){
        string o,p,z;
        char c;
        int x,y;
        cin>>o>>c>>p>>x>>y;
        if(o=="query"&&p=="p"){
            cout<<dis(x,y)- 1<<"\n";
        }
        if(o=="query"&&p=="e"){
            cin>>c>>c>>z;
            cout<<ask(x,y,mp[z])<<"\n";
        }
        if(o=="del"&&p=="e"){
            cin>>c>>c>>z;
            cout<<ask(x,y,mp[z])<<"\n";
            change(x,y,mp[z]);
        }
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...