知识点: SAM，线段树合并

原题面 Loj Luogu

扯

抄着题解水过去了。
这就是 noi 吗/fad

题意简述

给定模式串 \(S\)，有 \(Q\) 次询问。
每次询问给定询问串 \(T\)，参数 \(l,r\)。
求 \(T\) 的本质不同子串中 没有在 \(S[l:r]\) 中出现过的个数。
\(1\le |S|\le 5\times 10^5\)，\(1\le l\le r\le |S|\)，\(1\le Q\le 10^5\)，\(1\le \sum |T|\le 10^6\)。
特殊性质：有 \(68\%\) 的测试点满足询问的 \(l=1, r=|S|\)。

分析题意

\(T\) 的本质不同子串 没有 在 \(S[l:r]\) 中出现过的个数，等价于 总个数减去出现过的个数。

建出 \(T\) 的 SAM，本质不同子串的总个数 = \(\sum\operatorname{len}(i) - \operatorname{len}(\operatorname{link}(i))\)。
考虑如何快速求得出现过的子串个数。

先考虑特殊性质 \(l=1, r=|S|\)。即需要求得 \(T\) 的本质不同子串 在 \(S\) 中出现的次数。
考虑对于 \(T\) 的每一个前缀 \(T[:i]\)，求得其在 \(S\) 中出现的最长的后缀 \(\operatorname{match}_i\)，可在 \(S\) 的 SAM 上匹配 \(T\) 求得。
具体怎么求详见：如何用 SAM 过 SP1811。

对于每一个 SAM 的状态，其维护的所有串的 \(\operatorname{endpos}\) 相同。
维护 \(T\) 的 SAM 的每个状态 \(i\) 的 \(\operatorname{endpos}\) 中最小的值，设为 \(\operatorname{firend}_i\)。

考虑 \(T\) 的 SAM 的状态 \(i\) 维护的 \(T\) 的子串，它们互为后缀，且其长度在 \([\operatorname{len}(\operatorname{link}(i)) + 1, \operatorname{len}(i)]\) 内。
若 \(\operatorname{match}_{{\operatorname{firend}}_i}\ge \operatorname{len}(\operatorname{link}(i)) + 1\)，表示状态 \(i\) 维护的串中小于等于 \(\operatorname{match}_{{\operatorname{firend}}_i}\) 的在 \(S\) 中出现过。则 \([\operatorname{len}(\operatorname{link}(i)) + 1, \operatorname{match}_{\operatorname{firend}_i}]\) 内的串，均在 \(S\) 中出现过，其它串均在 \(S\) 内未出现。

考虑枚举 \(T\) 的 SAM 的状态，则 \(T\) 的在 \(S\) 中出现过的，本质不同的子串个数，为：

再考虑一开始的补集转化，由于可能存在 \(\operatorname{match}_{\operatorname{firpos}_i}>\operatorname{len}(i)\)，则答案为：

再考虑 \(l,r\) 任意的情况。
发现 \(l,r\) 的改变，只影响上述过程中对 \(\operatorname{match}\) 的预处理。
如果仍按照上述过程进行匹配，可能会匹配到一个不属于 \(S[l:r]\) 的子串。

考虑使用权值线段树合并维护 \(\operatorname{endpos}\) 即可。
合并后的 \(\operatorname{endpos}\) 意义与 SAM 中的原定义不同，代表以该状态代表的串 为后缀的 所有 位置。

设匹配的长度为 \(len\)。若当前匹配到的状态属于 \(S[l:r]\)，等价于匹配到的状态的 \(\operatorname{endpos}\) 中存在 \([l+len-1,r]\) 中的数。

考虑在匹配时增加判断：
设当前状态匹配的长度为 \(len\)，若应该按照对应字符转移到的下一个状态 的 \(\operatorname{endpos}\) 中存在 \([l+len,r]\)，则可转移。否则令 \(len-1\)，再进行检查。
若 \(len = \operatorname{len}(\operatorname{link}(i))\)，令当前匹配的状态转移到 \(\operatorname{link}(i)\)，再重复进行上述检查过程。

复杂度 \(O(n\log n)\) 级别。

爆零小技巧

SAM 分裂状态时，注意状态信息的继承。

代码实现

//知识点：SAM，线段树合并
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define ll long long
#define max std::max
const int kMaxn = 1e6 + 10;
const int kMaxm = 26;
//=============================================================
char S[kMaxn], T[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(ll &fir, ll sec) {
  if (sec > fir) fir = sec;
}
struct SuffixAutomaton {
  int n, last = 1, node_num = 1;
  int firend[kMaxn << 1];
  int ch[kMaxn << 1][kMaxm], len[kMaxn << 1], link[kMaxn << 1];
  void Clear() {
    for (int i = 1; i <= node_num; ++ i) {
      link[i] = len[i] = firend[i] = 0;
      memset(ch[i], 0, sizeof (ch[i]));
    }
    last = node_num = 1;
  }
  void Insert(int c_, int pos_) {
    int p = last, now = last = ++ node_num;
    firend[now] = pos_; len[now] = len[p] + 1;
    for (; p && ! ch[p][c_]; p = link[p]) ch[p][c_] = now;
    if (! p) {link[now] = 1; return ;} 
    int q = ch[p][c_];
    if (len[q] == len[p] + 1) {link[now] = q; return ;}
    int newq = ++ node_num;
    memcpy(ch[newq], ch[q], sizeof(ch[q])); 
    link[newq] = link[q];
    len[newq] = len[p] + 1; 
    firend[newq] = firend[q]; //注意继承
    link[q] = link[now] = newq; 
    for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
  }
};
struct SuffixAutomaton1 {
  #define ls lson[now_]
  #define rs rson[now_]
  SuffixAutomaton sam;
  int edge_num, head[kMaxn], v[kMaxn << 1], ne[kMaxn << 1];
  int node_num, root[kMaxn << 1];
  int lson[kMaxn << 5], rson[kMaxn << 5], sum[kMaxn << 5];
  void TreeInsert(int &now_, int L_, int R_, int pos_) {
    if (! now_) now_ = ++ node_num;
    sum[now_] ++;
    if (L_ == R_) return ;
    int mid = (L_ + R_) >> 1;
    if (pos_ <= mid) TreeInsert(ls, L_, mid, pos_);
    else TreeInsert(rs, mid + 1, R_, pos_);
  }
  int Merge(int x_, int y_, int L_, int R_) {
    if (! x_ || ! y_) return x_ + y_;
    int now_ = ++ node_num;
    sum[now_] = sum[x_] + sum[y_];
    if (L_ == R_) return now_;
    int mid = (L_ + R_) >> 1;
    ls = Merge(lson[x_], lson[y_], L_, mid);
    rs = Merge(rson[x_], rson[y_], mid + 1, R_);
    return now_;
  }
  int Query(int now_, int L_, int R_, int ql_, int qr_) {
    if (! now_) return 0;
    if (ql_ <= L_ && R_ <= qr_) return sum[now_];
    int mid = (L_ + R_) >> 1, ret = 0;
    if (ql_ <= mid) ret += Query(ls, L_, mid, ql_, qr_);
    if (qr_ > mid) ret += Query(rs, mid + 1, R_, ql_, qr_);
    return ret;
  }
  void AddEdge(int u_, int v_) {
    v[++ edge_num] = v_, ne[edge_num] = head[u_], head[u_] = edge_num;
  }
  void Dfs(int u_) {
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      Dfs(v_);
      root[u_] = Merge(root[u_], root[v_], 1, sam.n);
    }
  }
  void Build() {
    sam.n = strlen(S + 1);
    for (int i = 1; i <= sam.n; ++ i) {
      sam.Insert(S[i] - 'a', i);
      TreeInsert(root[sam.last], 1, sam.n, i);
    }
    for (int i = 2; i <= sam.node_num; ++ i) AddEdge(sam.link[i], i);
    Dfs(1);
  }
  #undef ls
  #undef rs
} sam1;

struct SuffixAutomaton2 {
  SuffixAutomaton sam;
  int match[kMaxn << 1];
  void GetMatch(int l_, int r_) {
    int now = 1, nowlen = 0;
    for (int i = 1; i <= sam.n; ++ i) {
      while (true) {
        if (sam1.sam.ch[now][T[i] - 'a'] && 
            sam1.Query(sam1.root[sam1.sam.ch[now][T[i] - 'a']], 
                            1, sam1.sam.n, l_ + nowlen, r_)) {
          now = sam1.sam.ch[now][T[i] - 'a'];
          nowlen ++;
          break;
        }
        if (! nowlen) break;
        nowlen --;
        if (nowlen == sam1.sam.len[sam1.sam.link[now]]) {
          now = sam1.sam.link[now];
        }
      }
      match[i] = nowlen;
    }
  }
  void Build() {
    sam.Clear();
    sam.n = strlen(T + 1);
    for (int i = 1; i <= sam.n; ++ i) {
      sam.Insert(T[i] - 'a', i);
    }
  }
  void Solve() {
    int l = read(), r = read();
    ll ans = 0ll;
    GetMatch(l, r);
    for (int i = 2; i <= sam.node_num; ++ i) {
      ans += max(0, sam.len[i] - max(match[sam.firend[i]], sam.len[sam.link[i]]));
    }
    printf("%lld\n", ans);
  }
} sam2;
//=============================================================
int main() {
  freopen("name.in", "r", stdin);
  freopen("name.out", "w", stdout);
  scanf("%s", S + 1);
  sam1.Build();
  int q = read();
  while (q --) {
    scanf("%s", T + 1);
    sam2.Build(); sam2.Solve();
  }
  return 0; 
}