結果

問題 No.3239 Omnibus
ユーザー NyaanNyaan
提出日時 2025-08-15 22:32:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 556 ms / 10,000 ms
コード長 1,625 bytes
コンパイル時間 933 ms
コンパイル使用メモリ 81,992 KB
実行使用メモリ 90,812 KB
最終ジャッジ日時 2025-08-15 22:32:37
合計ジャッジ時間 14,364 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include <iostream>

#ifdef NyaanLocal
#include "misc/timer.hpp"
#endif
using namespace std;

int N, Q;
char S[200200], a[4];
int A[200200];

constexpr int B = 500;
long long sum[B][26 * 26 * 26];
int num[B][26 * 26 * 26];

void update(int k, bool first = false) {
  if (!(0 <= k and k + 2 < N)) return;
  if (!first) sum[k / B][A[k]] -= k, num[k / B][A[k]]--;
  A[k] = S[k] + S[k + 1] * 26 + S[k + 2] * 676;
  sum[k / B][A[k]] += k, num[k / B][A[k]]++;
}

long long query(int l, int r) {
  int x = a[0] + a[1] * 26 + a[2] * 676;
  int init_l = l;
  long long ans = 0, bns = 0;
  if (l + B + 2 < r) {
    while (l % B != 0) {
      ans += A[l] == x ? l : 0;
      bns += A[l] == x ? 1 : 0;
      l++;
    }
    while (l + B + 2 < r) {
      ans += sum[l / B][x];
      bns += num[l / B][x];
      l += B;
    }
  }
  while (l + 2 < r) {
    ans += A[l] == x ? l : 0;
    bns += A[l] == x ? 1 : 0;
    l++;
  }
  return ans - bns * (init_l - 1);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
#ifdef NyaanLocal
  Timer timer;
#endif
  cin >> N >> Q >> S;
  for (int i = 0; i < N; i++) S[i] -= 'a';
  for (int i = 0; i + 2 < N; i++) update(i, true);
  while (Q--) {
    int cmd;
    cin >> cmd;
    if (cmd == 1) {
      int k;
      char x;
      cin >> k >> x;
      k--;
      S[k] = x - 'a';
      update(k - 2), update(k - 1), update(k);
    } else {
      int l, r;
      cin >> l >> r >> a;
      for (int i = 0; i < 3; i++) a[i] -= 'a';
      --l;
      cout << query(l, r) << "\n";
    }
  }
#ifdef NyaanLocal
  cerr << timer() << endl;
#endif
}
0