結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー keymoon
提出日時 2025-04-19 21:06:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 5,775 bytes
コンパイル時間 6,152 ms
コンパイル使用メモリ 346,888 KB
実行使用メモリ 658,968 KB
最終ジャッジ日時 2025-04-19 21:06:55
合計ジャッジ時間 13,335 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// 多重集合を実現するために (value, index) をキーにする
using pii  = pair<int,int>;
using ost  = tree<pii, null_type, less<pii>,
                  rb_tree_tag, tree_order_statistics_node_update>;

struct SegTree {
    int n;                   // 要素数
    vector<ost> seg;         // 4n 個のノード

    explicit SegTree(const vector<int>& a) : n((int)a.size()), seg(4*n) {
        build(1, 0, n-1, a);
    }

    // i 番目を val に変更
    void set_val(int i, int prev, int val) {
        update(1, 0, n-1, i, prev, val);
    }

    // 区間 [l,r] で A[k] < val となる k の個数
    int range_count_lt(int l, int r, int val) const {
        return query(1, 0, n-1, l, r, val);
    }

private:
    // --- 内部実装 -----------------------------------------------------------

    void build(int v, int tl, int tr, const vector<int>& a) {
        if (tl == tr) {
            seg[v].insert({a[tl], tl});
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v<<1, tl, tm, a);
        build(v<<1|1, tm+1, tr, a);
        // 子の要素をまとめて現在ノードへ
        for (const auto& elem : seg[v<<1]) {
            seg[v].insert(elem);
        }
        for (const auto& elem : seg[v<<1|1]) {
            seg[v].insert(elem);
        }
    }

    void update(int v, int tl, int tr,
                int pos, int oldVal, int newVal) {
        seg[v].erase({oldVal, pos});
        seg[v].insert({newVal, pos});
        if (tl == tr) return;
        int tm = (tl + tr) >> 1;
        if (pos <= tm) update(v<<1,   tl, tm, pos, oldVal, newVal);
        else           update(v<<1|1, tm+1, tr, pos, oldVal, newVal);
    }

    int query(int v, int tl, int tr,
              int l, int r, int val) const {
        if (r < tl || tr < l) return 0;
        if (l <= tl && tr <= r) {
            // ost::order_of_key:  < val の要素数を返す
            return (int)seg[v].order_of_key({val, -1});
        }
        int tm = (tl + tr) >> 1;
        return query(v<<1,   tl, tm, l, r, val) +
               query(v<<1|1, tm+1, tr, l, r, val);
    }
};

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

    vector<long long> A(N + 2);      // 1-indexed, 番兵付き
    for (int i = 1; i <= N; ++i) cin >> A[i];

    /* ---- 全値収集 ---- */
    vector<vector<long long>> candA(N + 2);      // 位置ごとの候補値
    for (int i = 1; i <= N; ++i) candA[i].push_back(A[i]);

    vector<tuple<int,int,long long>> queries;    // (type, p1, p2/x)
    for (int t = 0; t < Q; ++t) {
        int tp; cin >> tp;
        if (tp == 1) {
            int i; long long x; cin >> i >> x;
            queries.emplace_back(tp, i, x);
            candA[i].push_back(x);
        } else {
            int l, r; cin >> l >> r;
            queries.emplace_back(tp, l, r);
        }
    }

    /* ---- 座標圧縮 ---- */
    vector<long long> all;
    for (int i = 1; i <= N; ++i) {
        for (auto v : candA[i]) all.push_back(v);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    auto idx = [&](long long x) { return int(lower_bound(all.begin(), all.end(), x) - all.begin()); };

    /* ---- BIT 構築：A用 ---- */
    vector<int> compressedA(N + 2);
    for (int i = 1; i <= N; ++i) compressedA[i] = idx(A[i]);

    /* ---- 隣接 min 配列 D ---- */
    int M = max(1, N - 1);

    /* ---- 初期値登録 ---- */
    vector<int> Dval(M + 2, -1);
    for (int i = 1; i <= M; ++i) {
        Dval[i] = idx(min(A[i], A[i + 1]));
    }

    SegTree bitA(compressedA);
    SegTree bitD(Dval);


    /* ---- 2 種クエリ処理 ---- */
    auto works = [&](int l, int r, int id) -> bool {
        long long vRaw = all[id];
        int len = r - l + 1;

        int lowCnt = bitA.range_count_lt(l, r, id);          // A_i < v
        int high = len - lowCnt;
        if (high == 0) return false;

        int pairCnt = max(0, r - l);
        int lowPair = bitD.range_count_lt(l, r - 1, id);     // D_i < v
        int adjHigh = pairCnt - lowPair;                 // both ≥ v
        int groups = high - adjHigh;

        int startLow = (A[l] < vRaw);
        int endLow   = (A[r] < vRaw);

        long long lowBlocks = groups - 1 + startLow + endLow;
        return high > lowBlocks;
    };

    ostringstream out;
    for (auto [tp,p1,p2] : queries) {
        if (tp == 1) {             /* 更新 */
            int i = p1; long long x = p2;
            if (A[i] == x) continue;

            /* A の BIT 更新 */
            bitA.set_val(i, idx(A[i]), idx(x));

            /* 隣接 D の更新 */
            auto updD = [&](int dIdx) {
                if (dIdx < 1 || dIdx > M) return;
                long long newRaw = min(A[dIdx], A[dIdx+1]);
                if (dIdx == i - 1) newRaw = min(A[dIdx], x);
                if (dIdx == i)     newRaw = min(x, A[dIdx+1]);
                bitD.set_val(dIdx, Dval[dIdx], idx(newRaw));
                Dval[dIdx] = idx(newRaw);
            };
            updD(i - 1);
            updD(i);

            A[i] = x;
        } else {                  /* 質問 */
            int l = p1, r = (int)p2;
            /* 長さ 1 はそのまま */
            if (l == r) { out << A[l] << '\n'; continue; }

            int lo = 0, hi = (int)all.size() - 1, ans = all[0];
            while (lo <= hi) {
                int mid = (lo + hi) >> 1;
                if (works(l, r, mid)) { ans = all[mid]; lo = mid + 1; }
                else hi = mid - 1;
            }
            out << ans << '\n';
        }
    }
    cout << out.str();
    return 0;
}
0