結果
| 問題 |
No.2761 Substitute and Search
|
| コンテスト | |
| ユーザー |
 apricity
|
| 提出日時 | 2024-05-20 02:34:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,325 ms / 4,000 ms |
| コード長 | 7,073 bytes |
| コンパイル時間 | 1,627 ms |
| コンパイル使用メモリ | 136,164 KB |
| 最終ジャッジ日時 | 2025-02-21 16:15:08 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#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);
}
}
}