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

提出ソース
結果

問題	No.2761 Substitute and Search
ユーザー	torisasami4
提出日時	2024-05-17 21:57:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	11,980 bytes
コンパイル時間	2,216 ms
コンパイル使用メモリ	217,448 KB
実行使用メモリ	145,692 KB
最終ジャッジ日時	2024-05-17 21:57:40
合計ジャッジ時間	8,392 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,752 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("O2,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define per(i, n) for (int i = (n)-1; 0 <= i; i--)
#define rep2(i, l, r) for (int i = (l); i < int(r); i++)
#define per2(i, l, r) for (int i = (r)-1; int(l) <= i; i--)
#define each(e, v) for (auto &e : v)
#define MM << " " <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
template <typename T>
void print(const vector<T> &v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
    if (v.empty()) cout << '\n';
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}
template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}
template <class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T>
using maxheap = std::priority_queue<T>;
template <typename T>
int lb(const vector<T> &v, T x) {
    return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, T x) {
    return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
void rearrange(vector<T> &v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

// __int128_t gcd(__int128_t a, __int128_t b) {
//     if (a == 0)
//         return b;
//     if (b == 0)
//         return a;
//     __int128_t cnt = a % b;
//     while (cnt != 0) {
//         a = b;
//         b = cnt;
//         cnt = a % b;
//     }
//     return b;
// }

struct Union_Find_Tree {
    vector<int> data;
    const int n;
    int cnt;

    Union_Find_Tree(int n) : data(n, -1), n(n), cnt(n) {}

    int root(int x) {
        if (data[x] < 0) return x;
        return data[x] = root(data[x]);
    }

    int operator[](int i) { return root(i); }

    bool unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        // if (data[x] > data[y]) swap(x, y);
        data[x] += data[y], data[y] = x;
        cnt--;
        return true;
    }

    int size(int x) { return -data[root(x)]; }

    int count() { return cnt; };

    bool same(int x, int y) { return root(x) == root(y); }

    void clear() {
        cnt = n;
        fill(begin(data), end(data), -1);
    }
};

template <int mod>
struct Mod_Int {
    int x;

    Mod_Int() : x(0) {}

    Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    static int get_mod() { return mod; }

    Mod_Int &operator+=(const Mod_Int &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator-=(const Mod_Int &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator*=(const Mod_Int &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    Mod_Int &operator/=(const Mod_Int &p) {
        *this *= p.inverse();
        return *this;
    }

    Mod_Int &operator++() { return *this += Mod_Int(1); }

    Mod_Int operator++(int) {
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int &operator--() { return *this -= Mod_Int(1); }

    Mod_Int operator--(int) {
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator-() const { return Mod_Int(-x); }

    Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }

    Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }

    Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }

    Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }

    bool operator==(const Mod_Int &p) const { return x == p.x; }

    bool operator!=(const Mod_Int &p) const { return x != p.x; }

    Mod_Int inverse() const {
        assert(*this != Mod_Int(0));
        return pow(mod - 2);
    }

    Mod_Int pow(long long k) const {
        Mod_Int now = *this, ret = 1;
        for (; k > 0; k >>= 1, now *= now) {
            if (k & 1) ret *= now;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Mod_Int &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, Mod_Int &p) {
        long long a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

ll mpow(ll x, ll n, ll mod) {
    ll ans = 1;
    x %= mod;
    while (n != 0) {
        if (n & 1) ans = ans * x % mod;
        x = x * x % mod;
        n = n >> 1;
    }
    ans %= mod;
    return ans;
}

template <typename T>
T modinv(T a, const T &m) {
    T b = m, u = 1, v = 0;
    while (b > 0) {
        T t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
    }
    return u >= 0 ? u % m : (m - (-u) % m) % m;
}

ll divide_int(ll a, ll b) {
    if (b < 0) a = -a, b = -b;
    return (a >= 0 ? a / b : (a - b + 1) / b);
}

// const int MOD = 1000000007;
const int MOD = 998244353;
using mint = Mod_Int<MOD>;

// ----- library -------
template <typename Monoid>
struct Segment_Tree {
    using M = typename Monoid::V;
    int n, m;
    vector<M> seg;

    // f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = a

    Segment_Tree(const vector<M> &v) : n(v.size()) {
        m = 1;
        while (m < n) m <<= 1;
        seg.assign(2 * m, Monoid::id);
        copy(begin(v), end(v), begin(seg) + m);
        build();
    }

    Segment_Tree(int n, M x = Monoid::id) : Segment_Tree(vector<M>(n, x)) {}

    void set(int i, const M &x) { seg[m + i] = x; }

    void build() {
        for (int i = m - 1; i > 0; i--) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);
    }

    void update(int i, const M &x, bool apply = false) {
        seg[i + m] = apply ? Monoid::merge(seg[i + m], x) : x;
        i += m;
        while (i >>= 1) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);
    }

    M query(int l, int r) const {
        l = max(l, 0), r = min(r, n);
        M L = Monoid::id, R = Monoid::id;
        l += m, r += m;
        while (l < r) {
            if (l & 1) L = Monoid::merge(L, seg[l++]);
            if (r & 1) R = Monoid::merge(seg[--r], R);
            l >>= 1, r >>= 1;
        }
        return Monoid::merge(L, R);
    }

    M operator[](int i) const { return seg[m + i]; }

    template <typename C>
    int find_subtree(int i, const C &check, M &x, int type) const {
        while (i < m) {
            M nxt = type ? Monoid::merge(seg[2 * i + type], x) : Monoid::merge(x, seg[2 * i + type]);
            if (check(nxt)) {
                i = 2 * i + type;
            } else {
                x = nxt;
                i = 2 * i + (type ^ 1);
            }
        }
        return i - m;
    }

    // check(区間 [l,r] での演算結果) を満たす最小の r (存在しなければ n)
    template <typename C>
    int find_first(int l, const C &check) const {
        M L = Monoid::id;
        int a = l + m, b = 2 * m;
        while (a < b) {
            if (a & 1) {
                M nxt = Monoid::merge(L, seg[a]);
                if (check(nxt)) return find_subtree(a, check, L, 0);
                L = nxt;
                a++;
            }
            a >>= 1, b >>= 1;
        }
        return n;
    }

    // check((区間 [l,r) での演算結果)) を満たす最大の l (存在しなければ -1)
    template <typename C>
    int find_last(int r, const C &check) const {
        M R = Monoid::id;
        int a = m, b = r + m;
        while (a < b) {
            if ((b & 1) || a == 1) {
                M nxt = Monoid::merge(seg[--b], R);
                if (check(nxt)) return find_subtree(b, check, R, 1);
                R = nxt;
            }
            a >>= 1, b >>= 1;
        }
        return -1;
    }
};

struct Random_Number_Generator {
    mt19937_64 mt;

    Random_Number_Generator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}

    // 区間 [l,r) の整数で乱数発生
    int64_t operator()(int64_t l, int64_t r) {
        uniform_int_distribution<int64_t> dist(l, r - 1);
        return dist(mt);
    }

    // 区間 [0,r) の整数で乱数発生
    int64_t operator()(int64_t r) { return (*this)(0, r); }
} rng;

using ull = unsigned long long;
const ull mod = (1ULL << 61) - 1;

ull hash_mod(ull x) {
    ull ret = (x >> 61) + (x & mod);
    return ret - (ret >= mod ? mod : 0);
}

ull hash_mul(ull x, ull y) {
    x = hash_mod(x), y = hash_mod(y);
    ull x1 = x >> 31, x2 = x & ((1ULL << 31) - 1), y1 = y >> 31, y2 = y & ((1ULL << 31) - 1);
    ull z = x1 * y2 + x2 * y1, z1 = z >> 30, z2 = z & ((1ULL << 30) - 1);
    return hash_mod(x1 * y1 * 2 + x2 * y2 + z1 + (z2 << 31));
}

ull hash_pow(ull x, ull n) {
    ull ret = 1;
    for (; n > 0; n >>= 1, x = hash_mul(x, x)) {
        if (n & 1) ret = hash_mul(ret, x);
    }
    return ret;
}

// m 以上の base を乱択で生成する
ull base;
void generate_base(ull m = (1ULL << 50)) {
    while (true) {
        ull k = rng(mod);
        if (gcd(mod - 1, k) != 1) continue;
        base = hash_pow(3, k);
        if (base >= m) return;
    }
}

// 0 が含まれないように
template <typename T = string>
struct Rolling_Hash {
    const int n;
    vector<ull> hashed, pw;

    Rolling_Hash(const T &s) : n(s.size()) {
        hashed.assign(n + 1, 0), pw.assign(n + 1, 1);
        for (int i = 0; i < n; i++) {
            pw[i + 1] = hash_mul(pw[i], base);
            hashed[i + 1] = hash_mul(hashed[i], base) + s[i];
            if (hashed[i + 1] >= mod) hashed[i + 1] -= mod;
        }
    }

    // 文字列の [l,r) の部分のハッシュ値
    ull get_hash(int l, int r) const {
        ull ret = hashed[r] + mod - hash_mul(hashed[l], pw[r - l]);
        return ret - (ret >= mod ? mod : 0);
    }

    ull get_all_hash() const { return hashed[n]; }

    // s[l1:r1] と s[l2:r2] の最長共通接頭辞
    int lcp(int l1, int r1, int l2, int r2) {
        int ok = 0, ng = min(r1 - l1, r2 - l2) + 1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            (get_hash(l1, l1 + mid) == get_hash(l2, l2 + mid) ? ok : ng) = mid;
        }
        return ok;
    }

    // s[l1:r1] と s[l2:r2] の辞書順大小比較 (-1 : <, 0 : =, 1 : >)
    int comp(int l1, int r1, int l2, int r2) {
        int d = lcp(l1, r1, l2, r2);
        if (r1 == l1 + d && r2 == l2 + d) return 0;
        if (r1 == l1 + d) return -1;
        if (r2 == l2 + d) return 1;
        return get_hash(l1 + d, l1 + d + 1) < get_hash(l2 + d, l2 + d + 1) ? -1 : 1;
    }
};

struct Data_1 {
    ull v, p;
    Data_1(ull v, ull p) : v(v), p(p) {}
    Data_1(char c) : v(c), p(base) {}
    constexpr Data_1() : v(0), p(1) {}
};

struct Monoid_1 {
    using V = Data_1;
    static V merge(V a, V b) { return Data_1(hash_mod(hash_mul(a.v, b.p) + b.v), hash_mul(a.p, b.p)); }
    static const V id;
};

constexpr Monoid_1::V Monoid_1::id = Data_1();
// ----- library -------

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);

    generate_base();

    int n, l, q;
    cin >> n >> l >> q;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    vector<Segment_Tree<Monoid_1>> seg;
    rep(i, n) {
        vector<Data_1> v;
        rep(j, l) v.eb(s[i][j]);
        seg.eb(v);
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k;
            char c, d;
            cin >> k >> c >> d;
            k--;
            rep(i, n) if (s[i][k] == c) s[i][k] = d, seg[i].update(k, Data_1(d));
        }
        else {
            string t;
            cin >> t;
            int m = sz(t), ans = 0;
            rep(i, n) if (Rolling_Hash(t).get_all_hash() == seg[i].query(0, m).v) ans++;
            cout << ans << '\n';
        }
    }
}
yukicoder

結果

テストケース

ソースコード
