結果

問題 No.3122 Median of Medians of Division
ユーザー keymoon
提出日時 2025-04-19 20:43:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,799 bytes
コンパイル時間 5,284 ms
コンパイル使用メモリ 300,228 KB
実行使用メモリ 814,504 KB
最終ジャッジ日時 2025-04-19 20:43:43
合計ジャッジ時間 9,085 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/* ---------- 二段 Fenwick  ---------- */
struct BIT2 {
    int n;
    vector<vector<int>> bit;            // 内側 Fenwick

    BIT2(int N, int M) : n(N), bit(n, vector<int>(M + 1, 0)) {}

    /* 内側 Fenwick */
    static void fen_add(vector<int>& f, int idx, int delta) {
        for (int i = idx; i < (int)f.size(); i += i & -i) f[i] += delta;
    }
    static int fen_sum(const vector<int>& f, int idx) {
        int s = 0;
        for (int i = idx; i > 0; i -= i & -i) s += f[i];
        return s;
    }
    /* 1点加算 / 区間個数(< val) */
    void add(int idx, int val, int delta) {
        for (int i = idx; i <= n; i += i & -i) {
            int p = val + 1;
            fen_add(bit[i - 1], p, delta);       // bit は 0-origin vector
        }
    }
    int prefix_less(int idx, int val) const {    // [1,idx] で < val
        int res = 0;
        for (int i = idx; i > 0; i -= i & -i) {
            res += fen_sum(bit[i - 1], val);
        }
        return res;
    }
    int range_less(int l, int r, int val) const {   // [l,r]
        if (l > r) return 0;
        return prefix_less(r, val) - prefix_less(l - 1, 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用 ---- */
    BIT2 bitA(N, all.size());

    /* ---- 隣接 min 配列 D ---- */
    int M = max(1, N - 1);
    BIT2 bitD(M, all.size());

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

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

        int lowCnt = bitA.range_less(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_less(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.add(i, idx(A[i]), -1);
            bitA.add(i, idx(x),   +1);

            /* 隣接 D の更新 */
            auto updD = [&](int dIdx) {
                if (dIdx < 1 || dIdx > M) return;
                bitD.add(dIdx, Dval[dIdx], -1);
                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]);
                Dval[dIdx] = idx(newRaw);
                bitD.add(dIdx, Dval[dIdx], +1);
            };
            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