結果

問題 No.3239 Omnibus
コンテスト
ユーザー ルビサファせだい
提出日時 2025-08-21 12:47:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,265 bytes
コンパイル時間 4,770 ms
コンパイル使用メモリ 280,460 KB
実行使用メモリ 92,620 KB
最終ジャッジ日時 2025-08-21 12:48:14
合計ジャッジ時間 30,300 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 6 RE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = 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){ return {a.i_sum + b.i_sum, a.cnt_sum + b.cnt_sum}; }
Node e(){ return {0, 0}; }

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{
                ll l = event.l;
                ll R = event.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;
}
0