#1042039 (C++23) No.1951 消えたAGCT(2)

• 問題: No.1951 消えたAGCT(2)
• ユーザー: Jikky1618
• 提出日時: 2025-02-12 00:30:59
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 232 ms / 3,000 ms
• コード長: 8,377 bytes
• コンパイル時間: 3,074 ms
• コンパイル使用メモリ: 284,432 KB
• 実行使用メモリ: 29,276 KB
• 最終ジャッジ日時: 2025-02-12 00:31:09
• 合計ジャッジ時間: 6,230 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 28

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <class S, S (*op)(S, S), S (*e)()>
class SplayTree {
   private:
    struct Node {
        S val, sum;             // 自身の値と部分木全体の集約値
        int size;               // 部分木のサイズ
        bool rev;               // 遅延反転フラグ
        Node *lch, *rch, *par;  // 左子、右子、親へのポインタ

        Node() : val(e()), sum(e()), size(0), rev(false), lch(nullptr), rch(nullptr), par(nullptr) {}
        Node(const S& v) : val(v), sum(v), size(1), rev(false), lch(nullptr), rch(nullptr), par(nullptr) {}
    };

    Node* root;

    inline int size(Node* t) const { return t ? t->size : 0; }
    inline S sum(Node* t) const { return t ? t->sum : e(); }

    // t のサイズ・集約値を左右の子から更新
    inline void push_up(Node* t) {
        if (!t) return;
        t->size = 1;
        t->sum = t->val;
        if (t->lch) {
            t->size += t->lch->size;
            t->sum = op(t->lch->sum, t->sum);
        }
        if (t->rch) {
            t->size += t->rch->size;
            t->sum = op(t->sum, t->rch->sum);
        }
    }

    // 反転フラグが立っていたら子に伝搬し、左右の子を入れ替える
    inline void push_down(Node* t) {
        if (t && t->rev) {
            swap(t->lch, t->rch);
            if (t->lch) t->lch->rev ^= true;
            if (t->rch) t->rch->rev ^= true;
            t->rev = false;
        }
    }

    // x とその親 p を回転する（x を上げる）
    void rotate(Node* x) {
        Node *p = x->par, *g = p->par;
        push_down(p);
        push_down(x);
        if (x == p->lch) {
            p->lch = x->rch;
            if (x->rch) x->rch->par = p;
            x->rch = p;
        } else {
            p->rch = x->lch;
            if (x->lch) x->lch->par = p;
            x->lch = p;
        }
        x->par = g;
        if (g) {
            if (p == g->lch)
                g->lch = x;
            else
                g->rch = x;
        }
        p->par = x;
        push_up(p);
        push_up(x);
    }

    // k 番目 (0 <= t < size) のノードを根に持ってくる
    Node* kth_element(Node* t, int k) {
        while (true) {
            push_down(t);
            int lsize = size(t->lch);
            if (k == lsize) break;
            if (k < lsize) {
                t = t->lch;
            } else if (k > lsize) {
                k -= lsize + 1;
                t = t->rch;
            }
        }
        splay(t);
        return t;
    }

    // x を根に持ってくる
    void splay(Node* x) {
        if (!x) return;
        while (x->par) {
            Node* p = x->par;
            Node* g = p->par;
            if (g) push_down(g);
            push_down(p);
            push_down(x);
            if (!g) {
                rotate(x);
            } else if ((g->lch == p && p->lch == x) || (g->rch == p && p->rch == x)) {
                rotate(p);
                rotate(x);
            } else {
                rotate(x);
                rotate(x);
            }
        }
        root = x;
    }

    // 木 t を先頭 k 個と残りに分割し、ペア {l, t} を返す
    pair<Node*, Node*> split(Node* t, int k) {
        if (!t) return {nullptr, nullptr};
        if (k == 0) return {nullptr, t};
        if (k >= size(t)) return {t, nullptr};
        // t を k 番目のノードが根になるよう splay する
        t = kth_element(t, k);
        Node* l = t->lch;
        l->par = nullptr;
        t->lch = nullptr;
        push_up(t);
        return {l, t};
    }

    // l, r を結合する
    Node* merge(Node* l, Node* r) {
        if (!l) return r;
        if (!r) return l;
        // l の最大要素（右端）を splay する
        l = kth_element(l, size(l) - 1);
        l->rch = r;
        r->par = l;
        push_up(l);
        return l;
    }

    Node* build(const vector<S>& V, int l, int r) {
        if (l >= r) return nullptr;
        int m = (l + r) >> 1;
        Node* t = new Node(V[m]);
        t->lch = build(V, l, m);
        t->rch = build(V, m + 1, r);
        if (t->lch) t->lch->par = t;
        if (t->rch) t->rch->par = t;
        push_up(t);
        return t;
    }

    void delete_all(Node* t) {
        if (!t) return;
        delete_all(t->lch);
        delete_all(t->rch);
        delete t;
    }

   public:
    SplayTree() : root(nullptr) {}
    SplayTree(const vector<S>& V) : root(nullptr) {
        if (!V.empty()) root = build(V, 0, V.size());
    }
    ~SplayTree() { delete_all(root); }

    // get: k (0 <= k < size) 番目の要素の値を返す
    S get(int k) {
        assert(root && 0 <= k && k < root->size);
        return kth_element(root, k)->val;
    }

    // insert: 位置 k に値 v を挿入する
    void insert(int k, S v) {
        assert(0 <= k && k <= size(root));
        Node* newNode = new Node(v);
        if (!root) {
            root = newNode;
            return;
        }
        if (k == 0) {
            root = merge(newNode, root);
        } else if (k == size(root)) {
            root = merge(root, newNode);
        } else {
            auto [L, R] = split(root, k);
            root = merge(merge(L, newNode), R);
        }
    }

    // erase: 位置 k の要素を削除する
    void erase(int k) {
        assert(root && 0 <= k && k < root->size);
        Node* target = kth_element(root, k);
        Node *L = target->lch, *R = target->rch;
        if (L) L->par = nullptr;
        if (R) R->par = nullptr;
        delete target;
        root = merge(L, R);
    }

    // update: 位置 k の値を v に更新する
    void update(int k, S v) {
        assert(root && 0 <= k && k < root->size);
        Node* target = kth_element(root, k);
        target->val = v;
        push_up(target);
    }

    // prod: 区間 [l, r) の要素を op で集約した値を返す
    S prod(int l, int r) {
        assert(0 <= l && r <= size());
        if (l >= r) return e();
        auto [A, BC] = split(root, l);
        auto [B, C] = split(BC, r - l);
        S res = B ? B->sum : e();
        root = merge(A, merge(B, C));
        return res;
    }

    // reverse: 区間 [l, r) の要素を反転する
    void reverse(int l, int r) {
        assert(0 <= l && r <= size());
        if (l >= r) return;
        auto [A, BC] = split(root, l);
        auto [B, C] = split(BC, r - l);
        if (B) B->rev ^= true;
        root = merge(A, merge(B, C));
    }

    // rotate: 区間 [l, r) を m 番目の要素が先頭になるように巡回シフトする
    // 0 <= l < m < r <= size()
    void rotate(int l, int m, int r) {
        assert(0 <= l && l < m && m < r && r <= size());
        auto [A, BC] = split(root, l);
        auto [B, C] = split(BC, r - l);
        auto [B1, B2] = split(B, m - l);  // B = [B1, B2] で、B2 が先頭に来る
        B = merge(B2, B1);
        root = merge(A, merge(B, C));
    }

    bool empty() const { return root == nullptr; }
    int size() const { return size(root); }
    S operator[](int k) { return get(k); }
};

using T = int;
constexpr T e() { return 0; }
T op(T a, T b) { return a + b; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    string S;
    cin >> S;
    constexpr int z = 26;

    // A, B, C, ..., Z を 0, 1, 2, ..., 25 に変換
    vector<int> V(N);
    for (int i = 0; i < N; i++) V[i] = S[i] - 'A';
    SplayTree<T, op, e> st(V);

    // cur := 0 の箇所
    // cnt[c] := 文字 c - cur がいくつあるか
    int cur = 0;
    vector<int> cnt(z);
    for (int i = 0; i < N; i++) cnt[V[i]]++;

    // c mod z
    auto f = [&](int c) -> int { return (c % z + z) % z; };
    int ans = 0;
    while (true) {
        // c1 := A, G, C, T の個数
        int c1 = cnt[f(0 - cur)] + cnt[f(6 - cur)] + cnt[f(2 - cur)] + cnt[f(19 - cur)];
        if (c1 == 0) break;
        // c1 番目の文字 c を削除
        int c = st[c1 - 1];
        st.erase(c1 - 1);
        cnt[c]--;
        // c2 := 文字 c の個数
        int c2 = cnt[c];
        // c2 回, 文字を次の文字に置き換える
        cur = f(cur + c2);
        ans++;
    }

    cout << ans << '\n';
}