結果

問題 No.2761 Substitute and Search
ユーザー norioc
提出日時 2025-05-07 04:44:19
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 5,299 bytes
コンパイル時間 6,501 ms
コンパイル使用メモリ 83,124 KB
実行使用メモリ 331,656 KB
最終ジャッジ日時 2025-05-07 04:44:38
合計ジャッジ時間 14,786 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 2 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.io.*;

public class Main {
    static int _ceilPow2(int n) {
        int x = 0;
        while ((1 << x) < n) x++;
        return x;
    }

    interface Op<T> {
        T apply(T a, T b);
    }

    static class SegTree<T> {
        private final Op<T> op;
        private final T e;
        private final int n, log, size;
        private final Object[] d;

        public SegTree(Op<T> op, T e, List<T> v) {
            this.op = op;
            this.e = e;
            this.n = v.size();
            this.log = _ceilPow2(n);
            this.size = 1 << log;
            this.d = new Object[2 * size];
            Arrays.fill(d, e);

            for (int i = 0; i < n; i++) {
                d[size + i] = v.get(i);
            }
            for (int i = size - 1; i > 0; i--) {
                update(i);
            }
        }

        public void set(int p, T x) {
            if (p < 0 || p >= n) throw new AssertionError();
            p += size;
            d[p] = x;
            for (int i = 1; i <= log; i++) {
                update(p >> i);
            }
        }

        @SuppressWarnings("unchecked")
        public T get(int p) {
            if (p < 0 || p >= n) throw new AssertionError();
            return (T) d[p + size];
        }

        @SuppressWarnings("unchecked")
        public T prod(int l, int r) {
            if (l < 0 || l > r || r > n) throw new AssertionError();
            T sml = e;
            T smr = e;
            l += size;
            r += size;
            while (l < r) {
                if ((l & 1) == 1) sml = op.apply(sml, (T) d[l++]);
                if ((r & 1) == 1) smr = op.apply((T) d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op.apply(sml, smr);
        }

        @SuppressWarnings("unchecked")
        public T allProd() {
            return (T) d[1];
        }

        private void update(int k) {
            d[k] = op.apply((T) d[2 * k], (T) d[2 * k + 1]);
        }
    }

    static class RollingHashOnSegTree {
        final int B = 1009;
        final int MOD = 998244353;
        SegTree<long[]> segt;

        public RollingHashOnSegTree(String s) {
            Op<long[]> op = (a, b) -> {
                long h = (a[0] * powMod(B, b[1], MOD) + b[0]) % MOD;
                return new long[]{h, a[1] + b[1]};
            };

            List<long[]> v = new ArrayList<>();
            for (char c : s.toCharArray()) {
                v.add(new long[]{c, 1});
            }
            this.segt = new SegTree<>(op, new long[]{0, 0}, v);
        }

        public char get(int p) {
            return (char) segt.get(p)[0];
        }

        public void set(int p, char c) {
            segt.set(p, new long[]{c, 1});
        }

        public long prod(int l, int r) {
            return segt.prod(l, r)[0];
        }

        public long allProd() {
            return segt.allProd()[0];
        }
    }

    static long rh(String s) {
        final int B = 1009;
        final int MOD = 998244353;
        long h = 0;
        for (char c : s.toCharArray()) {
            h = (h * B + c) % MOD;
        }
        return h;
    }

    static long powMod(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader();
        int N = in.nextInt();
        int L = in.nextInt();
        int Q = in.nextInt();

        List<RollingHashOnSegTree> hs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String S = in.next();
            hs.add(new RollingHashOnSegTree(S));
        }

        for (int i = 0; i < Q; i++) {
            String[] qs = in.nextLine().split(" ");
            if (qs[0].equals("1")) {
                int k = Integer.parseInt(qs[1]) - 1;
                char c = qs[2].charAt(0);
                char d = qs[3].charAt(0);
                for (RollingHashOnSegTree h : hs) {
                    if (h.get(k) == c) {
                        h.set(k, d);
                    }
                }
            } else if (qs[0].equals("2")) {
                String t = qs[1];
                long th = rh(t);
                int res = 0;
                for (RollingHashOnSegTree h : hs) {
                    if (h.prod(0, t.length()) == th) {
                        res++;
                    }
                }
                System.out.println(res);
            }
        }
    }

    // 高速入力
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        String nextLine() throws IOException {
            return br.readLine();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}
0