結果

問題 No.3122 Median of Medians of Division
ユーザー keymoon
提出日時 2025-04-19 21:42:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,974 ms / 2,000 ms
コード長 5,834 bytes
コンパイル時間 4,317 ms
コンパイル使用メモリ 329,408 KB
実行使用メモリ 74,168 KB
最終ジャッジ日時 2025-04-19 21:43:27
合計ジャッジ時間 67,510 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")

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

/* ---------- 二段 Fenwick  ---------- */
struct BIT2 {
    int n;
    vector<vector<int>> coord;          // 各ノードに載る値(圧縮済)
    vector<vector<int>> bit;            // 内側 Fenwick

    BIT2(int N = 0) : n(N), coord(N + 1) {}

    // 構築：add_coord で全候補値を登録したあと build()
    void add_coord(int idx, int val) {
        for (int i = idx; i <= n; i += i & -i) coord[i].push_back(val);
    }
    void build() {
        for (int i = 1; i <= n; ++i) {
            auto &v = coord[i];
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            bit.emplace_back(v.size() + 1, 0);   // 1-indexed
        }
    }
    /* 内側 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;
    }
    int pos_in(int i, int val) const {           // < val の個数 ⇒ lower_bound
        return lower_bound(coord[i].begin(), coord[i].end(), val) - coord[i].begin();
    }
    /* 1点加算 / 区間個数(< val) */
    void add(int idx, int val, int delta) {
        for (int i = idx; i <= n; i += i & -i) {
            int p = lower_bound(coord[i].begin(), coord[i].end(), val) - coord[i].begin() + 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) {
            int p = pos_in(i, val);
            res += fen_sum(bit[i - 1], p);
        }
        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<long long> all;
    for (int i = 1; i <= N; ++i) all.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);
            all.push_back(x);
        } else {
            int l, r; cin >> l >> r;
            queries.emplace_back(tp, l, r);
        }
    }

    /* ---- 座標圧縮 ---- */
    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()); };

    /* ---- 隣接 min 配列 D ---- */
    int M = max(1, N - 1);
    vector<vector<long long>> cands(M + 2);
    auto addDcand = [&](int dIdx, long long v) {
        if (dIdx < 1 || dIdx > M) return;
        cands[dIdx].push_back(v);
    };

    vector<long long> tmpA = A;  // 初期状態をコピー
    // 初期の隣接ペア
    for (int i = 1; i <= M; ++i) {
        long long v = min(tmpA[i], tmpA[i + 1]);
        addDcand(i, v);
    }
    // クエリを先読みしているので、ここで tmpA を順に更新しながら
    for (auto [tp,p1,p2] : queries) {
        if (tp == 1) {
            int i = p1;
            long long x = p2;
            // 更新前の tmpA に対して「この更新で変わる隣接ペアの min」を追加
            if (i - 1 >= 1) addDcand(i - 1, min(tmpA[i - 1], x));
            if (i <= M)     addDcand(i,     min(x, tmpA[i + 1]));
            // そして tmpA を実際に更新
            tmpA[i] = x;
        }
    }
    BIT2 bit(M);
    for (int i = 1; i <= M; ++i)
        for (auto v : cands[i]) 
            bit.add_coord(i, idx(v));

    bit.build();

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

    auto works = [&](int l, int r, int id) -> bool {
        long long vRaw = all[id];
        int len = r - l + 1;

        int lowPair = bit.range_less(l, r - 1, id);

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

        return 0 > (lowPair - len) + startLow + endLow;
    };

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

            /* 隣接 D の更新 */
            auto updD = [&](int dIdx) {
                if (dIdx < 1 || dIdx > M) return;
                bit.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);
                bit.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