結果

問題 No.3122 Median of Medians of Division
ユーザー Takao Obi
提出日時 2025-04-19 14:37:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,214 bytes
コンパイル時間 2,335 ms
コンパイル使用メモリ 208,684 KB
実行使用メモリ 145,700 KB
最終ジャッジ日時 2025-04-19 14:39:00
合計ジャッジ時間 27,750 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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 t, i, x, l, r; };
    vector<Query> qs(Q);
    vector<int> vals;
    vals.reserve(N + Q);
    for(int i = 0; i < N; i++) vals.push_back(A[i]);
    for(int qi = 0; qi < Q; qi++){
        int t;
        cin >> t;
        qs[qi].t = t;
        if(t == 1){
            cin >> qs[qi].i >> qs[qi].x;
            --qs[qi].i;
            vals.push_back(qs[qi].x);
        } else {
            cin >> qs[qi].l >> qs[qi].r;
            --qs[qi].l; --qs[qi].r;
        }
    }
    // compress values
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int M = vals.size();
    auto getId = [&](int x){ return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); };

    // build segtree size
    int S = 1;
    while(S < M) S <<= 1;
    int SZ = 2 * S;
    
    vector<vector<int>> pos(SZ);
    // collect positions
    for(int i = 0; i < N; i++){
        int v = getId(A[i]);
        pos[S + v].push_back(i);
    }
    for(int qi = 0; qi < Q; qi++){
        if(qs[qi].t == 1){
            int v = getId(qs[qi].x);
            pos[S + v].push_back(qs[qi].i);
        }
    }
    // build internal pos by merging
    for(int i = S-1; i >= 1; i--){
        auto &L = pos[2*i];
        auto &R = pos[2*i+1];
        auto &P = pos[i];
        P.reserve(L.size() + R.size());
        merge(L.begin(), L.end(), R.begin(), R.end(), back_inserter(P));
        P.erase(unique(P.begin(), P.end()), P.end());
    }
    // BIT arrays
    vector<vector<int>> bit(SZ);
    for(int i = 1; i < SZ; i++){
        bit[i].assign(pos[i].size()+1, 0);
    }
    
    auto bitUpd = [&](vector<int> &b, int idx, int d){
        int n = b.size();
        for(int i = idx; i < n; i += i & -i) b[i] += d;
    };
    auto bitSum = [&](const vector<int> &b, int idx){ int s = 0; for(int i = idx; i > 0; i -= i & -i) s += b[i]; return s; };

    // initial insert
    for(int i = 0; i < N; i++){
        int v = getId(A[i]);
        int node = S + v;
        while(node){
            auto &P = pos[node];
            int p = int(lower_bound(P.begin(), P.end(), i) - P.begin()) + 1;
            bitUpd(bit[node], p, 1);
            node >>= 1;
        }
    }

    // process queries
    for(auto &q: qs){
        if(q.t == 1){
            int idx = q.i;
            int oldv = getId(A[idx]);
            int newv = getId(q.x);
            if(oldv == newv) { A[idx] = q.x; continue; }
            int node = S + oldv;
            while(node){
                auto &P = pos[node];
                int p = int(lower_bound(P.begin(), P.end(), idx) - P.begin()) + 1;
                bitUpd(bit[node], p, -1);
                node >>= 1;
            }
            node = S + newv;
            while(node){
                auto &P = pos[node];
                int p = int(lower_bound(P.begin(), P.end(), idx) - P.begin()) + 1;
                bitUpd(bit[node], p, +1);
                node >>= 1;
            }
            A[idx] = q.x;
        } else {
            int l = q.l, r = q.r;
            int len = r - l + 1;
            int k = (len + 1) >> 1; // lower median
            int node = 1;
            int lo = 0, hi = S - 1;
            while(node < S){
                int mid = (lo + hi) >> 1;
                // count in left child
                int left = 2*node;
                auto &P = pos[left];
                int li = int(lower_bound(P.begin(), P.end(), l) - P.begin()) + 1;
                int ri = int(upper_bound(P.begin(), P.end(), r) - P.begin());
                int cnt = 0;
                if(ri >= li) cnt = bitSum(bit[left], ri) - bitSum(bit[left], li-1);
                if(cnt >= k){
                    node = left;
                    hi = mid;
                } else {
                    node = left + 1;
                    lo = mid + 1;
                    k -= cnt;
                }
            }
            int vid = node - S;
            cout << vals[vid] << '\n';
        }
    }
    return 0;
}
0