题解：P8947 Angels & Demons

· · 题解

考虑对所有 S 建 GSAM，然后询问肯定是在 GSAM 上倍增找到对应 S_p[l,r] 的节点 p，再处理子树信息。

考虑如何处理 T 串。我们直接把 T 放在 GSAM 上跑，求出每个节点的最大匹配长度 L_u。

那么，一个节点 u 中的串 S[l,r] 在 T 中出现过就要求：

对于第一个，我们直接 u 到 root 的路径做链加。当然，可以改为区间和、单点加，可以使用树状数组维护。

对于第二个，对每个结点开一个动态开点线段树，来处理不同 r-l+1 时 u 的贡献。要做区间加，单点查，但是也可以改为区间查、单点插入。

最大的问题是：如何去除重复的部分？

每个 T 只能贡献一次，而多次链加会重复加某些节点，我们期望的效果是得到所有链的并的加。

另外，如果一个位置被链加了，那么它的第二种贡献是没有用的。那么我们还要去除所有子树内有匹配的点，因为这种点的链加和第二种贡献都是没有用的。

更通俗来讲，我们找出所有被匹配了点，把它们建成虚树，然后就只有叶子应该保留。

我们考虑如何不建出虚树但能找到所有的叶子。

考虑从 dfs 序的角度来看。按照 dfs 序对这些点排序，记排序的结果为 \{p_i\}。那么，如果 p_i 在 p_{i-1} 的子树里，显然是可以删去 p_{i-1}。容易发现，这样处理之后就已经只剩叶子了，毕竟如果 p_{i-1} 没有被 p_i 删去，说明 p_i 的 dfs 序已经超出了 p_{i-1} 的出栈序。

得到叶子之后，链加仍然不是并集，我们发现相邻两个叶子的路径上，lca 以上的部分被重复加了一次，做一个链减即可。

这样我们在查询时，就可以直接考虑这两种贡献了。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define LG(x) (31^__builtin_clz(x))
#define SIZIO (1<<22)
#define gc() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,SIZIO,stdin))==rp1?EOF:*rp1++)
#define pc(c) ((wrp==wbuf+SIZIO)&&(fwrite(wbuf,1,SIZIO,stdout),wrp=wbuf),(*wrp++)=c)
char buf[SIZIO+1],*rp1,*rp2;
char wbuf[SIZIO+1],*wrp=wbuf;
inline void read(char &c){c=gc();while(c<33||c>126) c=gc();}
inline void read(char *s){
    char ch=gc();
    while(ch<33||ch>126)ch=gc();
    while(ch>=33&&ch<=126) (*s++)=ch,ch=gc();
    *s=0;
}
inline int read(){
    int d=0,f=0;char ch=gc();
    while (!isdigit(ch)) f|=(ch=='-'),ch=gc();
    while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-'0',ch=gc();
    return f?-d:d;
}
inline void write(int n){
    if (n<0) n=-n,pc('-');
    int stk[35],tp=0;
    do{stk[++tp]=n%10,n/=10;}while (n);
    while (tp) pc(stk[tp--]+'0');
} 
inline void fmax(int &x,int y) {(x<y)&&(x=y);}
inline void fmin(int &x,int y) {(x>y)&&(x=y);}
const int N=100005,M=1000005,LG2=22;
char s[M];
int n,q,w0,A,B,C,le[N],lstans,up,tot=1,idx=1,tim;
vector <int> v[N];
int fa[M],len[M],ch[M][26],st[M];
inline int extend(int c,int lst){
    if (ch[lst][c]&&len[ch[lst][c]]==len[lst]+1) return ch[lst][c];
    int p=lst,q,nq,np=++tot,flag=0;
    len[np]=len[p]+1;
    for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np,st[p]|=1<<c;
    if (!p) fa[np]=1;
    else {
        q=ch[p][c];
        if (len[q]==len[p]+1) fa[np]=q;
        else {
            if (p==lst) np=0,flag=1,tot--;
            nq=++tot;
            for (int i=st[q],x;i;i-=i&-i) 
                x=LG(i&-i),ch[nq][x]=ch[q][x];
            st[nq]=st[q],len[nq]=len[p]+1,fa[nq]=fa[q],fa[np]=fa[q]=nq;
            for (;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
    return flag?nq:np;
}

int e[M],ne[M],h[M],dep[M],ff[LG2][M],bg[M],ed[M];
inline void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u){
    bg[u]=++tim,ff[0][u]=fa[u],dep[u]=dep[fa[u]]+1;
    for (int i=1;(1<<i)<=dep[u];i++) ff[i][u]=ff[i-1][ff[i-1][u]];
    for (int i=h[u];i;i=ne[i]) dfs(e[i]);
    ed[u]=tim;
}

inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=LG(dep[x]);i>=0;i--) 
        if (dep[x]-(1<<i)>=dep[y]) x=ff[i][x];
    if (x==y) return x;
    for (int i=LG(dep[x]);i>=0;i--)
        if (ff[i][x]!=ff[i][y]) x=ff[i][x],y=ff[i][y];
    return ff[0][x];
}

inline void init(){
    n=read(),q=read(),w0=read();
    if (w0) A=read(),B=read(),C=read();
    for (int i=1,lst;i<=n;i++) {
        read(s+1),le[i]=strlen(s+1),lst=1,fmax(up,le[i]),v[i].resize(le[i]+1);
        for (int j=1;j<=le[i];j++) v[i][j]=lst=extend(s[j]-'a',lst);
    }
    for (int i=2;i<=tot;i++) add(fa[i],i);
    dfs(1);
}

struct BIT{
    int t[M];
    inline void add(int x,int v){
        for (int i=x;i<=tot;i+=i&-i) t[i]+=v; 
    }
    inline int query(int x){
        int res=0;
        for (int i=x;i;i-=i&-i) res+=t[i];
        return res;
    }
    inline int query(int l,int r) {return query(r)-query(l-1);} 
}tree;

int rt[M];
struct SEG_T{
    int tot;
    struct Tree{int ls,rs,sum;}t[M*30];
    #define ls(u) t[u].ls
    #define rs(u) t[u].rs
    #define mid (l+r>>1)
    void insert(int &u,int x,int l=1,int r=up){
        if (!u) u=++tot;
        t[u].sum++;
        if (l==r) return ;
        if (x<=mid) insert(ls(u),x,l,mid);
        else insert(rs(u),x,mid+1,r); 
    }
    int query(int u,int ql,int qr,int l=1,int r=up){
        if (!u) return 0;
        if (ql<=l&&r<=qr) return t[u].sum;
        int ans=0;
        if (ql<=mid) ans+=query(ls(u),ql,qr,l,mid);
        if (qr>mid) ans+=query(rs(u),ql,qr,mid+1,r);
        return ans;
    }
}DT;

int maxn[M],stk[M],vis[M],tp,bu[M],bcnt;
bool cmp(int x,int y) {return bg[x]<bg[y];}
bool issub(int u,int fa) {return bg[fa]<=bg[u]&&bg[u]<=ed[fa];}
inline void solve1(){
    while (tp){int u=stk[tp--];vis[u]=maxn[u]=0;}
    read(s+1),bcnt=0;
    if (w0){
        int x((1ll*A*lstans+B)%C),l=strlen(s+1);
        for (int i=1;i<=l;i++) 
            swap(s[i],s[x%l+1]),x=(1ll*A*x+B)%C;
    }
    int p=1,l=0;
    for (int i=1;s[i];i++){
        int c=s[i]-'a';
        while (p!=1&&!ch[p][c]) p=fa[p],l=len[p];
        if (ch[p][c]) p=ch[p][c],l++;
        if (!vis[p]) stk[++tp]=p,vis[p]=1;
        fmax(maxn[p],l);
    }
    sort(stk+1,stk+tp+1,cmp);
    for (int i=1;i<=tp;i++)
        if (!issub(stk[i+1],stk[i])||i==tp) {
            int u=stk[i];bu[++bcnt]=stk[i];
            tree.add(bg[fa[u]],1),DT.insert(rt[u],maxn[u]);
        }
    for (int i=1;i<bcnt;i++){
        int u=bu[i],v=bu[i+1],lca=LCA(u,v);
        tree.add(bg[lca],-1);
    }
}
inline void solve2(){
    int p=read(),l=read(),r=read();
    if (w0) {
        int x=(1ll*A*lstans+B)%C;
        p=(p+x)%n+1,x=(1ll*A*x+B)%C;
        l=(l+x)%le[p]+1,x=(1ll*A*x+B)%C;
        r=(r+x)%le[p]+1;if (l>r) swap(l,r);
    }
    int u=v[p][r];
    for (int i=LG(dep[u]),w;i>=0;i--) if ((w=ff[i][u])&&len[w]>=r-l+1) u=w;
    write(lstans=tree.query(bg[u],ed[u])+DT.query(rt[u],r-l+1,up)),pc('\n');
}

int main(){
    init();
    while (q--) 
        if (read()==1) solve1();
        else solve2();
    fwrite(wbuf,1,wrp-wbuf,stdout);
    return 0;
}

::::