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

• 問題: No.2020 Sum of Common Prefix Length
• ユーザー: kuhaku
• 提出日時: 2026-05-29 22:59:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 13,977 bytes
• コンパイル時間: 2,443 ms
• コンパイル使用メモリ: 201,568 KB
• 実行使用メモリ: 35,324 KB
• 最終ジャッジ日時: 2026-05-29 22:59:49
• 合計ジャッジ時間: 11,990 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
other	AC * 20 TLE * 1 -- * 17

ソースコード

// 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>
/// @brief オイラーツアー
struct euler_tour {
    template <class T>
    euler_tour(const Graph<T> &g, int r = 0) : euler_tour(g, g.size(), r) {}
    std::pair<int, int> operator[](int i) const { return std::make_pair(ls[i], rs[i]); }
    int size() const { return _size; }
    int left(int i) const { return ls[i]; }
    int right(int i) const { return rs[i]; }
    int order(int i) const { return ord[i]; }
    template <class F>
    void query(int v, const F &f) const {
        f(ls[v], rs[v]);
    }
  private:
    int _size;
    std::vector<int> ord, ls, rs;
    template <class T>
    euler_tour(const Graph<T> &g, int n, int r) : _size(n), ord(n), ls(n, -1), rs(n) {
        int c = 0;
        std::stack<int> st;
        st.emplace(r);
        while (!st.empty()) {
            auto x = st.top();
            st.pop();
            if (x < 0) {
                rs[~x] = c;
                continue;
            }
            ls[x] = c;
            ord[x] = c++;
            rs[x] = c;
            for (auto e : g[x]) {
                if (ls[e.to()] != -1) continue;
                st.emplace(~x);
                st.emplace(e.to());
            }
        }
    }
};
// オイラーツアー版（HLD 版 2020.test.cpp の別解）。
// answer(x) = Σ_{v ∈ path(x), v≠root} (v の部分木にある終端 pos_k の本数)
//           = Σ_k depth(LCA(pos_x, pos_k))
// 各文字列の終端 pos_k を行きがけ順 in[pos_k] に一点加算しておくと、
// ノード v の「部分木内アクティブ終端数」は BIT の区間和 [in[v], out[v]) で取れる。
// クエリ2 は root→pos_x のパスを親リンクで辿りこの区間和を足す（1 クエリ O(|S_x|·log)）。
// 末尾追加で終端が伸びたら、旧終端を一点減算し新終端を一点加算する。
int main() {
    int n;
    std::cin >> n;
    Trie<26, 'a'> trie;
    std::vector<int> pos(n);  ///< pos[i]: S_i の現在の終端ノード id
    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();
    }
    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 から親→子の木を作り、オイラーツアーを構築する（root = 0）。
    int m = trie.size();
    Graph<int> g(m);
    std::vector<int> par(m, -1);
    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_edge(v, u), par[u] = v;
        }
    }
    euler_tour et(g, 0);
    fenwick_tree<std::int64_t> bit(m);
    auto activate = [&](int v) {
        bit.add(et.left(v), 1);
    };
    auto deactivate = [&](int v) {
        bit.add(et.left(v), -1);
    };
    auto query = [&](int x) {  // root→pos_x のパス上（root 除く）の部分木和の総和
        std::int64_t res = 0;
        for (int v = x; v != 0; v = par[v]) {
            et.query(v, [&](int l, int r) {
                res += bit.sum(l, r);
            });
        }
        return res;
    };
    // 時系列を再生する。初期文字列の終端を activate し、現在終端を記録。
    std::vector<int> cur(n);
    for (int i = 0; i < n; ++i) {
        cur[i] = init_path[i].empty() ? 0 : init_path[i].back();
        activate(cur[i]);
    }
    for (int i = 0; i < q; ++i) {
        if (qtype[i] == 1) {
            // 終端が cur[x] から qadd[i] へ移動する。
            deactivate(cur[qx[i]]);
            cur[qx[i]] = qadd[i];
            activate(qadd[i]);
        } else {
            std::cout << query(cur[qx[i]]) << '\n';
        }
    }
    return 0;
}