#1178925 (C++23) No.3638 Itsuki

• 問題: No.3638 Itsuki
• ユーザー: shobonvip
• 提出日時: 2026-08-25 14:19:38
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 85 ms / 3,000 ms
• コード長: 3,167 bytes
• コンパイル時間: 4,110 ms
• コンパイル使用メモリ: 378,232 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 14:20:43
• 合計ジャッジ時間: 6,541 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 2
小課題1	10 %	AC * 5
小課題2	50 %	AC * 6
小課題3	40 %	AC * 18
合計	100 点

ソースコード

/**
	author:  shobonvip
	created: 2026.08.25 14:16:01
**/

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

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

using ull = unsigned long long;
struct roriha {
   static constexpr ull mask30 = (1ULL << 30) - 1;
   static constexpr ull mask31 = (1ULL << 31) - 1;
   static constexpr ull mask61 = (1ULL << 61) - 1;
   static constexpr ull mod = (1ULL << 61) - 1;
   static constexpr ull positive = mod * 4;
   static inline ull base = 0;
   static inline vector<ull> pows = {1};
   static ull mul(ull a, ull b) {
      ull au = a >> 31, ad = a & mask31;
      ull bu = b >> 31, bd = b & mask31;
      ull mid = ad * bu + au * bd;
      ull midu = mid >> 30, midd = mid & mask30;
      return (au * bu * 2 + midu + (midd << 31) + ad * bd);
   }
   static ull cal(ull x) {
      ull xu = x >> 61, xd = x & mask61;
      ull ret = xu + xd;
      if(ret >= mod) ret -= mod;
      return ret;
   }
   static void sethash() {
      if(base == 0) base = (1ULL << 31) + (random_device()() & mask31);
   }
   static void extend(int len) {
      int nlen = pows.size();
      if(nlen > len) return;
      pows.resize(len + 1);
      rep(i, nlen, len + 1) { pows[i] = cal(mul(pows[i - 1], base)); }
   }
   vector<ull> inner;
   roriha(string s = "") {
      sethash();
      int n = s.size();
      extend(n);
      inner.resize(n + 1);
      inner[0] = 0;
      rep(i, 0, n) inner[i + 1] = cal(mul(inner[i], base) + s[i]);
   }
   ull get(int l, int r) { return cal(inner[r] + positive - mul(inner[l], pows[r - l])); }
   static ull concat(ull h1, ull h2, int len2) { return cal(cal(mul(h1, pows[len2])) + h2); }
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, q;
	cin >> n >> q;
	string s; cin >> s;
	roriha rh(s);
	while(q--) {
		int t; cin >> t;
		if (t == 1) {
			int i; cin >> i; i--;
			char c; cin >> c;
			s[i] = c;
			rh = roriha(s);
		} else {
			string t; cin >> t;
			int m = (int)t.size();
			roriha rh2 = roriha(t);
			bool mode = 0;
			rep(i,0,n-m+1) {
				if (rh2.get(0,m) == rh.get(i,i+m)){
					mode = 1;
					break;
				}
			}
			if (mode) {
				cout << "Yes\n";
			} else {
				cout << "No\n";
			}
		}
	}

}