#1167592 (C++23) No.2020 Sum of Common Prefix Length

• 問題: No.2020 Sum of Common Prefix Length
• ユーザー: kuhaku
• 提出日時: 2026-05-29 22:35:05
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 185 ms / 2,000 ms
• コード長: 19,892 bytes
• コンパイル時間: 1,670 ms
• コンパイル使用メモリ: 207,948 KB
• 実行使用メモリ: 72,408 KB
• 最終ジャッジ日時: 2026-05-29 22:35:13
• 合計ジャッジ時間: 7,034 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_1

ファイルパターン	結果
other	AC * 38

ソースコード

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2020
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
/// @brief フェニック木
/// @see http://hos.ac/slides/20140319_bit.pdf
template <class T>
struct fenwick_tree {
    fenwick_tree() : _size(), data() {}
    fenwick_tree(int n) : _size(n + 1), data(n + 1) {}
    template <class U>
    fenwick_tree(const std::vector<U> &v) : _size((int)v.size() + 1), data((int)v.size() + 1) {
        build(v);
    }
    T operator[](int i) const { return sum(i, i + 1); }
    T at(int k) const { return operator[](k); }
    T get(int k) const { return operator[](k); }
    template <class U>
    void build(const std::vector<U> &v) {
        for (int i = 0, n = v.size(); i < n; ++i) data[i + 1] = v[i];
        for (int i = 1; i < _size; ++i) {
            if (i + (i & -i) < _size) data[i + (i & -i)] += data[i];
        }
    }
    /// @brief v[k] = val
    void set(int k, T val) { add(k, val - at(k)); }
    /// @brief v[k] += val
    void add(int k, T val) {
        assert(0 <= k && k < _size - 1);
        for (++k; k < _size; k += k & -k) data[k] += val;
    }
    /// @brief chmax(v[k], val)
    bool chmax(int k, T val) {
        if (at(k) >= val) return false;
        set(k, val);
        return true;
    }
    /// @brief chmin(v[k], val)
    bool chmin(int k, T val) {
        if (at(k) <= val) return false;
        set(k, val);
        return true;
    }
    /// @brief v[0] + ... + v[n - 1]
    T all_prod() const { return prod(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    T prod(int k) const { return sum(k); }
    /// @brief v[a] + ... + v[b - 1]
    T prod(int a, int b) const { return sum(a, b); }
    /// @brief v[0] + ... + v[n - 1]
    T all_sum() const { return sum(_size - 1); }
    /// @brief v[0] + ... + v[k - 1]
    T sum(int k) const {
        assert(0 <= k && k < _size);
        T res = 0;
        for (; k > 0; k -= k & -k) res += data[k];
        return res;
    }
    /// @brief v[a] + ... + v[b - 1]
    T sum(int a, int b) const {
        assert(0 <= a && a <= b && b < _size);
        T res = T();
        while (a != b) {
            if (a < b) {
                res += data[b];
                b -= b & -b;
            } else {
                res -= data[a];
                a -= a & -a;
            }
        }
        return res;
    }
    int lower_bound(T val) const {
        if (val <= 0) return 0;
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && data[res + k] < val) val -= data[res += k];
        }
        return res;
    }
    int lower_bound(int k, T val) const { return lower_bound(val + sum(k)); }
    int upper_bound(T val) const {
        if (val <= 0) return 0;
        int k = 1;
        while (k < _size) k <<= 1;
        int res = 0;
        for (; k > 0; k >>= 1) {
            if (res + k < _size && !(val < data[res + k])) val -= data[res += k];
        }
        return res;
    }
    int upper_bound(int k, T val) const { return upper_bound(val + sum(k)); }
  private:
    int _size;
    std::vector<T> data;
};
/// @brief 重み付きグラフ
template <class T>
struct Graph {
  private:
    struct _edge {
        constexpr _edge() : _from(), _to(), _weight() {}
        constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {}
        constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); }
        constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
        constexpr int from() const { return _from; }
        constexpr int to() const { return _to; }
        constexpr T weight() const { return _weight; }
      private:
        int _from, _to;
        T _weight;
    };
  public:
    using edge_type = typename Graph<T>::_edge;
    Graph() : _size(), edges() {}
    Graph(int v) : _size(v), edges(v) {}
    const auto &operator[](int i) const { return edges[i]; }
    auto &operator[](int i) { return edges[i]; }
    const auto begin() const { return edges.begin(); }
    auto begin() { return edges.begin(); }
    const auto end() const { return edges.end(); }
    auto end() { return edges.end(); }
    constexpr int size() const { return _size; }
    void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); }
    void add_edge(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); }
    void add_edges(int from, int to, T weight = T(1)) {
        edges[from].emplace_back(from, to, weight);
        edges[to].emplace_back(to, from, weight);
    }
    void input_edge(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            T weight;
            std::cin >> from >> to >> weight;
            add_edge(from - base, to - base, weight);
        }
    }
    void input_edges(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            T weight;
            std::cin >> from >> to >> weight;
            add_edges(from - base, to - base, weight);
        }
    }
  private:
    int _size;
    std::vector<std::vector<edge_type>> edges;
};
/// @brief 重みなしグラフ
template <>
struct Graph<void> {
  private:
    struct _edge {
        constexpr _edge() : _from(), _to() {}
        constexpr _edge(int from, int to) : _from(from), _to(to) {}
        constexpr int from() const { return _from; }
        constexpr int to() const { return _to; }
        constexpr int weight() const { return 1; }
        constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); }
        constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
      private:
        int _from, _to;
    };
  public:
    using edge_type = typename Graph<void>::_edge;
    Graph() : _size(), edges() {}
    Graph(int v) : _size(v), edges(v) {}
    const auto &operator[](int i) const { return edges[i]; }
    auto &operator[](int i) { return edges[i]; }
    const auto begin() const { return edges.begin(); }
    auto begin() { return edges.begin(); }
    const auto end() const { return edges.end(); }
    auto end() { return edges.end(); }
    constexpr int size() const { return _size; }
    void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); }
    void add_edge(int from, int to) { edges[from].emplace_back(from, to); }
    void add_edges(int from, int to) {
        edges[from].emplace_back(from, to);
        edges[to].emplace_back(to, from);
    }
    void input_edge(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edge(from - base, to - base);
        }
    }
    void input_edges(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edges(from - base, to - base);
        }
    }
  private:
    int _size;
    std::vector<std::vector<edge_type>> edges;
};
/// @brief Trie
/// @see https://algo-logic.info/trie-tree/
/// @see https://atcoder.jp/contests/tenka1-2016-final-open/tasks/tenka1_2016_final_c
template <int char_size = 96, int base = ' '>
struct Trie {
  private:
    struct _node {
        std::vector<int> next_node;
        int count;  ///< このノードを通過した文字列の本数（= このノードに対応する接頭辞を持つ文字列数）
        _node() : next_node(char_size, -1), count(0) {}
    };
  public:
    using node_type = _node;
    Trie() : root(0), nodes() { nodes.emplace_back(); }
    int size() const { return nodes.size(); }
    /// @brief ノード node_id の子 c をたどる。無ければ新規作成。count は更新しない。
    /// @return 子ノードの id
    int add(int node_id, char ch) {
        assert(0 <= node_id && node_id < (int)nodes.size());
        int c = ch - base;
        assert(0 <= c && c < char_size);
        int &next_id = nodes[node_id].next_node[c];
        if (next_id == -1) {
            next_id = nodes.size();
            nodes.emplace_back();
        }
        return next_id;
    }
    /// @brief ノード node_id の通過カウントを増やす。
    void add_count(int node_id, int x = 1) {
        assert(0 <= node_id && node_id < (int)nodes.size());
        nodes[node_id].count += x;
    }
    /// @brief ノード node_id の通過カウント（接頭辞を持つ文字列数）。
    int count(int node_id) const {
        assert(0 <= node_id && node_id < (int)nodes.size());
        return nodes[node_id].count;
    }
    std::vector<int> insert(const std::string &word) {
        std::vector<int> res;
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = nodes[node_id].next_node[c];
            if (next_id == -1) {
                next_id = nodes.size();
                nodes.emplace_back();
            }
            node_id = next_id;
            ++nodes[node_id].count;
            res.emplace_back(node_id);
        }
        return res;
    }
    int search_id(const std::string &word) {
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = nodes[node_id].next_node[c];
            if (next_id == -1) return -1;
            node_id = next_id;
        }
        return node_id;
    }
    node_type get_node(int node_id) const {
        assert(0 <= node_id && node_id < (int)nodes.size());
        return nodes[node_id];
    }
  private:
    int root;
    std::vector<node_type> nodes;
};
#include <stack>
#include <utility>
namespace internal {
struct graph_csr {
  private:
    struct edge_list {
        using const_iterator = std::vector<int>::const_iterator;
        edge_list(const graph_csr &g, int v) : g(g), v(v) {}
        const_iterator begin() const { return std::next(g.elist.begin(), g.start[v]); }
        const_iterator end() const { return std::next(g.elist.begin(), g.start[v + 1]); }
      private:
        const graph_csr &g;
        int v;
    };
  public:
    graph_csr(int n) : _size(n), edges(), start(n + 1) {}
    edge_list operator[](int i) const { return edge_list(*this, i); }
    constexpr int size() const { return _size; }
    void build() {
        for (auto [u, v] : edges) ++start[u + 1];
        for (int i = 0; i < _size; ++i) start[i + 1] += start[i];
        auto counter = start;
        elist = std::vector<int>(edges.size());
        for (auto [u, v] : edges) elist[counter[u]++] = v;
    }
    void add_edge(int u, int v) { edges.emplace_back(u, v); }
    void add_edges(int u, int v) {
        edges.emplace_back(u, v);
        edges.emplace_back(v, u);
    }
    void input_edge(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edge(from - base, to - base);
        }
        build();
    }
    void input_edges(int m, int base = 1) {
        for (int i = 0; i < m; ++i) {
            int from, to;
            std::cin >> from >> to;
            add_edges(from - base, to - base);
        }
        build();
    }
    int _size;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> elist;
    std::vector<int> start;
};
template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>> &edges) : start(n + 1), elist(edges.size()) {
        for (auto e : edges) ++start[e.first + 1];
        for (int i = 1; i <= n; ++i) start[i] += start[i - 1];
        auto counter = start;
        for (auto e : edges) elist[counter[e.first]++] = e.second;
    }
};
}  // namespace internal
/**
 * @brief HL分解
 * @see https://beet-aizu.github.io/library/tree/heavylightdecomposition.cpp
 */
struct heavy_light_decomposition {
    heavy_light_decomposition() = default;
    template <class T>
    heavy_light_decomposition(const Graph<T> &g, int r = 0) : heavy_light_decomposition(g.size()) {
        std::vector<int> heavy_path(_size, -1), sub_size(_size, 1);
        std::stack<int> st;
        st.emplace(r);
        int pos = 0;
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            vid[pos++] = v;
            for (auto &e : g[v]) {
                int u = e.to();
                if (u == par[v]) continue;
                par[u] = v, dep[u] = dep[v] + 1, st.emplace(u);
            }
        }
        for (int i = _size - 1; i >= 0; --i) {
            int v = vid[i];
            int max_sub = 0;
            for (auto &e : g[v]) {
                int u = e.to();
                if (u == par[v]) continue;
                sub_size[v] += sub_size[u];
                if (max_sub < sub_size[u]) max_sub = sub_size[u], heavy_path[v] = u;
            }
        }
        nxt[r] = r;
        pos = 0;
        st.emplace(r);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            vid[v] = pos++;
            inv[vid[v]] = v;
            int hp = heavy_path[v];
            for (auto &e : g[v]) {
                int u = e.to();
                if (u == par[v] || u == hp) continue;
                nxt[u] = u, st.emplace(u);
            }
            if (hp != -1) nxt[hp] = nxt[v], st.emplace(hp);
        }
    }
    heavy_light_decomposition(const internal::graph_csr &g, int r = 0)
        : heavy_light_decomposition(g.size()) {
        std::vector<int> heavy_path(_size, -1), sub_size(_size, 1);
        std::stack<int> st;
        st.emplace(r);
        int pos = 0;
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            vid[pos++] = v;
            for (int u : g[v]) {
                if (u == par[v]) continue;
                par[u] = v, dep[u] = dep[v] + 1, st.emplace(u);
            }
        }
        for (int i = _size - 1; i >= 0; --i) {
            int v = vid[i];
            int max_sub = 0;
            for (int u : g[v]) {
                if (u == par[v]) continue;
                sub_size[v] += sub_size[u];
                if (max_sub < sub_size[u]) max_sub = sub_size[u], heavy_path[v] = u;
            }
        }
        nxt[r] = r;
        pos = 0;
        st.emplace(r);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            vid[v] = pos++;
            inv[vid[v]] = v;
            int hp = heavy_path[v];
            for (int u : g[v]) {
                if (u == par[v] || u == hp) continue;
                nxt[u] = u, st.emplace(u);
            }
            if (hp != -1) nxt[hp] = nxt[v], st.emplace(hp);
        }
    }
    constexpr int size() const { return _size; }
    int get(int v) const { return vid[v]; }
    int get_parent(int v) const { return par[v]; }
    int get_depth(int v) const { return dep[v]; }
    int dist(int u, int v) const {
        int d = 0;
        while (true) {
            if (vid[u] > vid[v]) std::swap(u, v);
            if (nxt[u] == nxt[v]) return d + vid[v] - vid[u];
            d += vid[v] - vid[nxt[v]] + 1;
            v = par[nxt[v]];
        }
    }
    int jump(int u, int v, int k) const {
        int d = dist(u, v);
        if (d < k) return -1;
        int l = lca(u, v);
        if (dist(u, l) >= k) return la(u, k);
        else return la(v, d - k);
    }
    int la(int v, int k) const {
        while (true) {
            int u = nxt[v];
            if (vid[v] - k >= vid[u]) return inv[vid[v] - k];
            k -= vid[v] - vid[u] + 1;
            v = par[u];
        }
    }
    int lca(int u, int v) const {
        while (true) {
            if (vid[u] > vid[v]) std::swap(u, v);
            if (nxt[u] == nxt[v]) return u;
            v = par[nxt[v]];
        }
    }
    template <class F>
    void for_each(int u, int v, const F &f) const {
        while (true) {
            if (vid[u] > vid[v]) std::swap(u, v);
            f(std::max(vid[nxt[v]], vid[u]), vid[v] + 1);
            if (nxt[u] != nxt[v]) v = par[nxt[v]];
            else break;
        }
    }
    template <class F>
    void for_each_edge(int u, int v, const F &f) const {
        while (true) {
            if (vid[u] > vid[v]) std::swap(u, v);
            if (nxt[u] != nxt[v]) {
                f(vid[nxt[v]], vid[v] + 1);
                v = par[nxt[v]];
            } else {
                if (u != v) f(vid[u] + 1, vid[v] + 1);
                break;
            }
        }
    }
  private:
    int _size;
    std::vector<int> vid, nxt, par, dep, inv;
    heavy_light_decomposition(int n) : _size(n), vid(n, -1), nxt(n), par(n, -1), dep(n), inv(n) {}
};
// S_x と全 S_k の最長共通接頭辞長の総和は、S_x がたどる Trie のパス上の
// 各ノードの「通過文字列数 cnt」の総和に等しい。
//   cnt(v) = v を接頭辞に持つ文字列の本数
// よって「木上の一点加算」と「root から pos_x までのパス上の頂点総和」に帰着する。
// 末尾追加・全ノードを確定させるため、クエリを先読みするオフライン処理を行う。
int main() {
    int n;
    std::cin >> n;
    Trie<26, 'a'> trie;
    std::vector<int> pos(n);  ///< pos[i]: S_i の現在の終端ノード id
    // insert が通過した全ノードを cnt 再生用に保持する。
    std::vector<std::vector<int>> init_path(n);
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        init_path[i] = trie.insert(s);
        pos[i] = init_path[i].empty() ? 0 : init_path[i].back();
    }
    // insert は cnt を増やしてしまうので、ここで一旦リセットして再生する。
    // （Trie の cnt は使わず BIT で管理するため、増えた分は影響しない）
    int q;
    std::cin >> q;
    std::vector<int> qtype(q), qx(q), qadd(q, -1);  ///< qadd: type1 で増えたノード id
    // 先にクエリを適用しきって最終 Trie（全ノード）を確定させる。
    for (int i = 0; i < q; ++i) {
        std::cin >> qtype[i] >> qx[i];
        --qx[i];
        if (qtype[i] == 1) {
            char c;
            std::cin >> c;
            int nid = trie.add(pos[qx[i]], c);
            qadd[i] = nid;
            pos[qx[i]] = nid;
        }
    }
    // 確定した Trie から親→子の木を作って HLD を構築する（root = 0）。
    int m = trie.size();
    Graph<int> g(m);
    for (int v = 0; v < m; ++v) {
        const auto node = trie.get_node(v);
        for (int c = 0; c < 26; ++c) {
            int u = node.next_node[c];
            if (u != -1)
                g.add_edges(v, u);
        }
    }
    heavy_light_decomposition hld(g, 0);
    fenwick_tree<std::int64_t> bit(m);
    auto point_add = [&](int v, int x) {
        bit.add(hld.get(v), x);
    };
    auto path_sum = [&](int v) {  // root(0) から v までのパス上の cnt 総和
        std::int64_t res = 0;
        hld.for_each(0, v, [&](int l, int r) {
            res += bit.sum(l, r);
        });
        // root 自身（深さ0, 空接頭辞）は LCP に寄与しないので差し引く。
        res -= bit[hld.get(0)];
        return res;
    };
    // 時系列を再生する。まず初期文字列の通過ノードへ +1 し、現在終端を記録。
    std::vector<int> cur(n);  ///< cur[i]: 再生中の S_i の終端ノード id
    for (int i = 0; i < n; ++i) {
        for (int v : init_path[i]) point_add(v, 1);
        cur[i] = init_path[i].empty() ? 0 : init_path[i].back();
    }
    for (int i = 0; i < q; ++i) {
        if (qtype[i] == 1) {
            // 伸びた先のノードを S_qx[i] が新たに通過する。
            point_add(qadd[i], 1);
            cur[qx[i]] = qadd[i];
        } else {
            std::cout << path_sum(cur[qx[i]]) << '\n';
        }
    }
    return 0;
}