結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
|
提出日時 | 2024-05-31 13:59:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 4,000 ms |
コード長 | 1,704 bytes |
コンパイル時間 | 4,813 ms |
コンパイル使用メモリ | 263,232 KB |
最終ジャッジ日時 | 2025-02-21 17:20:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <algorithm> #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; int N,L,Q; vector<string> S; vector<int> OP; vector<string> T; vector<int> K; vector<char> C,D; using mint = modint998244353; mint op(mint a, mint b){ return a+b; } mint e(){ return 0; } void solve(){ int base = 364; vector<mint> coef(L); coef[0] = 1; for(int i = 1;i<L;i++){ coef[i] = coef[i-1]*base; } vector<segtree<mint, op, e>> segs(N); for(int i = 0;i<N;i++){ segtree<mint, op, e> seg(L); for(int j = 0;j<L;j++){ seg.set(j, mint(S[i][j]-'a')*coef[j]); } segs[i] = seg; } for(int i = 0;i<Q;i++){ if(OP[i] == 1){ for(int j = 0;j<N;j++){ if(S[j][K[i]-1] == C[i]){ S[j][K[i]-1] = D[i]; segs[j].set(K[i]-1, mint(D[i]-'a')*coef[K[i]-1]); } } }else{ mint rh = 0; for(int j = 0;j<T[i].size();j++){ rh += mint(T[i][j]-'a')*coef[j]; } int ans = 0; for(int j = 0;j<N;j++){ if(segs[j].prod(0, T[i].size())==rh){ ans++; } } cout<<ans<<endl; } } } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> N >> L >> Q; S.resize(N); OP.resize(Q); T.resize(Q); K.resize(Q); C.resize(Q); D.resize(Q); for(int i = 0;i<N;i++){ cin >> S[i]; } for(int i = 0;i<Q;i++){ cin >> OP[i]; if(OP[i] == 2){ cin >> T[i]; }else{ cin >> K[i] >> C[i] >> D[i]; } } solve(); }