library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:warning: string/substring_count_in_substring.hpp

Depends on

Code

#include "ds/fenwicktree/fenwicktree.hpp"
#include "string/basic_substring_structure.hpp"

// pattern S[i,j) を重み w で追加. S[i,j) に含まれる pattern の総和を求める.
// offline で実装している (online 化は易しい)
template <typename WT, bool ONLINE>
struct Substring_Count_in_Substring {
  Basic_Substring_Structure BASS;
  vc<tuple<int, int, WT>> pattern;

  // 各行に対して block を含めず右にあるものの個数
  // 各行に対して block を含めて右にあるものの個数
  vc<WT> R0, R1;
  vc<WT> R0c;
  // 各列の上端に対して, 右下にあるものの個数
  vc<WT> RD;

  Substring_Count_in_Substring(Basic_Substring_Structure& BASS, vc<tuple<int, int, WT>> pattern) : BASS(BASS), pattern(pattern) { build(); }

  void build() {
    for (auto& [i, j, w]: pattern) {
      auto [a, b] = BASS.get_position(i, j);
      i = a, j = b;
    }
    int n = BASS.n_block();
    auto [H, W] = BASS.shape();
    R0.resize(H), R1.resize(H);
    for (auto& [a, b, w]: pattern) { R1[a] += w; }
    FOR(i, H) {
      int k = BASS.right[i];
      if (k != -1) R0[i] = R1[k];
      R1[i] += R0[i];
    }
    R0c = cumsum<WT>(R0);

    RD.resize(W);

    for (auto& [a, b, w]: pattern) RD[b] += w;
    FOR(k, n) {
      FOR_R(y, BASS.Y[k], BASS.Y[k + 1] - 1) { RD[y] += RD[y + 1]; }
    }

    FOR(y, W) {
      int k = BASS.Y_to_block[y];
      int a = BASS.X[k];
      int b = a + BASS.height[y];
      RD[y] += R0c[b] - R0c[a];
      if (BASS.down[y] != -1) RD[y] += RD[BASS.down[y]];
    }
    if (ONLINE) {
      // block 内の矩形クエリ用のデータ構造を構築
    }
  }

  vc<WT> sum_query(vc<pair<int, int>> query) {
    static_assert(!ONLINE);
    int Q = len(query);
    for (auto& [i, j]: query) {
      auto [a, b] = BASS.get_position(i, j);
      i = a, j = b;
    }
    vc<WT> ANS(Q);
    auto [H, W] = BASS.shape();
    vvc<int> PID(H), QID(H);
    FOR(i, len(pattern)) { PID[get<0>(pattern[i])].eb(i); }
    FOR(i, Q) { QID[query[i].fi].eb(i); }

    FenwickTree<Monoid_Add<WT>> bit(W);
    FOR_R(i, H) {
      for (int p: PID[i]) {
        auto [a, b, w] = pattern[p];
        bit.add(b, w);
      }
      int r = BASS.Y[BASS.X_to_block[i]] + BASS.width[i];
      for (int q: QID[i]) {
        auto [a, b] = query[q];
        ANS[q] += bit.sum(b, r);
        int k = BASS.X_to_block[a];
        int d = BASS.X[k] + BASS.height[b];
        ANS[q] += R0c[d] - R0c[a];
        int c = BASS.down[b];
        if (c != -1) ANS[q] += RD[c];
      }
    }
    return ANS;
  }

  WT sum_query(int i, int j) { assert(0); }
};
#line 1 "string/substring_count_in_substring.hpp"

#line 2 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 3 "ds/fenwicktree/fenwicktree.hpp"

template <typename Monoid>
struct FenwickTree {
  using G = Monoid;
  using MX = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;
  E total;

  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }

  E prod_all() { return total; }
  E sum_all() { return total; }
  E sum(int k) { return prefix_sum(k); }
  E prod(int k) { return prefix_prod(k); }
  E prefix_sum(int k) { return prefix_prod(k); }
  E prefix_prod(int k) {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) { return prod(L, R); }
  E prod(int L, int R) {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
    while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
    return G::op(pos, G::inverse(neg));
  }

  vc<E> get_all() {
    vc<E> res(n);
    FOR(i, n) res[i] = prod(i, i + 1);
    return res;
  }

  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }
  void set(int k, E x) { add(k, G::op(G::inverse(prod(k, k + 1)), x)); }

  template <class F>
  int max_right(const F check, int L = 0) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  // check(i, x)
  template <class F>
  int max_right_with_index(const F check, int L = 0) {
    assert(check(L, G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(i + (1 << k), t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(i + (1 << k), t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = R;
    // false になるところまで戻る
    int k = 0;
    while (i > 0 && check(s)) {
      s = G::op(s, dat[i - 1]);
      k = lowbit(i);
      i -= i & -i;
    }
    if (check(s)) {
      assert(i == 0);
      return 0;
    }
    // 2^k 進むと ok になる
    // false を維持して進む
    while (k) {
      --k;
      E t = G::op(s, G::inverse(dat[i + (1 << k) - 1]));
      if (!check(t)) { i += (1 << k), s = t; }
    }
    return i + 1;
  }

  int kth(E k, int L = 0) {
    return max_right([&k](E x) -> bool { return x <= k; }, L);
  }
};
#line 2 "string/basic_substring_structure.hpp"

#line 2 "ds/hashmap.hpp"

// u64 -> Val

template <typename Val>
struct HashMap {
  // n は入れたいものの個数で ok

  HashMap(u32 n = 0) { build(n); }
  void build(u32 n) {
    u32 k = 8;
    while (k < n * 2) k *= 2;
    cap = k / 2, mask = k - 1;
    key.resize(k), val.resize(k), used.assign(k, 0);
  }

  // size を保ったまま. size=0 にするときは build すること.

  void clear() {
    used.assign(len(used), 0);
    cap = (mask + 1) / 2;
  }
  int size() { return len(used) / 2 - cap; }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; i = (i + 1) & mask) {}
    return i;
  }

  Val& operator[](const u64& k) {
    if (cap == 0) extend();
    int i = index(k);
    if (!used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    return (used[i] ? val[i] : default_value);
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    FOR(i, len(used)) if (used[i]) f(key[i], val[i]);
  }

private:
  u32 cap, mask;
  vc<u64> key;
  vc<Val> val;
  vc<bool> used;

  u64 hash(u64 x) {
    static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return (x ^ (x >> 31)) & mask;
  }

  void extend() {
    vc<pair<u64, Val>> dat;
    dat.reserve(len(used) / 2 - cap);
    FOR(i, len(used)) {
      if (used[i]) dat.eb(key[i], val[i]);
    }
    build(2 * len(dat));
    for (auto& [a, b]: dat) (*this)[a] = b;
  }
};
#line 2 "string/suffix_array.hpp"

#line 2 "alg/monoid/min.hpp"

template <typename E>
struct Monoid_Min {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return min(x, y); }
  static constexpr X unit() { return infty<E>; }
  static constexpr bool commute = true;
};
#line 2 "ds/sparse_table/sparse_table.hpp"

// 冪等なモノイドであることを仮定。disjoint sparse table より x 倍高速
template <class Monoid>
struct Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

  Sparse_Table() {}
  Sparse_Table(int n) { build(n); }
  template <typename F>
  Sparse_Table(int n, F f) {
    build(n, f);
  }
  Sparse_Table(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].resize(n);
    FOR(i, n) dat[0][i] = f(i);

    FOR(i, log - 1) {
      dat[i + 1].resize(len(dat[i]) - (1 << i));
      FOR(j, len(dat[i]) - (1 << i)) {
        dat[i + 1][j] = MX::op(dat[i][j], dat[i][j + (1 << i)]);
      }
    }
  }

  X prod(int L, int R) {
    if (L == R) return MX::unit();
    if (R == L + 1) return dat[0][L];
    int k = topbit(R - L - 1);
    return MX::op(dat[k][L], dat[k][R - (1 << k)]);
  }

  template <class F>
  int max_right(const F check, int L) {
    assert(0 <= L && L <= n && check(MX::unit()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(0 <= R && R <= n && check(MX::unit()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};
#line 2 "ds/segtree/segtree.hpp"

template <class Monoid>
struct SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  using value_type = X;
  vc<X> dat;
  int n, log, size;

  SegTree() {}
  SegTree(int n) { build(n); }
  template <typename F>
  SegTree(int n, F f) {
    build(n, f);
  }
  SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::unit());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  X get(int i) { return dat[size + i]; }
  vc<X> get_all() { return {dat.begin() + size, dat.begin() + size + n}; }

  void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
  void set(int i, const X& x) {
    assert(i < n);
    dat[i += size] = x;
    while (i >>= 1) update(i);
  }

  void multiply(int i, const X& x) {
    assert(i < n);
    i += size;
    dat[i] = Monoid::op(dat[i], x);
    while (i >>= 1) update(i);
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    X vl = Monoid::unit(), vr = Monoid::unit();
    L += size, R += size;
    while (L < R) {
      if (L & 1) vl = Monoid::op(vl, dat[L++]);
      if (R & 1) vr = Monoid::op(dat[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

  X prod_all() { return dat[1]; }

  template <class F>
  int max_right(F check, int L) {
    assert(0 <= L && L <= n && check(Monoid::unit()));
    if (L == n) return n;
    L += size;
    X sm = Monoid::unit();
    do {
      while (L % 2 == 0) L >>= 1;
      if (!check(Monoid::op(sm, dat[L]))) {
        while (L < size) {
          L = 2 * L;
          if (check(Monoid::op(sm, dat[L]))) { sm = Monoid::op(sm, dat[L++]); }
        }
        return L - size;
      }
      sm = Monoid::op(sm, dat[L++]);
    } while ((L & -L) != L);
    return n;
  }

  template <class F>
  int min_left(F check, int R) {
    assert(0 <= R && R <= n && check(Monoid::unit()));
    if (R == 0) return 0;
    R += size;
    X sm = Monoid::unit();
    do {
      --R;
      while (R > 1 && (R % 2)) R >>= 1;
      if (!check(Monoid::op(dat[R], sm))) {
        while (R < size) {
          R = 2 * R + 1;
          if (check(Monoid::op(dat[R], sm))) { sm = Monoid::op(dat[R--], sm); }
        }
        return R + 1 - size;
      }
      sm = Monoid::op(dat[R], sm);
    } while ((R & -R) != R);
    return 0;
  }

  // prod_{l<=i<r} A[i xor x]
  X xor_prod(int l, int r, int xor_val) {
    static_assert(Monoid::commute);
    X x = Monoid::unit();
    for (int k = 0; k < log + 1; ++k) {
      if (l >= r) break;
      if (l & 1) { x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]); }
      if (r & 1) { x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]); }
      l /= 2, r /= 2, xor_val /= 2;
    }
    return x;
  }
};
#line 6 "string/suffix_array.hpp"

// 辞書順 i 番目の suffix が j 文字目始まりであるとき、
// SA[i] = j, ISA[j] = i
// |S|>0 を前提（そうでない場合 dummy 文字を追加して利用せよ）
template <bool USE_SPARSE_TABLE = true>
struct Suffix_Array {
  vc<int> SA;
  vc<int> ISA;
  vc<int> LCP;
  using Mono = Monoid_Min<int>;
  using SegType = conditional_t<USE_SPARSE_TABLE, Sparse_Table<Mono>, SegTree<Mono> >;
  SegType seg;
  bool build_seg;

  Suffix_Array() {}
  Suffix_Array(string& s) {
    build_seg = 0;
    assert(len(s) > 0);
    char first = 127, last = 0;
    for (auto&& c: s) {
      chmin(first, c);
      chmax(last, c);
    }
    SA = calc_suffix_array(s, first, last);
    calc_LCP(s);
  }

  Suffix_Array(vc<int> s) {
    build_seg = 0;
    assert(len(s) > 0);
    SA = calc_suffix_array(s);
    calc_LCP(s);
  }

  // lcp(S[i:], S[j:])
  int lcp(int i, int j) {
    if (!build_seg) {
      build_seg = true;
      seg.build(LCP);
    }
    int n = len(SA);
    if (i == n || j == n) return 0;
    if (i == j) return n - i;
    i = ISA[i], j = ISA[j];
    if (i > j) swap(i, j);
    return seg.prod(i, j);
  }

  // S[i:] との lcp が n 以上であるような半開区間
  pair<int, int> lcp_range(int i, int n) {
    if (!build_seg) {
      build_seg = true;
      seg.build(LCP);
    }
    i = ISA[i];
    int a = seg.min_left([&](auto e) -> bool { return e >= n; }, i);
    int b = seg.max_right([&](auto e) -> bool { return e >= n; }, i);
    return {a, b + 1};
  }

  // -1: S[L1:R1) < S[L2, R2)
  //  0: S[L1:R1) = S[L2, R2)
  // +1: S[L1:R1) > S[L2, R2)
  int compare(int L1, int R1, int L2, int R2) {
    int n1 = R1 - L1, n2 = R2 - L2;
    int n = lcp(L1, L2);
    if (n == n1 && n == n2) return 0;
    if (n == n1) return -1;
    if (n == n2) return 1;
    return (ISA[L1 + n] > ISA[L2 + n] ? 1 : -1);
  }

private:
  void induced_sort(const vc<int>& vect, int val_range, vc<int>& SA, const vc<bool>& sl, const vc<int>& lms_idx) {
    vc<int> l(val_range, 0), r(val_range, 0);
    for (int c: vect) {
      if (c + 1 < val_range) ++l[c + 1];
      ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());
    fill(SA.begin(), SA.end(), -1);
    for (int i = (int)lms_idx.size() - 1; i >= 0; --i) SA[--r[vect[lms_idx[i]]]] = lms_idx[i];
    for (int i: SA)
      if (i >= 1 && sl[i - 1]) SA[l[vect[i - 1]]++] = i - 1;
    fill(r.begin(), r.end(), 0);
    for (int c: vect) ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
      if (i >= 1 && !sl[i - 1]) { SA[--r[vect[i - 1]]] = i - 1; }
  }

  vc<int> SA_IS(const vc<int>& vect, int val_range) {
    const int n = vect.size();
    vc<int> SA(n), lms_idx;
    vc<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
      sl[i] = (vect[i] > vect[i + 1] || (vect[i] == vect[i + 1] && sl[i + 1]));
      if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vect, val_range, SA, sl, lms_idx);
    vc<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
      if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) { new_lms_idx[k++] = SA[i]; }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
      int i = new_lms_idx[k - 1], j = new_lms_idx[k];
      if (vect[i] != vect[j]) {
        SA[j] = ++cur;
        continue;
      }
      bool flag = false;
      for (int a = i + 1, b = j + 1;; ++a, ++b) {
        if (vect[a] != vect[b]) {
          flag = true;
          break;
        }
        if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
          flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
          break;
        }
      }
      SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
      auto lms_SA = SA_IS(lms_vec, cur + 1);
      for (size_t i = 0; i < lms_idx.size(); ++i) { new_lms_idx[i] = lms_idx[lms_SA[i]]; }
    }
    induced_sort(vect, val_range, SA, sl, new_lms_idx);
    return SA;
  }

  vc<int> calc_suffix_array(const string& s, const char first = 'a', const char last = 'z') {
    vc<int> vect(s.size() + 1);
    copy(begin(s), end(s), begin(vect));
    for (auto& x: vect) x -= (int)first - 1;
    vect.back() = 0;
    auto ret = SA_IS(vect, (int)last - (int)first + 2);
    ret.erase(ret.begin());
    return ret;
  }

  vc<int> calc_suffix_array(const vc<int>& s) {
    vc<int> ss = s;
    UNIQUE(ss);

    vc<int> vect(s.size() + 1);
    copy(all(s), vect.begin());
    for (auto& x: vect) x = LB(ss, x) + 1;
    vect.back() = 0;
    auto ret = SA_IS(vect, MAX(vect) + 2);
    ret.erase(ret.begin());
    return ret;
  }

  template <typename STRING>
  void calc_LCP(const STRING& s) {
    int n = s.size(), k = 0;
    ISA.resize(n);
    LCP.resize(n);
    for (int i = 0; i < n; i++) ISA[SA[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
      if (ISA[i] == n - 1) {
        k = 0;
        continue;
      }
      int j = SA[ISA[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
      LCP[ISA[i]] = k;
    }
    LCP.resize(n - 1);
  }
};
#line 2 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 2 "mod/modint61.hpp"

struct modint61 {
  static constexpr u64 mod = (1ULL << 61) - 1;
  u64 val;
  constexpr modint61() : val(0ULL) {}
  constexpr modint61(u32 x) : val(x) {}
  constexpr modint61(u64 x) : val(x % mod) {}
  constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {}
  constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {}
  static constexpr u64 get_mod() { return mod; }

  modint61 &operator+=(const modint61 &a) {
    val = ((val += a.val) >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 &operator-=(const modint61 &a) {
    val = ((val -= a.val) >= mod) ? (val + mod) : val;
    return *this;
  }
  modint61 &operator*=(const modint61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val;
    val = (y >> 61) + (y & mod);
    val = (val >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 operator-() const { return modint61(val ? mod - val : u64(0)); }
  modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); }
  modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
  modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
  modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
  modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
  bool operator<(const modint61 &other) const { return val < other.val; }
  bool operator==(const modint61 &p) const { return val == p.val; }
  bool operator!=(const modint61 &p) const { return val != p.val; }
  modint61 inverse() const {
    ll a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint61(u);
  }
  modint61 pow(ll n) const {
    assert(n >= 0);
    modint61 ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul, n >>= 1;
    }
    return ret;
  }
};

#ifdef FASTIO
void rd(modint61 &x) {
  fastio::rd(x.val);
  assert(0 <= x.val && x.val < modint61::mod);
}

void wt(modint61 x) { fastio::wt(x.val); }
#endif
#line 4 "string/rollinghash.hpp"

struct RollingHash {
  using mint = modint61;
  static constexpr u64 mod = mint::get_mod();
  const mint base;
  vc<mint> power;

  static inline mint generate_base() { return RNG(mod); }

  inline void expand(size_t sz) {
    if (power.size() < sz + 1) {
      int pre_sz = (int)power.size();
      power.resize(sz + 1);
      FOR(i, pre_sz - 1, sz) power[i + 1] = power[i] * base;
    }
  }

  explicit RollingHash(mint base = generate_base()) : base(base), power{1} {}

  template <typename STRING>
  vector<mint> build(const STRING& s) const {
    int sz = s.size();
    vector<mint> hashed(sz + 1, mint(0));
    for (int i = 0; i < sz; i++) { hashed[i + 1] = hashed[i] * base + s[i]; }
    return hashed;
  }

  template <typename STRING>
  mint eval(STRING& s) {
    mint x = 0;
    for (auto& ch: s) x = base * x + ch;
    return x;
  }

  mint query(const vc<mint>& s, int l, int r) {
    assert(0 <= l && l <= r && r < len(s));
    expand(r - l);
    return (s[r] - s[l] * power[r - l]);
  }

  mint combine(mint h1, mint h2, int h2len) {
    expand(h2len);
    return h1 * power[h2len] + h2;
  }

  mint add_char(mint h, int x) { return h * base + mint(x); }

  int lcp(const vc<mint>& a, int l1, int r1, const vc<mint>& b, int l2,
          int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = 0, high = len + 1;
    while (high - low > 1) {
      int mid = (low + high) / 2;
      if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
        low = mid;
      else
        high = mid;
    }
    return low;
  }
};
#line 2 "seq/cartesian_tree.hpp"
/*
辞書順で高さを unique して、木にしている。
極大長方形アルゴリズムで線形時間構築。
*/
template <typename T, bool IS_MIN>
struct CartesianTree {
  int n;
  vc<T>& A;
  vc<pair<int, int>> range;
  vc<int> lch, rch, par;
  int root;

  CartesianTree(vc<T>& A) : n(len(A)), A(A) {
    range.assign(n, {-1, -1});
    lch.assign(n, -1);
    rch.assign(n, -1);
    par.assign(n, -1);
    if (n == 1) {
      range[0] = {0, 1};
      root = 0;
      return;
    }
    auto is_sm = [&](int i, int j) -> bool {
      if (IS_MIN) return (A[i] < A[j]) || (A[i] == A[j] && i < j);
      return (A[i] > A[j]) || (A[i] == A[j] && i < j);
    };
    vc<int> st;
    FOR(i, n) {
      while (!st.empty() && is_sm(i, st.back())) {
        lch[i] = st.back();
        st.pop_back();
      }
      range[i].fi = (st.empty() ? 0 : st.back() + 1);
      st.eb(i);
    }
    st.clear();
    FOR_R(i, n) {
      while (!st.empty() && is_sm(i, st.back())) {
        rch[i] = st.back();
        st.pop_back();
      }
      range[i].se = (st.empty() ? n : st.back());
      st.eb(i);
    }
    FOR(i, n) if (lch[i] != -1) par[lch[i]] = i;
    FOR(i, n) if (rch[i] != -1) par[rch[i]] = i;
    FOR(i, n) if (par[i] == -1) root = i;
  }

  // (l, r, h)

  tuple<int, int, T> maximum_rectangle(int i) {
    auto [l, r] = range[i];
    return {l, r, A[i]};
  }

  // (l, r, h)

  T max_rectangle_area() {
    assert(IS_MIN);
    T res = 0;
    FOR(i, n) {
      auto [l, r, h] = maximum_rectangle(i);
      chmax(res, (r - l) * h);
    }
    return res;
  }

  ll count_subrectangle(bool baseline) {
    assert(IS_MIN);
    ll res = 0;
    FOR(i, n) {
      auto [l, r, h] = maximum_rectangle(i);
      ll x = (baseline ? h : h * (h + 1) / 2);
      res += x * (i - l + 1) * (r - i);
    }
    return res;
  }
};
#line 7 "string/basic_substring_structure.hpp"

// https://arxiv.org/pdf/2312.11873
struct Basic_Substring_Structure {
  using SA_t = Suffix_Array<false>;
  int N;
  string S, T; // T = rev(S)
  RollingHash RH;
  vc<decltype(RH)::mint> SH;
  SA_t S_SA, T_SA;
  HashMap<int> hash_to_col;

  /*
  block を diagonal に配置した長方形を作る感じにする.
  X, Y: i 番目の block が [X[i],X[i+1]) x [Y[i],Y[i+1]) になる.
  X_to_block, Y_to_block: 行番号や列番号に対応する block.
  width, height: 行の幅, 列の高さ. [X[i],X[i]+width[i]) など.
  right: 行き先の行
  down: 行き先の列
  */

  // topological 逆順 (最後に S[0,N) が来る)
  vc<pair<int, int>> raw_index; // 各 block の代表元に対応する [i,j]
  vc<int> X, Y;
  vc<int> X_to_block, Y_to_block;
  vc<int> width, height;
  vc<int> right, down;

  int n_block() { return len(raw_index); }
  pair<int, int> shape() { return {X.back(), Y.back()}; }

  Basic_Substring_Structure(string& S) { build(S); }

  void build(string& S_) {
    S = S_, T = {S_.rbegin(), S_.rend()};
    SH = RH.build(S);
    S_SA = SA_t(S), T_SA = SA_t(T);
    S_SA.seg.build(S_SA.LCP), S_SA.build_seg = true;
    T_SA.seg.build(T_SA.LCP), T_SA.build_seg = true;
    N = len(S);
    if (N == 1) {
      raw_index = {{0, 0}}, X = {0, 1}, Y = {0, 1}, X_to_block = {0}, Y_to_block = {0};
      width = {1}, height = {1}, right = {-1}, down = {-1};
      return;
    }
    X_to_block.reserve(2 * N - 1), Y_to_block.reserve(2 * N - 1);
    width.reserve(2 * N - 1), height.reserve(2 * N - 1);
    right.reserve(2 * N - 1), down.reserve(2 * N - 1);
    X = {0}, Y = {0};

    CartesianTree<int, true> CS(S_SA.LCP);
    CartesianTree<int, true> CT(T_SA.LCP);
    hash_to_col.build(N - 1);
    HashMap<int> hash_to_row(N - 1);

    auto is_node = [&](CartesianTree<int, true>& CT, int i) -> bool { return (CT.A[i] > 0 && (CT.par[i] == -1 || CT.A[CT.par[i]] != CT.A[i])); };

    // 列の先頭に相当するハッシュを集めておく
    HashMap<int> tmp(N - 1);
    FOR(i, N - 1) {
      if (!is_node(CS, i)) continue;
      int s = S_SA.SA[i], n = S_SA.LCP[i];
      tmp[RH.query(SH, s, s + n).val] = i;
    }

    // occur が小さい行から作っていく
    vc<int> ptr(N);
    FOR(i, N - 1) {
      if (is_node(CT, i)) ptr[CT.range[i].se - CT.range[i].fi]++;
    }
    ptr = cumsum<int>(ptr);
    vc<int> I(ptr.back(), -1);
    FOR(i, N - 1) {
      if (!is_node(CT, i)) continue;
      int occ = CT.range[i].se - CT.range[i].fi;
      I[ptr[occ]++] = i;
    }

    auto new_block = [&](int h, int w, int i, int j) -> int {
      int bid = len(raw_index);
      raw_index.eb(i, j);
      X.eb(X.back() + h), Y.eb(Y.back() + w);
      FOR(h) X_to_block.eb(bid), width.eb(-1), right.eb(-1);
      FOR(w) Y_to_block.eb(bid), height.eb(-1), down.eb(-1);
      return bid;
    };

    auto get_w = [&](int i) -> int { return CT.A[i] - (CT.par[i] == -1 ? 0 : CT.A[CT.par[i]]); };
    auto get_h = [&](int i) -> int { return CS.A[i] - (CS.par[i] == -1 ? 0 : CS.A[CS.par[i]]); };

    reverse(all(I));
    for (int a0: I) {
      int j = N - T_SA.SA[a0], n = T_SA.LCP[a0];
      u64 key = RH.query(SH, j - n, j).val;
      int b0 = tmp.get(key, -1);
      if (b0 == -1) continue;
      // occur>=2 に対応する block 発見
      int h = get_h(b0), w = get_w(a0);
      int bid = new_block(h, w, j - n, j);
      FOR(x, X[bid], X[bid + 1]) { hash_to_row[RH.query(SH, j - n, j - (x - X[bid])).val] = x; }
      FOR(y, Y[bid], Y[bid + 1]) { hash_to_col[RH.query(SH, j - n + (y - Y[bid]), j).val] = y; }
    }
    FOR(i, N - 1) {
      if (!is_node(CT, i)) continue;
      int r = N - T_SA.SA[i], n = T_SA.LCP[i];
      u64 key = RH.query(SH, r - n, r).val;
      int x = hash_to_row[key];
      width[x] = get_w(i);
      right[x] = hash_to_row.get(RH.query(SH, r - n + width[x], r).val, -1);
    }
    FOR(i, N - 1) {
      if (!is_node(CS, i)) continue;
      int l = S_SA.SA[i], n = S_SA.LCP[i];
      u64 key = RH.query(SH, l, l + n).val;
      int y = hash_to_col[key];
      height[y] = get_h(i);
      down[y] = hash_to_col.get(RH.query(SH, l, l + n - height[y]).val, -1);
    }

    // occur==1
    auto get_w2 = [&](int i) -> int { // [0,i)
      int k = T_SA.ISA[N - i];
      int n = i, m = 0;
      if (k > 0) chmax(m, T_SA.LCP[k - 1]);
      if (k < N - 1) chmax(m, T_SA.LCP[k]);
      return n - m;
    };
    auto get_h2 = [&](int i) -> int { // [i,N)
      int k = S_SA.ISA[i];
      int n = N - i, m = 0;
      if (k > 0) chmax(m, S_SA.LCP[k - 1]);
      if (k < N - 1) chmax(m, S_SA.LCP[k]);
      return n - m;
    };
    int h = get_h2(0), w = get_w2(N);
    int bid = new_block(h, w, 0, N);
    FOR(x, X[bid], X[bid + 1]) {
      int r = N - (x - X[bid]);
      width[x] = get_w2(r);
      right[x] = hash_to_row.get(RH.query(SH, width[x], r).val, -1);
    }
    FOR(y, Y[bid], Y[bid + 1]) {
      int l = y - Y[bid];
      height[y] = get_h2(l);
      down[y] = hash_to_col.get(RH.query(SH, l, N - height[y]).val, -1);
    }
  }

  // S[i,j) に対応する (x,y).
  pair<int, int> get_position(int i, int j) {
    // occur を保って長くする
    auto& seg = S_SA.seg;
    int n = j - i, k = S_SA.ISA[i];
    int m = N - i;
    auto check = [&](int e) -> bool {
      if (e >= n) chmin(m, e);
      return e >= n;
    };
    seg.min_left(check, k), seg.max_right(check, k);
    int y = hash_to_col.get(RH.query(SH, i, i + m).val, -1);
    if (y == -1) {
      assert(i + m == N);
      int x = X[n_block() - 1] + (N - j), y = Y[n_block() - 1] + i;
      return {x, y};
    }
    int bid = Y_to_block[y];
    auto [l, r] = raw_index[bid];
    int x = (X[bid] + Y[bid]) + ((r - l) - (j - i)) - y;
    return {x, y};
  }

  void debug() {
    auto [H, W] = shape();
    FOR(x, H) {
      string tmp(W, '.');
      int k = X_to_block[x];
      FOR(y, Y[k], Y[k] + width[x]) tmp[y] = '#';
      print(tmp);
    }
    SHOW(S);
    SHOW(raw_index);
    SHOW(width);
    SHOW(height);
    SHOW(right);
    SHOW(down);
    print();
  }
};
#line 4 "string/substring_count_in_substring.hpp"

// pattern S[i,j) を重み w で追加. S[i,j) に含まれる pattern の総和を求める.
// offline で実装している (online 化は易しい)
template <typename WT, bool ONLINE>
struct Substring_Count_in_Substring {
  Basic_Substring_Structure BASS;
  vc<tuple<int, int, WT>> pattern;

  // 各行に対して block を含めず右にあるものの個数
  // 各行に対して block を含めて右にあるものの個数
  vc<WT> R0, R1;
  vc<WT> R0c;
  // 各列の上端に対して, 右下にあるものの個数
  vc<WT> RD;

  Substring_Count_in_Substring(Basic_Substring_Structure& BASS, vc<tuple<int, int, WT>> pattern) : BASS(BASS), pattern(pattern) { build(); }

  void build() {
    for (auto& [i, j, w]: pattern) {
      auto [a, b] = BASS.get_position(i, j);
      i = a, j = b;
    }
    int n = BASS.n_block();
    auto [H, W] = BASS.shape();
    R0.resize(H), R1.resize(H);
    for (auto& [a, b, w]: pattern) { R1[a] += w; }
    FOR(i, H) {
      int k = BASS.right[i];
      if (k != -1) R0[i] = R1[k];
      R1[i] += R0[i];
    }
    R0c = cumsum<WT>(R0);

    RD.resize(W);

    for (auto& [a, b, w]: pattern) RD[b] += w;
    FOR(k, n) {
      FOR_R(y, BASS.Y[k], BASS.Y[k + 1] - 1) { RD[y] += RD[y + 1]; }
    }

    FOR(y, W) {
      int k = BASS.Y_to_block[y];
      int a = BASS.X[k];
      int b = a + BASS.height[y];
      RD[y] += R0c[b] - R0c[a];
      if (BASS.down[y] != -1) RD[y] += RD[BASS.down[y]];
    }
    if (ONLINE) {
      // block 内の矩形クエリ用のデータ構造を構築
    }
  }

  vc<WT> sum_query(vc<pair<int, int>> query) {
    static_assert(!ONLINE);
    int Q = len(query);
    for (auto& [i, j]: query) {
      auto [a, b] = BASS.get_position(i, j);
      i = a, j = b;
    }
    vc<WT> ANS(Q);
    auto [H, W] = BASS.shape();
    vvc<int> PID(H), QID(H);
    FOR(i, len(pattern)) { PID[get<0>(pattern[i])].eb(i); }
    FOR(i, Q) { QID[query[i].fi].eb(i); }

    FenwickTree<Monoid_Add<WT>> bit(W);
    FOR_R(i, H) {
      for (int p: PID[i]) {
        auto [a, b, w] = pattern[p];
        bit.add(b, w);
      }
      int r = BASS.Y[BASS.X_to_block[i]] + BASS.width[i];
      for (int q: QID[i]) {
        auto [a, b] = query[q];
        ANS[q] += bit.sum(b, r);
        int k = BASS.X_to_block[a];
        int d = BASS.X[k] + BASS.height[b];
        ANS[q] += R0c[d] - R0c[a];
        int c = BASS.down[b];
        if (c != -1) ANS[q] += RD[c];
      }
    }
    return ANS;
  }

  WT sum_query(int i, int j) { assert(0); }
};
Back to top page