#982583 (C++17) No.2761 Substitute and Search

• 問題: No.2761 Substitute and Search
• ユーザー: Today03
• 提出日時: 2024-05-18 00:30:34
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 3,236 ms / 4,000 ms
• コード長: 10,905 bytes
• コンパイル時間: 2,763 ms
• コンパイル使用メモリ: 227,096 KB
• 最終ジャッジ日時: 2025-02-21 15:35:35
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 13

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

template <typename T>
struct fenwick_tree {
    fenwick_tree() = default;
    fenwick_tree(int n) {
        this->n = n;
        dat = vector<T>(n);
    }
    void add(int i, T x) {
        i++;
        while (i <= n) {
            dat[i - 1] += x;
            i += i & -i;
        }
    }
    T operator[](int i) {
        return sum(i, i + 1);
    }
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
    int n;

private:
    vector<T> dat;
    T sum(int r) {
        T ret = 0;
        while (r > 0) {
            ret += dat[r - 1];
            r -= r & -r;
        }
        return ret;
    }
};

template <ll MOD>
struct modint {
    ll value;
    modint(ll x = 0) {
        if (x >= 0) {
            value = x % MOD;
        } else {
            value = MOD - (-x) % MOD;
        }
    }
    modint operator-() const {
        return modint(-value);
    }
    modint operator+() const {
        return modint(*this);
    }
    modint &operator+=(const modint &other) {
        value += other.value;
        if (value >= MOD) {
            value -= MOD;
        }
        return *this;
    }
    modint &operator-=(const modint &other) {
        value += MOD - other.value;
        if (value >= MOD) {
            value -= MOD;
        }
        return *this;
    }
    modint &operator*=(const modint other) {
        value = value * other.value % MOD;
        return *this;
    }
    modint &operator/=(modint other) {
        (*this) *= other.inv();
        return *this;
    }
    modint operator+(const modint &other) const {
        return modint(*this) += other;
    }
    modint operator-(const modint &other) const {
        return modint(*this) -= other;
    }
    modint operator*(const modint &other) const {
        return modint(*this) *= other;
    }
    modint operator/(const modint &other) const {
        return modint(*this) /= other;
    }
    modint pow(ll x) const {
        modint ret(1), mul(value);
        while (x) {
            if (x & 1) {
                ret *= mul;
            }
            mul *= mul;
            x >>= 1;
        }
        return ret;
    }
    modint inv() const {
        return pow(MOD - 2);
    }
    bool operator==(const modint &other) const {
        return value == other.value;
    }
    bool operator!=(const modint &other) const {
        return value != other.value;
    }
    friend ostream &operator<<(ostream &os, const modint &x) {
        return os << x.value;
    }
    friend istream &operator>>(istream &is, modint &x) {
        ll v;
        is >> v;
        x = modint<MOD>(v);
        return is;
    }
};
using mod998 = modint<998244353>;
using mod107 = modint<1000000007>;

namespace random_generator {
    mt19937_64 generate;
    void init() {
        random_device seed_gen;
        generate = mt19937_64(seed_gen());
    }
    template <typename T>
    T random_int(T x) {
        assert(x > 0);
        return generate() % x;
    }
    template <typename T>
    T random_int(T x, T y) {
        assert(x < y);
        return x + generate() % (y - x);
    }
    template <typename T>
    T get_elememt(vector<T> &a) {
        const int n = a.size();
        int idx = random_int(0, n);
        swap(a[n - 1], a[idx]);
        int ret = a.back();
        a.pop_back();
        return ret;
    }
    template <typename T>
    vector<T> random_array_int(int n, T lo, T hi, bool no_dup = false) {
        vector<T> ret(n);
        if (!no_dup) {
            for (int i = 0; i < n; i++) {
                ret[i] = random_int(lo, hi);
            }
        } else {
            set<T> st;
            for (int i = 0; i < n; i++) {
                int r = random_int(lo, hi);
                while (st.count(r)) {
                    r = random_int(lo, hi);
                }
                ret[i] = r;
                st.insert(r);
            }
        }
        return ret;
    }
    string random_alphabet(int n, bool lower = true) {
        string ret;
        for (int i = 0; i < n; i++) {
            int idx = random_int(26);
            ret.push_back(char((lower ? 'a' : 'A') + idx));
        }
        return ret;
    }
    string random_string(int n, string s) {
        string ret;
        int m = s.size();
        for (int i = 0; i < n; i++) {
            int idx = random_int(m);
            ret.push_back(s[idx]);
        }
        return ret;
    }
    template <typename T>
    vector<vector<T>> random_array_2D(int h, int w, T lo, T hi) {
        vector<vector<T>> ret(h, vector<T>(w));
        for (int i = 0; i < h; i++) {
            ret[i] = random_array_int(w, lo, hi);
        }
        return ret;
    }
    vector<string> random_alphabet_2D(int h, int w, bool lower = true) {
        vector<string> ret(h);
        for (int i = 0; i < h; i++) {
            ret[i] = random_alphabet(w, lower);
        }
        return ret;
    }
    vector<pair<int, int>> random_tree(int n) {
        vector<int> a = random_array_int<int>(n - 2, 1, n + 1);
        vector<int> d(n + 1);
        for (int i = 0; i < n - 2; i++) {
            d[a[i]]++;
        }
        for (int i = 1; i <= n; i++) {
            d[i]++;
        }
        vector<pair<int, int>> ret;
        set<int> pq;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                pq.insert(i);
            }
        }
        for (int i = 0; i < n - 2; i++) {
            int v = (*pq.begin());
            pq.erase(v);
            ret.push_back(make_pair(v, a[i]));
            d[v]--;
            d[a[i]]--;
            if (d[a[i]] == 1) {
                pq.insert(a[i]);
            } else if (d[a[i]] == 0) {
                pq.erase(a[i]);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                for (int j = i + 1; j <= n; j++) {
                    if (d[j] == 1) {
                        ret.push_back(make_pair(i, j));
                        break;
                    }
                }
                break;
            }
        }
        return ret;
    }
    vector<pair<int, int>> random_bintree(int n) {
        vector<pair<int, int>> ret;
        vector<ll> roots = {random_int(1, n + 1)};
        vector<ll> leaves;
        for (int i = 1; i <= n; i++) {
            if (i != roots.back()) {
                leaves.push_back(i);
            }
        }
        while (!leaves.empty()) {
            int root = get_elememt(roots);
            int leaf = get_elememt(leaves);
            ret.push_back(make_pair(root, leaf));
            roots.push_back(leaf);
            if (!leaves.empty()) {
                int leaf = get_elememt(leaves);
                ret.push_back(make_pair(root, leaf));
                roots.push_back(leaf);
            }
        }
        return ret;
    }
    vector<pair<int, int>> random_undigraph(int n, int m, bool connected = true) {
        vector<pair<int, int>> edges;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.push_back(make_pair(i + 1, j + 1));
            }
        }
        int ed = edges.size();
        if (!connected) {
            vector<pair<int, int>> ret;
            vector<int> idxs = random_array_int<int>(m, 0, ed, true);
            for (int idx : idxs) {
                ret.push_back(edges[idx]);
            }
            return ret;
        } else {
            vector<pair<int, int>> ret;
            while (true) {
                ret.clear();
                vector<int> idxs = random_array_int<int>(m, 0, ed, true);
                vector<int> parent(n);
                vector<vector<int>> sets(n);
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    sets[i].push_back(i);
                }
                for (int idx : idxs) {
                    ret.push_back(edges[idx]);
                    auto [a, b] = edges[idx];
                    a--;
                    b--;
                    if (parent[a] != parent[b]) {
                        if (sets[parent[a]].size() < sets[parent[b]].size()) {
                            swap(a, b);
                        }
                        for (int x : sets[parent[b]]) {
                            parent[x] = parent[a];
                            sets[parent[a]].push_back(x);
                        }
                        sets[parent[b]].clear();
                    }
                }
                bool ok = true;
                for (int i = 0; i < n; i++) {
                    if (parent[i] != parent[0]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    return ret;
                }
            }
        }
    }
};  // namespace random_generator

struct setup_random {
    setup_random() {
        random_generator::init();
    }
} setup_random_instance;

struct rolling_hash {
    int base;
    fenwick_tree<mod107> hash1;
    fenwick_tree<mod998> hash2;
    rolling_hash() = default;
    rolling_hash(const string &s, int base) {
        this->base = base;
        int n = s.size();
        hash1 = fenwick_tree<mod107>(n + 1);
        hash2 = fenwick_tree<mod998>(n + 1);
        for (int i = 0; i < n; i++) {
            hash1.add(i, mod107(s[i] - 'a' + 1) * mod107(base).pow(i));
            hash2.add(i, mod998(s[i] - 'a' + 1) * mod998(base).pow(i));
        }
    }
    void change(int i, char c1, char c2) {
        hash1.add(i, mod107(c2 - c1) * mod107(base).pow(i));
        hash2.add(i, mod998(c2 - c1) * mod998(base).pow(i));
    }
    pair<mod107, mod998> get(int len) {
        return {hash1.sum(0, len), hash2.sum(0, len)};
    }
};

int main() {
    int base = random_generator::random_int(1000, 10000);

    int N, L, Q;
    cin >> N >> L >> Q;
    vector<rolling_hash> rh(N);
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        rh[i] = rolling_hash(S[i], base);
    }

    while (Q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int k;
            char c, d;
            cin >> k >> c >> d;
            k--;

            for (int i = 0; i < N; i++) {
                if (S[i][k] == c) {
                    rh[i].change(k, c, d);
                    S[i][k] = d;
                }
            }
        }

        else {
            string T;
            cin >> T;
            rolling_hash rt(T, base);

            int ans = 0;
            for (int i = 0; i < N; i++) {
                int n = S[i].size();
                int m = T.size();
                if (n < m) continue;

                auto [h1, h2] = rt.get(m);
                auto [h3, h4] = rh[i].get(m);

                if (h1 == h3 && h2 == h4) ans++;
            }

            cout << ans << '\n';
        }
    }
}