結果

問題 No.3122 Median of Medians of Division
ユーザー shibh308
提出日時 2025-04-20 05:54:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,805 bytes
コンパイル時間 3,088 ms
コンパイル使用メモリ 212,328 KB
実行使用メモリ 125,608 KB
最終ジャッジ日時 2025-04-20 05:54:46
合計ジャッジ時間 11,462 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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) {}
    // build-listへの登録 (pos: 0-indexed)
    void fake_update(int v, int pos) {
        for(int i = v; i <= M; i += i & -i)
            ys[i].push_back(pos);
    }
    // init: ysをソート一意化し、bitを構築
    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);
        }
    }
    // 点加算: (value idx=v, pos: 0-indexed位置)
    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: 値軸<=v, positions<=pos (0-indexed)
    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;
    }
    // value in [v_lo,v_hi], positions in [l,r] (both 0-indexed inclusive)
    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) - (l > 0 ? query(v_hi, l-1) : 0);
        int b = query(v_lo-1, r) - (l > 0 ? query(v_lo-1, l-1) : 0);
        return a - b;
    }
};

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

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

    struct Query { int type, i, x, l, r; };
    vector<Query> queries(Q);
    vector<int> all_vals; all_vals.reserve(N + Q);
    vector<vector<int>> pos_vals(N);

    for(int i = 0; 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){
            int idx, x; cin >> idx >> x;
            idx--;  // 0-indexedに
            queries[qi].i = idx;
            queries[qi].x = x;
            pos_vals[idx].push_back(x);
            all_vals.push_back(x);
        } else {
            int l, r; cin >> l >> r;
            l--; r--;
            queries[qi].l = l;
            queries[qi].r = r;
        }
    }

    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;
    };

    Fenwick2D fw(M);
    // elementイベント登録 (pos 0-indexed)
    for(int i = 0; i < N; i++){
        for(int v: pos_vals[i]) fw.fake_update(comp(v), i);
    }
    // 隣接ペアイベント登録 (pos of pair = left idx)
    for(int i = 0; i < N-1; i++){
        for(int v: pos_vals[i])   fw.fake_update(comp(v), i);
        for(int v: pos_vals[i+1]) fw.fake_update(comp(v), i);
    }
    fw.init();

    // 初期重み: element=+2, pair=+1
    for(int i = 0; i < N; i++) fw.update(comp(A[i]), i, +2);
    for(int i = 0; i < N-1; i++) fw.update(comp(max(A[i], A[i+1])), i, +1);

    for(auto &q: queries){
        if(q.type == 1){
            int idx = q.i, old = A[idx], neu = q.x;
            // element更新
            fw.update(comp(old), idx, -2);
            fw.update(comp(neu), idx, +2);
            // 左ペア
            if(idx > 0){
                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);
            }
            // 右ペア
            if(idx < N-1){
                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;
            int total = fw.range_query(1, M, l, r);
            int low = 0, high = M;
            while(high - low > 1){
                int mid = (low + high) >> 1;
                int less_cnt = fw.range_query(1, mid, l, r);
                int w = total - less_cnt;
                if(w > len) low = mid;
                else high = mid;
            }
            cout << all_vals[low - 1] << '\n';
        }
    }
    return 0;
}
0