P11740 题解

dAniel_lele · 2025-04-15 17:11:07 · 题解

真不是给人写的。

先思考操作 3 怎么做。考虑求出每个字符串反串的 SA，然后分别找 s 前面加上 l-1 和 r 在 SA 中的 lower_bound，相减即为答案。

再考虑操作 0，也就是说我们需要在反串的末尾加入字符的同时维护 SA。考虑使用平衡树维护之，每次需要比较两个前缀的大小，可以使用二分哈希比较，这里我们使用更为快捷好写的自然溢出，是可以通过的，可以发现本题出题人还是十分良心的，不像某题解审核组 i 姓同学一天到晚想着卡哈希。

然后是操作 1，本操作跟操作 3 本质相同，唯一的问题是 k 次操作后 y 字符串是什么。显然其应该是一个 y 字符串的前缀，我们记录一下即可。

最后考虑操作 2，由于我们需要字符串赋值，我们显然不能重新构建一遍后缀平衡树。考虑将所有字符串放到一个 Trie 上，那么字符串对应的就是一个节点到根（操作 1 同样可以记录），这样赋值的问题就解决了。至于平衡树第一个想法便是对其进行可持久化，这样复杂度已经对了！然而这样大概会 MLE 且难写。考虑将 Trie 上所有节点对应的 SA 扔到一棵平衡树中，同时维护每个平衡树节点包含了多少个在每个字符串中的 Trie 上节点。对于赋值操作，可以记录一个 to_x 数组表示 x 字符串是赋值前的 to_x 字符串。这样就可以空间线性了。

总复杂度 O((len+q)(\log(len+q)+n)\log(len+q))，可以通过。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
const unsigned int mul=200467;
unsigned int pw[1000005];
unsigned int shash[20][1000005];
int sval[1000005],slen;
int aimpos,aimadd;
int n;
namespace Trie{
    unordered_map<signed,signed> f[500005];
    signed up[20][500005],dep[500005],val[500005];
    unsigned int hsh[20][500005];
    int cnt;
    void init(){
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<20;j++) up[j][i]=0;
            f[i].clear();
        }
        val[1]=-1;
        cnt=1;
    }
    int add(int x,int y){
        if(f[x][y]) return f[x][y];
        f[x][y]=++cnt; dep[cnt]=dep[x]+1,val[cnt]=y;
        up[0][cnt]=x; hsh[0][cnt]=y+1;
        for(int j=1;j<=19;j++){
            up[j][cnt]=up[j-1][up[j-1][cnt]];
            hsh[j][cnt]=hsh[j-1][cnt]+hsh[j-1][up[j-1][cnt]]*pw[1<<(j-1)];
        }
        return cnt;
    }
}
void gethash(vector<int> s){
    slen=s.size(); sval[0]=-1;
    for(int i=1;i<=slen;i++){
        shash[0][i]=s[i-1]+1; sval[i]=s[i-1];
        for(int j=1;(1<<j)<=i;j++) shash[j][i]=shash[j-1][i]+shash[j-1][i-(1<<(j-1))]*pw[1<<(j-1)];
    }
}
int cmp(int x,int y){
    if(x<0){
        if(x==-1){
            x=slen;
            for(int i=19;i>=0;i--){
                if((1<<i)<=min((int)Trie::dep[y],x)){
                    if(Trie::hsh[i][y]==shash[i][x]){
                        y=Trie::up[i][y];
                        x-=(1<<i);
                    }
                }
            }
            return (sval[x]<Trie::val[y])?0:((Trie::val[y]==sval[x])?1:2);
        }
        else{
//          cout<<aimpos<<" "<<aimadd<<" "<<y<<"\n";
            x=aimpos;
            for(int i=19;i>=0;i--){
                if((1<<i)<=min(Trie::dep[x],Trie::dep[y])){
                    if(Trie::hsh[i][x]==Trie::hsh[i][y]){
                        x=Trie::up[i][x];
                        y=Trie::up[i][y];
                    }
                }
            }
//          cout<<x<<" "<<y<<"\n";
            if(x!=1) return (Trie::val[x]<Trie::val[y])?0:((Trie::val[x]==Trie::val[y])?1:2);
            if(Trie::val[y]==aimadd){
                y=Trie::up[0][y];
                if(Trie::val[y]==-1) return 1;
                return 0; 
            }
            return (aimadd<Trie::val[y])?0:2;
        }
    }
    else{
//      bool rep=0;
//      if(x==7&&y==2) cout<<Trie::hsh[0][7]<<" "<<Trie::hsh[0][2]<<" OK\n",rep=1;
        for(int i=19;i>=0;i--){
            if((1<<i)<=min(Trie::dep[x],Trie::dep[y])){
                if(Trie::hsh[i][x]==Trie::hsh[i][y]){
                    x=Trie::up[i][x];
                    y=Trie::up[i][y];
                }
            }
        }
//      if(rep) cout<<x<<" "<<y<<"\n";
        return (Trie::val[x]<Trie::val[y])?0:((Trie::val[x]==Trie::val[y])?1:2);
    }
}
int res[5],root;
namespace Tree{
    const double alpha=0.75;
    const int N=2000005;
    int ver[N],tsz[N][5],sz[N][5],L[N],R[N],tag[N][5];
    int buffer_size,buffer[N],tmp_size[N][5];
    int ntsz[5],nsz[5],ntag[5];
    void init(){
        root=1;
    }
    void new_node(int &rt,int p){
        rt=p; ver[rt]=1;
        for(int i=0;i<n;i++) tsz[rt][i]=sz[rt][i]=0,tag[rt][i]=i;
        L[rt]=R[rt]=0;
    }
    void pushup(int rt){
        if(!rt) return ;
        for(int i=0;i<n;i++) tsz[rt][i]=tsz[L[rt]][i]+sz[rt][i]+tsz[R[rt]][i];
        ver[rt]=ver[L[rt]]+ver[R[rt]]+1;
    }
    void addtrans(int rt,int to[5]){
        for(int i=0;i<n;i++){
            ntsz[i]=tsz[rt][to[i]];
            nsz[i]=sz[rt][to[i]];
            ntag[i]=tag[rt][to[i]];
        }
        for(int i=0;i<n;i++){
            tsz[rt][i]=ntsz[i];
            sz[rt][i]=nsz[i];
            tag[rt][i]=ntag[i];
        }
    }
    void pushdown(int rt){
        if(L[rt]) addtrans(L[rt],tag[rt]);
        if(R[rt]) addtrans(R[rt],tag[rt]);
        for(int i=0;i<n;i++) tag[rt][i]=i;
    }
    bool balance(int rt){
        return alpha*ver[rt]>max(ver[L[rt]],ver[R[rt]]);
    }
    void flatten(int rt){
        if(!rt) return ;
        pushdown(rt);
        flatten(L[rt]);
        buffer[++buffer_size]=rt;
        for(int i=0;i<n;i++) tmp_size[buffer_size][i]=sz[rt][i];
        flatten(R[rt]);
    }
    void build(int &rt,int l,int r){
        if(l>r){
            rt=0; return ;
        }
        rt=buffer[mid];
        for(int i=0;i<n;i++) sz[rt][i]=tmp_size[mid][i];
        build(L[rt],l,mid-1),build(R[rt],mid+1,r);
        pushup(rt);
    }
    void rebuild(int &rt){
        buffer_size=0;
        flatten(rt);
        build(rt,1,buffer_size);
    }
    void add(int &rt,int p,int cg){
//      cout<<rt<<" "<<p<<" "<<cg<<"\n";
        if(!rt){
            new_node(rt,p);
            tsz[rt][cg]=sz[rt][cg]=1;
            return ;
        }
        int sta=cmp(p,rt);
        if(sta==1){
            tsz[rt][cg]++,sz[rt][cg]++;
            return ;
        }
        pushdown(rt);
        if(sta==0) add(L[rt],p,cg);
        if(sta==2) add(R[rt],p,cg);
        pushup(rt);
        if(!balance(rt)) rebuild(rt);
    }
    void qry1(int &rt,int p){ // <p
        if(!rt) return ;
        int sta=cmp(p,rt);
        pushdown(rt);
        if(sta==0){
            qry1(L[rt],p);
            return ;
        }
        if(sta==1){
            for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i];
            return ;
        }
        if(sta==2){
            for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i]+sz[rt][i];
            qry1(R[rt],p);
        }
    }
    void qry2(int &rt,int p){ // <=p
        if(!rt) return ;
        int sta=cmp(p,rt);
        pushdown(rt);
        if(sta==0){
            qry2(L[rt],p);
            return ;
        }
        for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i]+sz[rt][i];
        if(sta==2) qry2(R[rt],p);
    }
    void debug(int &rt){
        if(!rt) return ;
        cout<<rt<<" "<<L[rt]<<" "<<R[rt]<<"\n";
        for(int i=0;i<n;i++) cout<<sz[rt][i]<<" "<<tsz[rt][i]<<" "<<tag[rt][i]<<"  "; cout<<"\n";
        debug(L[rt]),debug(R[rt]);
    }
}
int nowed[5];
int remed[200005][5];
signed main(){
    pw[0]=1; for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*mul;
    Trie::init(),Tree::init();
    int m,ty; cin>>n>>m>>ty;
    int lsta=0;
    for(int i=0;i<n;i++){
        int len; cin>>len;
        nowed[i]=1;
        for(int j=1;j<=len;j++){
            int v; cin>>v;
            nowed[i]=Trie::add(nowed[i],v);
//          cout<<nowed[i]<<" ";
            Tree::add(root,nowed[i],i);
        }
//      Tree::debug(root);
//      cout<<"\n";
    }
    for(int i=0;i<n;i++) remed[0][i]=nowed[i];
    int q; cin>>q;
    for(int i=1;i<=q;i++){
//      Tree::debug(root);
        int tr=lsta*ty;
        int opt; cin>>opt; opt^=tr;
        if(opt==0){
            int x,c; cin>>x>>c; x^=tr,c^=tr; x--;
            nowed[x]=Trie::add(nowed[x],c);
//          cout<<x<<" "<<nowed[x]<<"\n";
            Tree::add(root,nowed[x],x);
        }
        else if(opt==1){
            int x,y,k,l,r; cin>>x>>y>>k>>l>>r; x^=tr,y^=tr,k^=tr,l^=tr,r^=tr; x--,y--;
//          cout<<remed[y][k]<<"\n";
            int ans[5]; memset(ans,0,sizeof(ans));
            memset(res,0,sizeof(res));
            aimpos=remed[k][y]; aimadd=l;
            Tree::qry1(root,-2);
            for(int i=0;i<n;i++) ans[i]-=res[i];//cout<<res[i]<<" "; cout<<"\n";
            memset(res,0,sizeof(res));
            aimpos=remed[k][y]; aimadd=r+1;
            Tree::qry1(root,-2);
            for(int i=0;i<n;i++) ans[i]+=res[i];//cout<<res[i]<<" "; cout<<"\n";
            cout<<(lsta=ans[x])<<"\n";
        }
        else if(opt==2){
            int x,y; cin>>x>>y; x^=tr,y^=tr; x--,y--;
            nowed[x]=nowed[y];
            int to[5]; for(int j=0;j<n;j++) to[j]=j; to[x]=y;
            Tree::addtrans(root,to);
        }
        else{
            int l,r; cin>>l>>r>>slen; l^=tr,r^=tr,slen^=tr;
            vector<int> vc;
            for(int i=1;i<=slen;i++){
                int v; cin>>v; v^=tr; vc.push_back(v);
            }
            vector<int> ex;
            int ans[5]; memset(ans,0,sizeof(ans));
            ex.clear(); ex.push_back(l); for(auto v:vc) ex.push_back(v); gethash(ex);
            memset(res,0,sizeof(res));
            Tree::qry1(root,-1);
            for(int i=0;i<n;i++) ans[i]-=res[i];//cout<<res[i]<<" "; cout<<"\n";
            ex.clear(); ex.push_back(r+1); for(auto v:vc) ex.push_back(v); gethash(ex);
            memset(res,0,sizeof(res));
            Tree::qry1(root,-1);
            for(int i=0;i<n;i++) ans[i]+=res[i];//cout<<res[i]<<" "; cout<<"\n";
            for(int i=0;i<n;i++) cout<<(lsta=ans[i])<<" "; cout<<"\n";
        }
        for(int j=0;j<n;j++) remed[i][j]=nowed[j];
    }
    return 0;
}