結果
問題 |
No.3239 Omnibus
|
ユーザー |
|
提出日時 | 2025-08-21 12:45:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,991 bytes |
コンパイル時間 | 4,521 ms |
コンパイル使用メモリ | 280,336 KB |
実行使用メモリ | 92,616 KB |
最終ジャッジ日時 | 2025-08-21 12:45:50 |
合計ジャッジ時間 | 27,723 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 6 RE * 26 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using ull = unsigned long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; ll ll_min = numeric_limits<ll>::min(); ll ll_max = numeric_limits<ll>::max(); ll ALPHABET_N = 26; static const ll INF = ll_max / 10; #define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++) #define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++) #define all(a) a.begin(), a.end() using namespace atcoder; struct Node { ll i_sum = 0; ll cnt_sum = 0; }; Node op(Node a, Node b) { Node res; res.i_sum = a.i_sum + b.i_sum; res.cnt_sum = a.cnt_sum + b.cnt_sum; return res; } Node e() { Node res; res.i_sum = 0; res.cnt_sum = 0; return res; } enum EventType { ADD, REMOVE, QUERY }; struct Event { ll t; EventType type; ll idx = -1; ll l = -1; ll r = -1; }; int main() { ios::sync_with_stdio(false); cin.tie(0); ll n, q; cin >> n >> q; string s; cin >> s; vector<tuple<ll, ll, ll, string>> queries(q); unordered_map<string, vector<Event>> ump; rep(i, q) { ll t; cin >> t; if (t == 1) { ll k; string x; cin >> k >> x; queries[i] = {t, k - 1, -1, x}; } else { ll l, r; string a; cin >> l >> r >> a; queries[i] = {t, l - 1, r, a}; ump[a].push_back({i, QUERY, -1, l - 1, r}); } } rep(i, n - 2) { string str = s.substr(i, 3); if (ump.find(str) == ump.end()) continue; ump[str].push_back({-1, ADD, i}); ump[str].push_back({q, REMOVE, i}); } rep(i, q) { auto [t, a, b, c] = queries[i]; if (t == 1) { ll idx = a; char x = c[0]; for (ll si = max(0LL, idx - 2); si <= min(n - 3, idx); si++) { string str = s.substr(si, 3); if (ump.find(str) == ump.end()) continue; ump[str].push_back({i, REMOVE, si}); } s[idx] = x; for (ll si = max(0LL, idx - 2); si <= min(n - 3, idx); si++) { string str = s.substr(si, 3); if (ump.find(str) == ump.end()) continue; ump[str].push_back({i, ADD, si}); } } } for (auto &[key, events] : ump) { sort(all(events), [](const Event &a, const Event &b) { return a.t < b.t; }); } segtree<Node, op, e> seg(n - 2); vector<pair<ll, ll>> t_ans; for (auto &[key, events] : ump) { for (const auto &event : events) { if (event.type == ADD) { seg.set(event.idx, {event.idx + 1, 1}); } else if (event.type == REMOVE) { seg.set(event.idx, {0, 0}); } else if (event.type == QUERY) { ll l = event.l, r = event.r; ll R = r - 2; if (l <= R) { Node res = seg.prod(l, R + 1); ll ans = res.i_sum - (l * res.cnt_sum); t_ans.push_back({event.t, ans}); } else { t_ans.push_back({event.t, 0}); } } } } sort(all(t_ans), [](const pair<ll, ll> &a, const pair<ll, ll> &b) { return a.first < b.first; }); rep(i, t_ans.size()) { cout << t_ans[i].second << "\n"; } return 0; }