P8947 Angels & Demons

· · 题解

P8947 Angels & Demons

因为查询和所有询问串相关，所以在加入询问串时，它对每个模板串的贡献都要考虑到。因此只能对所有模板串统一建出结构。

因为查询和模板串子串相关，所以这个结构需要描述所有模板串的所有子串。我们考虑广义 SAM。

加入询问串 T，考虑它的贡献。我们将 T 输入 SAM，得到它的每个前缀的最长的等于某个模板串子串的后缀长度 L，以及对应状态 p。根据 SAM 的 link 树的性质，可知 T 对某子串产生贡献的充要条件是：

相同的 p 只保留 L 最大的一个，然后删去所有子树内还有其它 p 的 (p, L)。接下来，将所有 p 的父亲到根的链并上所有节点的答案加 1，表示对应状态的所有子串答案均加 1，链加单点查转成单点加子树查。最后将所有 p 的所有长度不大于 L 的子串答案加 1，动态开点线段树维护即可。

说白了，就是把 Divljak 放在广义 SAM 上。

时空复杂度线性对数加线性字符集。

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

constexpr int N = 1e6 + 5;
constexpr int M = N << 4;
constexpr int K = 20;
constexpr int S = 26;

namespace GSAM {
  int node, cnt = 1;
  int son[N][S], len[N], fa[N], anc[K][N];
  int ins(int p, int it) {
    int to = son[p][it];
    if(to && len[p] + 1 == len[to]) return to;
    int cur = ++cnt;
    len[cur] = len[p] + 1;
    while(!son[p][it]) son[p][it] = cur, p = fa[p];
    if(!p) return fa[cur] = 1, cur;
    int q = son[p][it];
    if(len[p] + 1 == len[q]) return fa[cur] = q, cur;
    int cl = ++cnt;
    len[cl] = len[p] + 1;
    memcpy(son[cl], son[q], S << 2);
    fa[cl] = fa[q], fa[q] = fa[cur] = cl;
    while(son[p][it] == q) son[p][it] = cl, p = fa[p];
    return to ? cl : cur;
  }
  void build() {
    for(int i = 0; i < K; i++)
      for(int j = 1; j <= cnt; j++) {
        if(i) anc[i][j] = anc[i - 1][anc[i - 1][j]];
        else anc[i][j] = fa[j];
      }
  }
  int locate(int pos, int L) {
    for(int i = K - 1; ~i; i--) {
      int q = anc[i][pos];
      if(len[q] >= L) pos = q;
    }
    return pos;
  }
  void path(char *s, int m, auto P) {
    int L = 0, p = 1;
    for(int i = 1; i <= m; i++) {
      int it = s[i] - 'a';
      while(p > 1 && !son[p][it]) L = len[p = fa[p]];
      if(son[p][it]) L++, p = son[p][it];
      P[i - 1] = {p, L};
    }
  }
}

namespace BIT {
  int c[N];
  void add(int x, int v) {
    while(x < N) c[x] += v, x += x & -x;
  }
  int query(int x) {
    int s = 0;
    while(x) s += c[x], x -= x & -x;
    return s;
  }
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
}

namespace SEG {
  int node, R[N], ls[M], rs[M], val[M];
  void modify(int l, int r, int p, int &x) {
    if(!x) x = ++node;
    val[x]++;
    if(l == r) return;
    int m = l + r >> 1;
    if(p <= m) modify(l, m, p, ls[x]);
    else modify(m + 1, r, p, rs[x]);
  }
  int query(int l, int r, int ql, int qr, int x) {
    if(ql <= l && r <= qr || !x) return val[x];
    int m = l + r >> 1, ans = 0;
    if(ql <= m) ans = query(l, m, ql, qr, ls[x]);
    if(m < qr) ans += query(m + 1, r, ql, qr, rs[x]);
    return ans;
  }
}

using GSAM::fa;
using GSAM::len;
using GSAM::cnt;

int n, q, lg[N], w0, A, B, C = 1;
string str[N];
vector<int> pos[N], e[N];

int dn, dfn[N], dep[N], sz[N], mi[K][N];
void dfs(int id) {
  dfn[id] = ++dn, sz[id] = 1;
  mi[0][dn] = fa[id], dep[id] = dep[fa[id]] + 1;
  for(int it : e[id]) dfs(it), sz[id] += sz[it];
}
bool isa(int u, int v) {
  return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u];
}
int get(int x, int y) {
  return dep[x] < dep[y] ? x : y;
}
int lca(int u, int v) {
  if(u == v) return u;
  if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
  int d = lg[v - u++];
  return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}

int main() {
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q >> w0;
  if(w0) cin >> A >> B >> C;
  for(int i = 1, lst = 1; i <= n; i++, lst = 1) {
    cin >> str[i], pos[i].resize(str[i].size());
    for(int j = 0; j < str[i].size(); j++) {
      lst = pos[i][j] = GSAM::ins(lst, str[i][j] - 'a');
    }
  }
  GSAM::build();
  for(int i = 2; i <= cnt; i++) e[fa[i]].push_back(i);
  for(int i = 2; i <= cnt; i++) lg[i] = lg[i >> 1] + 1;
  dfs(1), assert(cnt == dn);
  for(int i = 1; i <= lg[cnt]; i++) {
    for(int j = 1; j + (1 << i) - 1 <= cnt; j++) {
      mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    }
  }

  for(int _ = 1, lst = 0; _ <= q; _++) {
    int op, x = (1ll * A * lst + B) % C;
    cin >> op;
    if(op == 1) {
      static char s[N];
      cin >> s + 1;
      int m = strlen(s + 1);
      if(w0) {
        for(int i = 1; i <= m; i++) {
          swap(s[i], s[x % m + 1]);
          x = (1ll * A * x + B) % C;
        }
      }
      static pair<int, int> P[N], Q[N];
      GSAM::path(s, m, P);
      sort(P, P + m, [&](auto a, auto b) {
        return a.fi != b.fi ? dfn[a.fi] < dfn[b.fi] : a.se < b.se;
      });
      int c = 0;
      for(int i = 0; i < m; i++) {
        while(c && isa(Q[c - 1].fi, P[i].fi)) c--;
        Q[c++] = P[i];
      }
      if(c == 1 && Q[0].fi == 1) continue;
      for(int i = 0; i < c; i++) {
        int id = Q[i].fi;
        BIT::add(dfn[fa[id]], 1);
        if(i) BIT::add(dfn[lca(fa[id], Q[i - 1].fi)], -1);
        SEG::modify(len[fa[id]] + 1, len[id], Q[i].se, SEG::R[id]);
      }
    }
    else {
      int p, l, r;
      cin >> p >> l >> r;
      if(w0) {
        p = (p + x) % n + 1;
        x = (1ll * A * x + B) % C;
        l = (l + x) % str[p].size() + 1;
        x = (1ll * A * x + B) % C;
        r = (r + x) % str[p].size() + 1;
        x = (1ll * A * x + B) % C;
        if(l > r) swap(l, r);
      }
      int L = r - l + 1;
      p = GSAM::locate(pos[p][r - 1], L);
      int ans = BIT::query(dfn[p], dfn[p] + sz[p] - 1);
      ans += SEG::query(len[fa[p]] + 1, len[p], L, len[p], SEG::R[p]);
      cout << (lst = ans) << "\n";
    }
  }

  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}