結果
問題 | No.2554 MMA文字列2 (Query Version) |
ユーザー |
|
提出日時 | 2023-12-08 19:22:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,642 ms / 5,000 ms |
コード長 | 854 bytes |
コンパイル時間 | 4,656 ms |
コンパイル使用メモリ | 259,132 KB |
最終ジャッジ日時 | 2025-02-18 09:31:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i,n) for (int i=0;i<(int)(n);i++) struct S{ vector<ll> v1,v2,v3; ll sm; S():v1(26,0),v2(26,0),sm(0){} }; S op(S a,S b){ S c; ll smb=0; rep(i,26){ c.v1[i]=a.v1[i]+b.v1[i]; c.v2[i]=a.v2[i]+b.v2[i]; smb+=b.v1[i]; } c.sm=a.sm+b.sm; rep(i,26){ c.v2[i]+=a.v1[i]*(smb-b.v1[i]); c.sm+=a.v1[i]*b.v2[i]; c.sm+=(a.v1[i]-1)*a.v1[i]/2*(smb-b.v1[i]); } return c; } S e(){ return S(); } S mk(char c){ S s; s.v1[c-'A']++; return s; } int main(){ int n,q; string s; cin>>n>>s>>q; atcoder::segtree<S,op,e> seg(n); rep(i,n) seg.set(i,mk(s[i])); rep(i,q){ int t; cin>>t; if(t==1){ int x; char c; cin>>x>>c; x--; seg.set(x,mk(c)); }else{ int l,r; cin>>l>>r; l--; cout<<seg.prod(l,r).sm<<"\n"; } } }