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

• 問題: No.2761 Substitute and Search
• ユーザー: GOTKAKO
• 提出日時: 2024-05-17 22:17:57
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 3,556 ms / 4,000 ms
• コード長: 6,155 bytes
• コンパイル時間: 2,938 ms
• コンパイル使用メモリ: 220,352 KB
• 実行使用メモリ: 155,008 KB
• 最終ジャッジ日時: 2024-05-17 22:18:28
• 合計ジャッジ時間: 25,409 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	3 ms; 6,944 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	1,962 ms; 155,008 KB
testcase_05	AC	3,556 ms; 155,008 KB
testcase_06	AC	465 ms; 154,880 KB
testcase_07	AC	2,557 ms; 155,008 KB
testcase_08	AC	494 ms; 155,008 KB
testcase_09	AC	2,556 ms; 155,008 KB
testcase_10	AC	467 ms; 155,008 KB
testcase_11	AC	2,543 ms; 155,008 KB
testcase_12	AC	1,585 ms; 154,880 KB
testcase_13	AC	1,510 ms; 155,008 KB
testcase_14	AC	1,508 ms; 155,008 KB
testcase_15	AC	1,465 ms; 154,880 KB

ソースコード

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

struct Modint64{
    //2^62未満&奇数modのみ.
    using Mint = Modint64;
    using u64 = uint64_t;
    using u128 = __uint128_t;
    static u64 mod,mod2,invmod,t128;
    u64 v = 0;
 
    Modint64(){v = 0;} Modint64(long long w){v = reduce((u128(w)+mod)*t128);}
    u64 val()const{
        u64 ret = reduce(v);
        return ret >= mod ? ret-mod : ret;
    }
    static u64 getmod(){return mod;}
    static u64 getinvmod(){
        u64 ret = mod;
        for(int i=0; i<5; i++) ret *= 2-mod*ret;
        return ret;
    }
    static void setmod(u64 m){
        assert((m<(1LL<<62)) && (m&1));
        mod = m; mod2 = m*2;
        t128 = -u128(mod)%mod;
        invmod = getinvmod();
    }
    static u64 reduce(const u128 &v){return (v+u128(u64(v)*u64(-invmod))*mod) >> 64;}
 
    Mint operator+(const Mint &b)const{return Mint(*this)+=b;}
    Mint operator-(const Mint &b)const{return Mint(*this)-=b;}
    Mint operator*(const Mint &b)const{return Mint(*this)*=b;}
    Mint operator/(const Mint &b)const{return Mint(*this)/=b;}
    Mint operator-()const{return Mint()-Mint(*this);}
    Mint& operator+=(const Mint &b){
        v += b.v;
        if(v >= mod2) v -= mod2;
        return *this; 
    }
    Mint& operator-=(const Mint &b){
        v += mod2-b.v;
        if(v >= mod2) v -= mod2;
        return *this;
    }
    Mint& operator*=(const Mint &b){
        v = reduce(u128(v)*b.v);
        return *this;
    }
    Mint& operator/=(const Mint &b){
        *this *= b.inv();
        return *this;
    }
    Mint pow(u128 b)const{
        Mint ret(1),p(*this);
        while(b){
            if(b&1) ret *= p;
            p = p*p; b >>= 1;
        }
        return ret;
    }
    Mint inv()const{return pow(mod-2);}
    
    bool operator==(const Mint &b)const{return (v >= mod?v-mod:v) == (b.v >= mod?b.v-mod:b.v);}
    bool operator!=(const Mint &b)const{return (v >= mod?v-mod:v) != (b.v >= mod?b.v-mod:b.v);}
};
typename Modint64::u64
Modint64::mod,Modint64::mod2,Modint64::invmod,Modint64::t128;
 
bool MillerRabin(long long N,vector<long long> A){
    using Mint = Modint64;
    Mint::setmod(N);
    int s = 0; long long d = N-1;
    while(d%2 == 0){s++,d >>= 1;}
    for(auto a : A){
        if(N <= a) return true;
        int t = 0; Mint x = Mint(a).pow(d);
        if(x != 1){
            for(; t < s; t++){
                if(x == N-1) break;
                x *= x;
            }
            if(t == s) return false;
        }
    }
    return true;
}
bool isprime(long long N){
    if(N <= 1) return false;
    if(N == 2) return true;
    if(N%2 == 0) return false;
    if(N < 475912314) return MillerRabin(N,{2,7,61});
    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;
    }
}
int getvalue(int minv,int range){return mt()%range+minv;}

struct SS{
    int len; long long hash;
    bool operator==(SS &b){return (len == b.len && hash == b.hash);}
};
class SegmentTreeHash{
    public:
    int siz = 1,n = -1;;
    long long B = 1,mod = 1;
    vector<long long> pB;
    vector<SS> dat;
 
    SS op(SS a, SS b){return {a.len+b.len,(a.hash*pB.at(b.len)+b.hash)%mod};}
    SS e(){return {0,0};}
    void renew (SS &a,SS x){
        //a = op(a,x);
        a = x;
        //その他.
    }
 
    void make(int N){
        n = N;
        while(siz < N) siz *= 2;
        dat.resize(siz*2,{0,0});
    }
 
    void make3(int N,string &A,int M,int b){
        make(N); pB.resize(N+1,1);
        mod = M; B = b;
        for(int i=1; i<=N; i++) pB.at(i) = pB.at(i-1)*B%mod; 
        for(int i=0; i<N; i++){
            int pos = i+siz;
            dat.at(pos) = {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));
    }
 
    void update(int pos,char x){
        int pos2 = n-1-pos+siz; pos += siz;
        renew(dat.at(pos),{1,x});
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    }
 
    SS findans(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 rangeans(int l,int r){return findans(l,r);}
    //ノーマルセグ木 二分探索は実装してない.
};

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

    int N,L,Q; cin >> N >> L >> Q;
    long long mod = getprime1(1000000000,1000000),B = getvalue(1000000,1000000);
    long long mod2 = getprime1(1000000000,1000000),B2 = getvalue(1000000,1000000);
    vector<vector<SegmentTreeHash>> Z(N,vector<SegmentTreeHash>(1));
    for(int i=0; i<N; i++){
        string s; cin >> s;
        Z.at(i).at(0).make3(L,s,mod,B);
    }

    while(Q--){
        int ope; cin >> ope;
        if(ope == 1){
            int pos; char c,d; cin >> pos >> c >> d; pos--;
            for(int i=0; i<N; i++) for(int k=0; k<1; k++){
                SS now = Z.at(i).at(k).get1(pos);
                if(now.hash == c) Z.at(i).at(k).update(pos,d);
                now = Z.at(i).at(k).get1(pos);
            }
        }
        if(ope == 2){
            string t; cin >> t;
            long long hash1 = 0,hash2 = 0;
            for(auto c : t){
                hash1 = hash1*B%mod;
                hash1 += c; hash1 %= mod;
            }
            int n = t.size(),answer = 0;
            for(int i=0; i<N; i++){
                SS now1 = Z.at(i).at(0).rangeans(0,n);
                if(now1.hash == hash1) answer++;
            }
            cout << answer << "\n";
        }
    }
}