#1179321 (C++17) No.3638 Itsuki

• 問題: No.3638 Itsuki
• ユーザー: tnakao0123
• 提出日時: 2026-08-26 11:18:20
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 656 ms / 3,000 ms
• コード長: 3,215 bytes
• コンパイル時間: 418 ms
• コンパイル使用メモリ: 72,832 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-26 11:18:30
• 合計ジャッジ時間: 4,116 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3638.cc:  No.3638 Itsuki - yukicoder
 */

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 5000;
const int MAX_L = 1000;
const int P = 4073;
const int MOD = 1000000007;

/* typedef */

template<const int MOD>
struct MI {
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }

  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }

  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }

  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }

  MI pow(int n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }

  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};

using mi = MI<MOD>;
using vmi = vector<mi>;

template <typename T>
struct BIT {
  int n;
  vector<T> bits;
  
  BIT() {}
  BIT(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    bits.assign(n + 1, 0);
  }

  T sum(int x) {
    x = min(x, n);
    T s = 0;
    while (x > 0) {
      s += bits[x];
      x -= (x & -x);
    }
    return s;
  }

  void add(int x, T v) {
    if (x <= 0) return;
    while (x <= n) {
      bits[x] += v;
      x += (x & -x);
    }
  }
};

/* global variables */

vmi pes, invpes;
char s[MAX_N + 4], t[MAX_L + 4];

/* subroutines */

void prep_rhash(int n) {
  pes.resize(n + 1), invpes.resize(n + 1);
  pes[0] = invpes[0] = 1;
  pes[1] = P;
  invpes[1] = pes[1].inv();
  for (int i = 2; i <= n; i++) {
    pes[i] = pes[i - 1] * P;
    invpes[i] = invpes[i - 1] * invpes[1];
  }
}

BIT<mi> s2rh(int n, const char s[]) {
  BIT<mi> bit;
  bit.init(n);
  for (int k = 0; k < n; k++)
    bit.add(k + 1, pes[k] * s[k]);
  return bit;
}

mi s2h(const char s[]) {
  mi h = 0;
  for (int k = 0; s[k]; k++) h += pes[k] * s[k];
  return h;
}

mi rhash(BIT<mi> &rh, int i, int j) {
  return (rh.sum(j) - rh.sum(i)) * invpes[i];
}

/* subroutines */

/* main */

int main() {
  prep_rhash(MAX_N);
  
  int n, qn;
  scanf("%d%d%s", &n, &qn, s);

  auto rh = s2rh(n, s);

  while (qn--) {
    int op;
    scanf("%d", &op);

    if (op == 1) {
      int i;
      scanf("%d%s", &i, t), i--;

      rh.add(i + 1, -pes[i] * s[i]);
      s[i] = t[0];
      rh.add(i + 1, pes[i] * s[i]);
    }
    else {
      scanf("%s", t);
      int l = strlen(t);
      auto th = s2h(t);

      bool found = false;
      for (int i = 0; i + l <= n; i++)
	if (rhash(rh, i, i + l) == th && ! strncmp(s + i, t, l)) {
	  found = true; break;
	}
      
      if (found) puts("Yes");
      else puts("No");
    }
  }
  
  return 0;
}