結果

問題 No.3239 Omnibus
ユーザー hitonanode
提出日時 2025-08-15 22:47:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,340 bytes
コンパイル時間 1,584 ms
コンパイル使用メモリ 130,368 KB
実行使用メモリ 21,776 KB
最終ジャッジ日時 2025-08-15 22:48:18
合計ジャッジ時間 10,319 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <ios>
#include <iostream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

template <class T> std::vector<T> sort_unique(std::vector<T> vec) {
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

template <class T> int arglb(const std::vector<T> &v, const T &x) {
    return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}

#include <atcoder/fenwicktree>

constexpr int D = 26;

int Encode(const string &s3) {
    assert(s3.size() == 3);
    int a = s3[0] - 'a';
    int b = s3[1] - 'a';
    int c = s3[2] - 'a';
    return a * D * D + b * D + c;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    string S;
    cin >> N >> Q >> S;

    vector<tuple<int, int, int, string>> queries(Q);
    for (auto &[tp, l, r, a] : queries) {
        cin >> tp;
        if (tp == 1) {
            cin >> l >> a;
            --l;
            r = -1;
        } else if (tp == 2) {
            cin >> l >> r >> a;
            --l;
        } else {
            assert(false);
        }
    }

    vector<vector<int>> w2is(D * D * D);
    REP(i, N - 2) w2is[Encode(S.substr(i, 3))].push_back(i);

    {
        auto T = S;
        for (auto [tp, l, r, a] : queries) {
            if (tp == 1) {
                T[l] = a[0];
                FOR(i, l - 2, l + 1) {
                    if (i >= 0 and i + 2 < N) w2is[Encode(T.substr(i, 3))].push_back(i);
                }
            }
        }
    }
    for (auto &is : w2is) is = sort_unique(is);

    vector<atcoder::fenwick_tree<int>> bit0(D * D * D);
    vector<atcoder::fenwick_tree<long long>> bit1(D * D * D);
    REP(d, D * D * D) {
        bit0[d] = atcoder::fenwick_tree<int>(w2is[d].size());
        bit1[d] = atcoder::fenwick_tree<long long>(w2is[d].size());
    }

    REP(i, N - 2) {
        const auto e = Encode(S.substr(i, 3));
        const int pos = arglb(w2is[e], i);
        bit0[e].add(pos, 1);
        bit1[e].add(pos, i);
    }

    {
        for (auto [tp, l, r, a] : queries) {
            if (tp == 1) {
                FOR(i, l - 2, l + 1) {
                    if (i >= 0 and i + 2 < N) {
                        const int e = Encode(S.substr(i, 3));
                        const int pos = arglb(w2is[e], i);
                        bit0[e].add(pos, -1);
                        bit1[e].add(pos, -i);
                    }
                }
                S[l] = a[0];
                FOR(i, l - 2, l + 1) {
                    if (i >= 0 and i + 2 < N) {
                        const int e = Encode(S.substr(i, 3));
                        const int pos = arglb(w2is[e], i);
                        bit0[e].add(pos, +1);
                        bit1[e].add(pos, +i);
                    }
                }
            } else {
                const int e = Encode(a);
                const int il = arglb(w2is[e], l);
                const int ir = arglb(w2is[e], r - 2);

                long long prod0 = bit0[e].sum(il, ir);
                auto prod1 = bit1[e].sum(il, ir);
                cout << prod1 - prod0 * (l - 1) << '\n';
            }
        }
    }
}
0