結果
問題 |
No.3239 Omnibus
|
ユーザー |
|
提出日時 | 2025-08-16 04:17:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 352 ms / 10,000 ms |
コード長 | 2,287 bytes |
コンパイル時間 | 2,056 ms |
コンパイル使用メモリ | 203,468 KB |
実行使用メモリ | 44,232 KB |
最終ジャッジ日時 | 2025-08-16 04:17:33 |
合計ジャッジ時間 | 10,961 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define BL 512 #define SB (BL - 1) int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; string s; cin >> s; constexpr int r = 26 * 26 * 26; const int bsz = (n + BL - 1) / BL; vector<array<int, r>> seg(bsz); vector<array<short,r>> cnt(bsz); vector<short> vec(n); auto add = [&](int p, int d){ int hs = vec[p]; if(d == 1){ seg[p / BL][hs] += p - (p / BL * BL) + 1; cnt[p / BL][hs]++; }else{ seg[p / BL][hs] -= p - (p / BL * BL) + 1; cnt[p / BL][hs]--; } }; short hs = (s[0] - 'a') * 26 + (s[1] - 'a'); for(int i = 0; i + 3 <= n; i++){ hs *= (short)(26); hs += (short)(s[i + 2] - 'a'); vec[i] = hs; add(i, 1); hs -= (short)(676 * (s[i] - 'a')); } while(q--){ int cmd; cin >> cmd; if(cmd == 1){ int p; char x; cin >> p >> x; p--; short d = x - s[p]; s[p] = x; if(p + 3 <= n){ add(p, -1); vec[p] += d * (short)(676); add(p, 1); } if(1 <= p && p + 2 <= n){ add(p - 1, -1); vec[p - 1] += d * (short)(26); add(p - 1, 1); } if(2 <= p){ add(p - 2, -1); vec[p - 2] += d; add(p - 2, 1); } }else{ int l, r; char c0, c1, c2; ll ans = 0; cin >> l >> r >> c0 >> c1 >> c2; short hs = (((c0 - 'a') * 26) + (c1 - 'a')) * 26 + c2 - 'a'; l--, r -= 2; int cur = l; while(cur < r && (cur & SB)){ if(hs == vec[cur]) ans += cur - l + 1; cur++; } while(cur + BL <= r){ ans += seg[cur / BL][hs] + cnt[cur / BL][hs] * (ll)(cur - l); cur += BL; } while(cur < r){ if(hs == vec[cur]) ans += cur - l + 1; cur++; } cout << ans << '\n'; } } }