結果
問題 | No.2554 MMA文字列2 (Query Version) |
ユーザー |
![]() |
提出日時 | 2023-11-25 14:32:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,149 ms / 5,000 ms |
コード長 | 1,780 bytes |
コンパイル時間 | 4,103 ms |
コンパイル使用メモリ | 280,164 KB |
実行使用メモリ | 165,588 KB |
最終ジャッジ日時 | 2024-09-26 10:44:38 |
合計ジャッジ時間 | 33,698 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;struct S {ll v01, v02, v03, v12, v13, v23;};S op(const S& x, const S& y) {return S{x.v01 + y.v01,x.v02 + x.v01 * y.v12 + y.v02,x.v03 + x.v02 * y.v23 + x.v01 * y.v13 + y.v03,x.v12 + y.v12,x.v13 + x.v12 * y.v23 + y.v13,x.v23 + y.v23};}S e() {return S{0, 0, 0, 0, 0, 0};}} int main() {ios::sync_with_stdio(false);cin.tie(0);int n;string s;cin >> n >> s;S match{1, 0, 0, 1, 0, 0}, unmatch{0, 0, 0, 0, 0, 1};vector<segtree<S, op, e>> seg;rep(c, 26) {vector<S> init(n);rep(i, n) {init[i] = s[i] - 'A' == c ? match : unmatch;}seg.emplace_back(init);}int q;cin >> q;while (q--) {int op;cin >> op;if (op == 1) {int x;char c;cin >> x >> c;x--;seg[s[x] - 'A'].set(x, unmatch);s[x] = c;seg[s[x] - 'A'].set(x, match);} else {int l, r;cin >> l >> r;l--;ll ans = 0;rep(c, 26) ans += seg[c].prod(l, r).v03;cout << ans << '\n';}}}