結果

問題 No.3122 Median of Medians of Division
ユーザー shibh308
提出日時 2025-04-20 05:35:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,533 bytes
コンパイル時間 2,596 ms
コンパイル使用メモリ 215,584 KB
実行使用メモリ 124,516 KB
最終ジャッジ日時 2025-04-20 05:35:33
合計ジャッジ時間 11,352 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Fenwick2D {
    int M;
    vector<vector<int>> ys;
    vector<vector<int>> bit;
    Fenwick2D(int _M): M(_M), ys(_M+1) {}
    // register (value idx, position) for structure building
    void fake_update(int v, int pos) {
        for(int i = v; i <= M; i += i & -i) {
            ys[i].push_back(pos);
        }
    }
    // initialize internal BIT arrays after all fake_update calls
    void init() {
        bit.resize(M+1);
        for(int i = 1; i <= M; i++) {
            auto &v = ys[i];
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            bit[i].assign(v.size()+1, 0);
        }
    }
    // point update: add delta at (value idx = v, position = pos)
    void update(int v, int pos, int delta) {
        for(int i = v; i <= M; i += i & -i) {
            int idx = int(lower_bound(ys[i].begin(), ys[i].end(), pos) - ys[i].begin()) + 1;
            for(int j = idx; j < (int)bit[i].size(); j += j & -j) {
                bit[i][j] += delta;
            }
        }
    }
    // prefix sum for values <= v, positions <= pos
    int query(int v, int pos) const {
        int res = 0;
        for(int i = v; i > 0; i -= i & -i) {
            int idx = int(upper_bound(ys[i].begin(), ys[i].end(), pos) - ys[i].begin());
            for(int j = idx; j > 0; j -= j & -j) {
                res += bit[i][j];
            }
        }
        return res;
    }
    // sum over values in [v_lo, v_hi], positions in [l, r]
    int range_query(int v_lo, int v_hi, int l, int r) const {
        if(v_lo > v_hi || l > r) return 0;
        int a = query(v_hi, r) - query(v_hi, l - 1);
        int b = query(v_lo - 1, r) - query(v_lo - 1, l - 1);
        return a - b;
    }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N+2);
    for(int i = 1; i <= N; i++) cin >> A[i];

    struct Query { int type, i, x, l, r; };
    vector<Query> queries(Q);

    // collect all values for compression and per-position possible values
    vector<int> all_vals;
    all_vals.reserve(N + Q + 5);
    vector<vector<int>> pos_vals(N+2);

    for(int i = 1; i <= N; i++) {
        pos_vals[i].push_back(A[i]);
        all_vals.push_back(A[i]);
    }

    for(int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        queries[qi].type = t;
        if(t == 1) {
            cin >> queries[qi].i >> queries[qi].x;
            all_vals.push_back(queries[qi].x);
            pos_vals[queries[qi].i].push_back(queries[qi].x);
        } else {
            cin >> queries[qi].l >> queries[qi].r;
        }
    }

    // compress all values
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    int M = all_vals.size();
    auto comp = [&](int x) {
        return int(lower_bound(all_vals.begin(), all_vals.end(), x) - all_vals.begin()) + 1;
    };

    // build Fenwick2D structure
    Fenwick2D fw(M);
    // fake updates for element events
    for(int i = 1; i <= N; i++) {
        auto &pv = pos_vals[i];
        sort(pv.begin(), pv.end());
        pv.erase(unique(pv.begin(), pv.end()), pv.end());
        for(int v : pv) {
            fw.fake_update(comp(v), i);
        }
    }
    // fake updates for pair events (i, i+1)
    for(int i = 1; i < N; i++) {
        vector<int> uv = pos_vals[i];
        uv.insert(uv.end(), pos_vals[i+1].begin(), pos_vals[i+1].end());
        sort(uv.begin(), uv.end());
        uv.erase(unique(uv.begin(), uv.end()), uv.end());
        for(int v : uv) {
            fw.fake_update(comp(v), i);
        }
    }
    fw.init();

    // initial population of weights
    // element weight = +2
    for(int i = 1; i <= N; i++) {
        fw.update(comp(A[i]), i, +2);
    }
    // pair weight = +1
    for(int i = 1; i < N; i++) {
        int pv = max(A[i], A[i+1]);
        fw.update(comp(pv), i, +1);
    }

    // process queries
    for(auto &q : queries) {
        if(q.type == 1) {
            int idx = q.i;
            int old = A[idx];
            int neu = q.x;
            // element update
            fw.update(comp(old), idx, -2);
            fw.update(comp(neu), idx, +2);
            // pair (idx-1, idx)
            if(idx > 1) {
                int oldp = max(A[idx-1], old);
                int newp = max(A[idx-1], neu);
                fw.update(comp(oldp), idx-1, -1);
                fw.update(comp(newp), idx-1, +1);
            }
            // pair (idx, idx+1)
            if(idx < N) {
                int oldp = max(old, A[idx+1]);
                int newp = max(neu, A[idx+1]);
                fw.update(comp(oldp), idx, -1);
                fw.update(comp(newp), idx, +1);
            }
            A[idx] = neu;
        } else {
            int l = q.l, r = q.r;
            int len = r - l + 1;
            // total weight in [1..M] values, positions [l..r]
            int total = fw.range_query(1, M, l, r);
            // binary search on value-axis
            int lo = 1, hi = M, ans_idx = 1;
            while(lo <= hi) {
                int mid = (lo + hi) >> 1;
                int low = fw.range_query(1, mid-1, l, r);
                int w = total - low;
                if(w > len) {
                    ans_idx = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            cout << all_vals[ans_idx-2] << '\n';
        }
    }
    return 0;
}
0