結果
問題 | No.2992 Range ABCD String Query |
ユーザー |
![]() |
提出日時 | 2024-12-17 01:43:11 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,363 ms / 6,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 2,964 ms |
コンパイル使用メモリ | 218,868 KB |
実行使用メモリ | 190,260 KB |
最終ジャッジ日時 | 2024-12-17 01:45:05 |
合計ジャッジ時間 | 104,538 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;void fast_io() {ios::sync_with_stdio(false);std::cin.tie(nullptr);}#include <atcoder/segtree>using namespace atcoder;using S = vector<vector<int>>;S op(S l, S r) {S res(4, vector<int>(4, 1e9));for (int i = 0; i < 4; i++) {for (int j = i; j < 4; j++) {for (int k = j; k < 4; k++) {res[i][k] = min(res[i][k], l[i][j] + r[j][k]);}}}return res;}S e() { return S(4, vector<int>(4)); }int main() {fast_io();int n, q;cin >> n >> q;string s;cin >> s;vector<S> seg_data(n);for (int i = 0; i < n; i++) {seg_data[i] = S(4, vector<int>(4, 1));for (int j = 0; j <= s[i] - 'A'; j++) {for (int k = s[i] - 'A'; k < 4; k++) {seg_data[i][j][k] = 0;}}}segtree<S, op, e> seg(seg_data);for (; q--;) {int com;cin >> com;if (com == 1) {int x;char c;cin >> x >> c;x--;S d(4, vector<int>(4, 1));for (int i = 0; i <= c - 'A'; i++) {for (int j = c - 'A'; j < 4; j++) {d[i][j] = 0;}}seg.set(x, d);} else {int l, r;cin >> l >> r;auto res = seg.prod(l - 1, r);cout << res[0][3] << "\n";}}}