結果

問題 No.2761 Substitute and Search
ユーザー apricityapricity
提出日時 2024-05-20 02:34:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 996 ms / 4,000 ms
コード長 7,073 bytes
コンパイル時間 1,644 ms
コンパイル使用メモリ 142,092 KB
実行使用メモリ 53,760 KB
最終ジャッジ日時 2024-05-20 02:34:49
合計ジャッジ時間 11,498 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 597 ms
53,632 KB
testcase_05 AC 996 ms
53,632 KB
testcase_06 AC 254 ms
53,760 KB
testcase_07 AC 650 ms
53,632 KB
testcase_08 AC 233 ms
53,632 KB
testcase_09 AC 684 ms
53,760 KB
testcase_10 AC 230 ms
53,632 KB
testcase_11 AC 708 ms
53,632 KB
testcase_12 AC 467 ms
53,632 KB
testcase_13 AC 463 ms
53,632 KB
testcase_14 AC 492 ms
53,632 KB
testcase_15 AC 462 ms
53,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<utility>
#include<tuple>
#include<cstdint>
#include<cstdio>
#include<iomanip>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<cctype>
#include<chrono>
#include<random>
#include<cassert>
#include<cstddef>
#include<iterator>
#include<string_view>
#include<type_traits>

#ifdef LOCAL
#  include "debug_print.hpp"
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
template<typename T> using PQ = priority_queue<T,vector<T>>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void yesno(bool flag) {cout << (flag?"Yes":"No") << "\n";}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}
template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    int s = (int)v.size();
    for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
    return os;
}
template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
void in() {}
template<typename T, class... U>
void in(T &t, U &...u) {
    cin >> t;
    in(u...);
}
void out() { cout << "\n"; }
template<typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
    cout << t;
    if (sizeof...(u)) cout << sep;
    out(u...);
}
void outr() {}
template<typename T, class... U, char sep = ' '>
void outr(const T &t, const U &...u) {
    cout << t;
    outr(u...);
}
#line 1 "string/rolling-hash.hpp"
/**
 * @brief Rolling-Hash(ローリングハッシュ)
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 * @docs docs/rolling-hash.md
 */
  const uint64_t mod = (1ull << 61ull) - 1;
  using uint128_t = __uint128_t;
  uint64_t add(uint64_t a, uint64_t b) {
    if((a += b) >= mod) a -= mod;
    return a;
  }
  uint64_t sub(uint64_t a, uint64_t b) {
    return add(a, mod-b);
  }

  uint64_t mul(uint64_t a, uint64_t b) {
    uint128_t c = (uint128_t) a * b;
    return add(c >> 61, c & mod);
  }

struct RollingHash {
  vector< uint64_t > power;
  const uint64_t base;


  static inline uint64_t generate_base() {
    mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution< uint64_t > rand(1, mod - 1);
    return rand(mt);
  }

  inline void expand(size_t sz) {
    if(power.size() < sz + 1) {
      int pre_sz = (int) power.size();
      power.resize(sz + 1);
      for(int i = pre_sz - 1; i < sz; i++) {
        power[i + 1] = mul(power[i], base);
      }
    }
  }

  explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {}

  vector< uint64_t > build(const string &s) const {
    int sz = s.size();
    vector< uint64_t > hashed(sz + 1);
    for(int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  template< typename T >
  vector< uint64_t > build(const vector< T > &s) const {
    int sz = s.size();
    vector< uint64_t > hashed(sz + 1);
    for(int i = 0; i < sz; i++) {
      hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
  }

  uint64_t query(const vector< uint64_t > &s, int l, int r) {
    expand(r - l);
    return add(s[r], mod - mul(s[l], power[r - l]));
  }

  uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {
    expand(h2len);
    return add(mul(h1, power[h2len]), h2);
  }

  int lcp(const vector< uint64_t > &a, int l1, int r1, const vector< uint64_t > &b, int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = 0, high = len + 1;
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return low;
  }
};

template <class Abel = uint64_t> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set

    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }

    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = add(dat[p][i], x);
    }
    inline void addf(int a, int b, Abel x) {
        sub_add(0, a, mul(x,sub(0,a-1)));
        sub_add(1, a, x);
        sub_add(0, b, mul(x,(b - 1)));
        sub_add(1, b, sub(0,x));
    }

    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = add(res,dat[p][i]);
        return res;
    }
    inline Abel sum(int a, int b) {
        Abel res = add(sub_sum(0,b-1), mul(sub_sum(1,b-1),b-1));
        res = sub(res, sub_sum(0,a-1));
        res = sub(res, mul(sub_sum(1,a-1),a-1));
        return res;
        // return sub_sum(0, b - 1) + mul(sub_sum(1, b - 1) , b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }

    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l,q; in(n,l,q);
    vector<string> s(n); in(s);
    uint64_t bs = RollingHash::generate_base();

    vector<uint64_t> pr(l+1); pr[0] = 1;
    rep(i,l) pr[i+1] = mul(pr[i], bs);
    vector<BIT<>> b(n,BIT<>(l+5));
    rep(i,n){
        rep(j,l) b[i].addf(j+1,j+2,mul(s[i][j]-'a', pr[j]));
    }
    while(q--){
        int type; in(type);
        if(type==1){
            int k; char c,d; in(k,c,d); k--;
            rep(i,n){
                if(s[i][k]==c){
                    uint64_t diff = mul(sub(d,c), pr[k]);
                    b[i].addf(k+1,k+2,diff);
                    s[i][k]=d;
                }
            }
        }
        else{
            string t; in(t); int m = t.size();
            uint64_t ht = 0;
            rep(i,m) ht = add(ht, mul(t[i]-'a',pr[i]));
            int ans = 0;
            rep(i,n) if(ht == b[i].sum(1,m+1)) ans++;
            out(ans);
        }
    }
}
0