結果
問題 |
No.3239 Omnibus
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:49:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,175 bytes |
コンパイル時間 | 3,184 ms |
コンパイル使用メモリ | 289,268 KB |
実行使用メモリ | 474,240 KB |
最終ジャッジ日時 | 2025-08-15 22:52:11 |
合計ジャッジ時間 | 72,806 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 RE * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/modint> // using namespace atcoder; // using mint = modint998244353; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} constexpr ll INFLL = (1LL << 62), MOD = 998244353; constexpr int INF = (1 << 30); int enc(string s){ assert(s.size()==3); int res = 0, t = 1; rep(i,3) res += (s[i]-'a') * t, t *= 27; return res; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,q; cin >> n >> q; string s; cin >> s; int log = 0; while(n-2>(1<<log)) ++log; vector<map<int,ll>> seg(19863); rep(i,n-2){ int x = enc(s.substr(i,3)), idx = i+(1<<log); while(idx) seg[x][idx] += ((ll)(i+1)<<18) + 1, idx >>= 1; } while(q--){ int t; cin >> t; if(t==1){ int k; char c; cin >> k >> c; --k; for(int i=max(k-2,0);i<=k;++i){ int x = enc(s.substr(i,3)), idx = i+(1<<log); while(idx) seg[x][idx] -= ((ll)(i+1)<<18) + 1, idx >>= 1; } s[k] = c; for(int i=max(k-2,0);i<=k;++i){ int x = enc(s.substr(i,3)), idx = i+(1<<log); while(idx) seg[x][idx] += ((ll)(i+1)<<18) + 1, idx >>= 1; } }else{ int l,r,z; string t; cin >> l >> r >> t; --l; z = l; r -= 2; if(l>r){ cout << "0\n"; continue; } l += 1<<log, r += 1<<log; int x = enc(t); ll tot = 0; while(l<r){ if(l&1) tot += seg[x][l++]; if(r&1) tot += seg[x][--r]; l >>= 1, r >>= 1; } ll cnt = tot & ((1<<18)-1); tot >>= 18; cout << tot-z*cnt << '\n'; } } return 0; }