結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
![]() |
提出日時 | 2024-05-22 02:28:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,565 ms / 4,000 ms |
コード長 | 1,963 bytes |
コンパイル時間 | 399 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 273,920 KB |
最終ジャッジ日時 | 2024-12-20 18:19:22 |
合計ジャッジ時間 | 26,649 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
def segfunc(x, y): return x + y class SegTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])%MOD def update(self, k, x): k += self.num self.tree[k] = x while k > 1: self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])%MOD k >>= 1 def query(self, l, r): res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l])%MOD l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1])%MOD l >>= 1 r >>= 1 return res N, L, Q = map(int, input().split()) S = [list(input()) for _ in range(N)] query = [list(input().split()) for _ in range(Q)] MOD = 4644785202401563 POW = [1] for _ in range(L-1): POW.append(POW[-1]*26%MOD) SEG = [] for i in range(N): A = [] for j in range(L): A.append(POW[j]*(ord(S[i][j])-ord("a")+1)%MOD) SEG.append(SegTree(A, segfunc, 0)) for i in range(Q): if query[i][0] == "1": k, c, d = query[i][1:] k = int(k)-1 for j in range(N): if S[j][k] == c: S[j][k] = d SEG[j].update(k, POW[k]*(ord(d)-ord("a")+1)%MOD) else: t = query[i][1] hash = 0 for j in range(len(t)): hash += POW[j]*(ord(t[j])-ord("a")+1)%MOD hash %= MOD cnt = 0 for j in range(N): if SEG[j].query(0, len(t)) == hash: cnt += 1 print(cnt)