結果
| 問題 | No.2761 Substitute and Search |
| ユーザー |
 ゆにぽけ
|
| 提出日時 | 2024-05-17 21:59:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,071 ms / 4,000 ms |
| コード長 | 5,309 bytes |
| コンパイル時間 | 1,344 ms |
| コンパイル使用メモリ | 137,504 KB |
| 最終ジャッジ日時 | 2025-02-21 14:49:19 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>#include <chrono>using namespace std;using ull = unsigned long long;const ull mod = (1ULL << 61) - 1;ull mul(ull a,ull b){ull au = a >> 31;ull ad = a & ((1ULL << 31)-1);ull bu = b >> 31;ull bd = b & ((1ULL << 31)-1);ull mid = au*bd + bu*ad;ull midu = mid >> 30;ull midd = mid & ((1ULL << 30)-1);ull res = au*bu*2 + midu + (midd << 31) + ad*bd;res = (res >> 61) + (res & mod);if(res >= mod) res -= mod;return res;}mt19937_64 mt{(unsigned int)time(nullptr)};template<class T,T (*op)(T,T),T (*e)()> struct segtree{private:int size,N;vector<T> node;public:segtree(int N = 0) : segtree(vector<T>(N,e())) {}segtree(const vector<T> &V){N = (int)V.size();size = 1;while(size < N){size <<= 1;}node.assign(2 * size,e());for(int i = 0;i < N;i++){node[i + size] = V[i];}for(int i = size - 1;i >= 1;i--){node[i] = op(node[2 * i],node[2 * i + 1]);}}void replace(int pos,T x){func_update(pos,x,[](T u,T v){return u = v;});}void add(int pos,T x){func_update(pos,x,[](T u,T v){return u + v;});}void func_update(int pos,T x){func_update(pos,x,op);}void func_update(int pos,T x,T (*func)(T,T)){assert(0 <= pos && pos < N);pos += size;node[pos] = func(node[pos],x);while(pos >> 1){pos >>= 1;node[pos] = op(node[2 * pos],node[2 * pos + 1]);}}T operator[](int pos){assert(0 <= pos && pos < N);return node[pos + size];}int get_log(){int res = 0;while(1 << res < size){res++;}assert((1 << res) == size);return res;}vector<vector<T>> tree_list(){vector<vector<T>> res;int log = get_log();res.reserve(log + 1);for(int i = 0;i <= log;i++){int L = 1 << log,R = L << 1;vector<T> cur(node.begin() + L,node.begin() + R);res.push_back(cur);}return res;}//suppose that class T has ostream &operator<<void print(int k){assert(0 <= k && k <= get_log());int L = 1 << k,R = L << 1;for(int i = L;i < R;i++){cerr << node[i] << (i + 1 == R ? "\n":" ");}}void print(){int log = get_log();for(int k = 0;k <= log;k++){int L = 1 << k,R = L << 1;const string unit((1 << (log - k)) - 1,' ');for(int i = L;i < R;i++){if(i == L){cerr << unit;}cerr << node[i];if(i + 1 < R){cerr << unit << unit << ' ';}else{cerr << unit;}}cerr << "\n";}}T prod(int l,int r){assert(0 <= l && l <= r && r <= N);T L = e(),R = e();l += size,r += size;while(l < r){if(l & 1){L = op(L,node[l++]);}if(r & 1){R = op(node[--r],R);}l >>= 1,r >>= 1;}return op(L,R);}T prod(){return node[1];}template<class F> int max_right(int l,F f){assert(0 <= l && l <= N);assert(f(e()));if(l == N){return N;}l += size;T val = e();do{while(!(l & 1)){l >>= 1;}if(!f(op(val,node[l]))){while(l < size){l <<= 1;if(f(op(val,node[l]))){val = op(val,node[l++]);}}return l - size;}val = op(val,node[l++]);} while((l & -l) != l);return N;}template<class F> int min_left(int r,F f){assert(0 <= r && r <= N);assert(f(e()));if(r == 0){return 0;}r += size;T val = e();do{r--;while(r > 1 && (r & 1)){r >>= 1;}if(!f(op(node[r],val))){while(r < size){r <<= 1;r++;if(f(op(node[r],val))){val = op(node[r--],val);}}return r + 1 - size;}val = op(node[r],val);} while((r & -r) != r);return 0;}};ull op(ull a, ull b){return (a + b) % mod;}ull e(){return 0ull;}void Main(){const ull base = mt() % mod;int N, L, Q;cin >> N >> L >> Q;vector<ull> P(L);P[0] = 1;for(int i = 1;i < L;i++){P[i] = mul(P[i - 1], base);}vector<string> S(N);vector<segtree<ull, op, e>> seg(N);for(int i = 0;i < N;i++){cin >> S[i];vector<ull> init(L);for(int j = 0;j < L;j++){init[j] = mul(S[i][j], P[L - j - 1]);}seg[i] = segtree<ull, op, e>(init);}for(;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){S[i][k] = d;seg[i].replace(k, mul(d, P[L - k - 1]));}}}else{string T;cin >> T;ull H = 0;for(int i = 0;i < (int)T.size();i++){H = (H + mul(T[i], P[L - i - 1])) % mod;}int ans = 0;for(int i = 0;i < N;i++){if(seg[i].prod(0, T.size()) == H){ans++;}}cout << ans << "\n";}}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}