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

• 問題: No.2761 Substitute and Search
• ユーザー: GOTKAKO
• 提出日時: 2025-04-30 09:20:20
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 3,600 ms / 4,000 ms
• コード長: 9,920 bytes
• コンパイル時間: 3,274 ms
• コンパイル使用メモリ: 218,736 KB
• 実行使用メモリ: 334,336 KB
• 最終ジャッジ日時: 2025-04-30 09:20:46
• 合計ジャッジ時間: 23,558 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 13

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Montgomery{
    //2^62未満&奇数modのみ.
    //初めにsetmodする.
    using u64 = uint64_t;
    using u128 = __uint128_t;
 
    private:
    static u64 mod,N2,Rsq; //N*N2≡1(mod N);
    //Rsq = R^2modN; R=2^64.
    u64 v = 0;
    public:
    long long val(){return reduce(v);}
    u64 getmod(){return mod;}
    static void setmod(u64 m){
        assert(m<(1LL<<62)&&(m&1));
        mod = m; N2 = mod;
        for(int i=0; i<5; i++) N2 *= 2-N2*mod;
        Rsq = (-u128(mod))%mod;
    }
    //reduce = T*R^-1modNを求める.
    u64 reduce(const u128 &T){
        //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い.
        u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    //初期値<mod. 初めにw*R modN...->reduce(R^2)でok.
    Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){}
 
    Montgomery& operator=(const Montgomery &b) = default;
    Montgomery operator-()const{return Montgomery()-Montgomery(*this);}
    Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;}
    Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;}
    Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;}
    Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;}
    Montgomery& operator+=(const Montgomery &b){
        v += b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator-=(const Montgomery &b){
        v += mod-b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery& operator*=(const Montgomery &b){
        v = reduce(u128(v)*b.v);
        return (*this);
    }
    Montgomery& operator/=(const Montgomery &b){
        (*this) *= b.inv();
        return (*this);
    }
    Montgomery pow(u64 b)const{
        Montgomery ret = 1,p = (*this);
        while(b){
            if(b&1) ret *= p;
            p *= p; b >>= 1;
        }
        return ret;
    }
    Montgomery inv()const{return pow(mod-2);}
 
    bool operator!=(const Montgomery &b)const{return v!=b.v;}
    bool operator==(const Montgomery &b)const{return v==b.v;}
};
typename Montgomery::u64 Montgomery::mod,Montgomery::N2,Montgomery::Rsq;
using mont = Montgomery;
bool MillerRabin(long long N,const vector<long long> &A){
    mont::setmod(N);
    long long s = __builtin_ctzll(N-1),d = N-1;
    d >>= s;
    for(auto &a : A){
        if(N <= a) break;
        mont x = mont(a).pow(d);
        if(x != 1){
            long long t;
            for(t=0; t<s; t++){
                if(x == N-1) break;
                x *= x;
            }
            if(t == s) return false;
        }
    }
    return true;
}
bool isprime(const long long N){
    if(N <= 1) return false;
    else if(N == 2) return true;
    else if(N%2 == 0) return false;
    else if(N < 4759123141LL) return MillerRabin(N,{2,7,61});
    else return MillerRabin(N, {2,325,9375,28178,450775,9780504,1795265022});
}

random_device rnd;
mt19937 mt(rnd());
mt19937_64 mt2(rnd());
int getprime1(int minv,int range){
    assert(minv+range >= 2);
    int ret = -1;
    while(true){
        ret = mt()%range+minv;
        if(isprime(ret)) return ret;
    }
}
long long getprime2(long long minv,long long range){
    assert(minv+range >= 2);
    long long ret = -1;
    while(true){
        ret = mt2()%range+minv;
        if(isprime(ret)) return ret;
    }
}

using SS = pair<int,mont>;
class SegmentTreeHash{
    public:
    int siz = -1,n = -1;
    long long mod;
    mont b;
    vector<mont> pb;
    vector<SS> dat,dat2; //dat2->rev(dat)
 
    SS op(SS a, SS b){return {a.first+b.first,a.second+pb.at(a.first)*b.second};} //ここpowにすれば連長圧縮なら長さ大きくてもいけそう.
    SS e(){return {0,0};}
    void renew (SS &a,SS x){
        a = op(a,x);
        //a = x; //set(pos,x)で可能.
        //その他.
    }
    void SetmodBase(long long Mod,mont B){
        if(Mod == 0){
            mod = getprime2((long long)1e18,(long long)1e17);
            b = mt2()%1001001001+1001001001;
            mont::setmod(mod);
        }
        else mod = Mod,b = B;
        pb.resize(siz*2); pb.at(0) = 1;
        for(int i=1; i<siz*2; i++) pb.at(i) = pb.at(i-1)*b;
    }
    pair<long long,mont> getmodBase(){return {mod,b};}

    SegmentTreeHash(int N,pair<long long,mont> mb = {0,0}){init(N,mb);}
    //mbは1通りしか認めない(モンゴメリ乗算の仕様上複数のセグ木で各々異なるmbを同時に使用することはできない).
    SegmentTreeHash(const vector<int> &A,pair<long long,mont> mb = {0,0}){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e()),dat2.resize(siz*2,e());
        SetmodBase(mb.first,mb.second);
        for(int i=0; i<n; i++) dat.at(i+siz) = {1,A.at(i)}; //Baseの都合上intだけ?.
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
        for(int i=0; i<n; i++) dat2.at(i+siz) = {1,A.at(n-1-i)};
        for(int i=siz-1; i>0; i--) dat2.at(i) = op(dat2.at(i*2),dat2.at(i*2+1));
    }
    SegmentTreeHash(const string &s,pair<long long,mont> mb = {0,0}){ 
        siz = 1; n = s.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e()),dat2.resize(siz*2,e());
        SetmodBase(mb.first,mb.second);
        for(int i=0; i<n; i++) dat.at(i+siz) = {1,s.at(i)}; //charでok.
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
        for(int i=0; i<n; i++) dat2.at(i+siz) = {1,s.at(n-1-i)};
        for(int i=siz-1; i>0; i--) dat2.at(i) = op(dat2.at(i*2),dat2.at(i*2+1));
    }
    void init(int N,pair<long long,mont> mb = {0,0}){
        //全要素単位元に初期化.
        siz = 1; n = N;
        while(siz < n) siz *= 2;
        dat.assign(siz*2,e()),dat2.assign(siz*2,e());
        SetmodBase(mb.first,mb.second);
    }
    void init(const vector<int> &A){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e()),dat2.resize(siz*2,e());
        SetmodBase(mod,b);
        for(int i=0; i<n; i++) dat.at(i+siz) = {1,A.at(i)};
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
        for(int i=0; i<n; i++) dat2.at(i+siz) = {1,A.at(n-1-i)};
        for(int i=siz-1; i>0; i--) dat2.at(i) = op(dat2.at(i*2),dat2.at(i*2+1));
    }
    void init(const string &s){
        siz = 1; n = s.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e()),dat2.resize(siz*2,e());
        SetmodBase(mod,b);
        for(int i=0; i<n; i++) dat.at(i+siz) = {1,s.at(i)};
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
        for(int i=0; i<n; i++) dat2.at(i+siz) = {1,s.at(n-1-i)};
        for(int i=siz-1; i>0; i--) dat2.at(i) = op(dat2.at(i*2),dat2.at(i*2+1));
    }
    void set(int pos,SS x){ //len=1限定?.
        int memo = pos;
        pos = pos+siz;
        dat.at(pos) = x;
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
        pos = memo; pos = n-1-memo;
        pos = pos+siz;
        dat2.at(pos) = x;
        while(pos != 1){
            pos = pos/2;
            dat2.at(pos) = op(dat2.at(pos*2),dat2.at(pos*2+1));
        }
    }
    void update(int pos,SS x){
        assert(false); //多分使わない.
        int memo = pos;
        pos = pos+siz;
        renew(dat.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
        pos = memo; pos = n-1-memo;
        pos = pos+siz;
        renew(dat2.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat2.at(pos) = op(dat2.at(pos*2),dat2.at(pos*2+1));
        }
    }
    SS rangeans1(int l, int r){
        SS retl = e(),retr = e();
        l += siz,r += siz;
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS get1(int pos){return dat.at(pos+siz);}
    SS allrange1(){return dat.at(1);}
    SS rangeans2(int l,int r){
        r--; swap(l,r);
        l = n-1-l,r = n-1-r; r++;
        SS retl = e(),retr = e();
        l += siz,r += siz;
        while(l < r){
            if(l&1) retl = op(retl,dat2.at(l++));
            if(r&1) retr = op(dat2.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS get2(int pos){return dat2.at(n-1-pos+siz);}
    SS allrange2(){return dat2.at(1);}
    bool ispalindrome(int l,int r){return rangeans1(l,r) == rangeans2(l,r);}
    mont gethash(const vector<int> &A){
        mont ret = 0,mul = 1;
        for(auto a : A) ret += mul*a,mul *= b;
        return ret;
    }
    mont gethash(const string &s){
        mont ret = 0,mul = 1;
        for(auto c : s) ret += mul*c,mul *= b;
        return ret;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,L,Q; cin >> N >> L >> Q;
    vector<string> S(N);
    vector<SegmentTreeHash> Z;
    long long Mod = 0; mont B = 0;
    for(auto &s : S){
        cin >> s,Z.emplace_back(SegmentTreeHash(s,{Mod,B}));
        if(Mod == 0) tie(Mod,B) = Z.back().getmodBase();
    }
    while(Q--){
        int T; cin >> T;
        if(T == 1){
            int p; char c,d; cin >> p >> c >> d; p--;
            for(int i=0; i<N; i++) if(S.at(i).at(p) == c) S.at(i).at(p) = d,Z.at(i).set(p,{1,d});
        }
        else{
            string t; cin >> t;
            mont now = Z.at(0).gethash(t);
            int answer = 0;
            for(int i=0; i<N; i++) answer += Z.at(i).rangeans1(0,t.size()).second==now;
            cout << answer << "\n";
        }
    }
}