結果
問題 |
No.3239 Omnibus
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:19:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,888 ms / 10,000 ms |
コード長 | 1,387 bytes |
コンパイル時間 | 3,811 ms |
コンパイル使用メモリ | 253,684 KB |
実行使用メモリ | 116,436 KB |
最終ジャッジ日時 | 2025-08-15 22:20:29 |
合計ジャッジ時間 | 53,107 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 1000000000000000001LL long long cs[500][26*26*26],ss[500][26*26*26]; int B = 500; string s; short get(string t){ short res = 0; rep(i,3){ res *= 26; res += t[i] - 'a'; } return res; } void deal(int pos,int add){ if(pos < 2)return; if(pos >= s.size())return; string t = s.substr(pos-2,3); short cur = get(t); cs[pos/B][cur] += add; ss[pos/B][cur] += pos * add; } int main(){ int n,q; cin>>n>>q; cin>>s; rep(i,n){ deal(i,1); } rep(_,q){ int t; cin>>t; if(t==1){ int i; char c; cin>>i>>c; i--; rep(j,3){ deal(i+j,-1); } s[i] = c; rep(j,3){ deal(i+j,1); } } else{ int l,r; cin>>l>>r; l--; string a; cin>>a; if(r-l < 3){ cout<<0<<endl; continue; } l += 2; long long tl = l,tr = r; long long ans = 0,c = 0; short ta = get(a); while(l<r && l%B != 0){ if(a == s.substr(l-2,3)){ ans += l; c++; } l++; } while(l+B < r){ ans += ss[l/B][ta]; c += cs[l/B][ta]; l += B; } while(l<r){ if(a == s.substr(l-2,3)){ ans += l; c++; } l++; } ans -= (tl-1) * c; cout<<ans<<endl; } } }