結果

問題 No.3122 Median of Medians of Division
ユーザー Takao Obi
提出日時 2025-04-19 14:44:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,854 bytes
コンパイル時間 2,243 ms
コンパイル使用メモリ 207,068 KB
実行使用メモリ 159,976 KB
最終ジャッジ日時 2025-04-19 14:46:27
合計ジャッジ時間 90,503 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 2 RE * 1 TLE * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// BIT of dynamic segment trees for range k-th order statistic
struct Node { int lc, rc; int cnt; };
static const int MAXQ = 200000;
static const int MAXN = 200000;
static const int MAXV = MAXN + MAXQ + 5;
static const int POOL_SIZE = (MAXN + MAXQ) * 32;
static Node pool[POOL_SIZE];
static int pool_ptr = 1; // 0 reserved as null

int new_node(int from = 0) {
    int id = pool_ptr++;
    pool[id] = pool[from];
    return id;
}

int update_node(int node, int L, int R, int pos, int delta) {
    int id = new_node(node);
    pool[id].cnt += delta;
    if (L == R) return id;
    int mid = (L + R) >> 1;
    if (pos <= mid) {
        pool[id].lc = update_node(pool[id].lc, L, mid, pos, delta);
    } else {
        pool[id].rc = update_node(pool[id].rc, mid+1, R, pos, delta);
    }
    return id;
}

int N, Q;
vector<int> vals;
int M;
vector<int> A;
vector<int> bit_roots; // size N+1, 1-indexed

void bit_update(int idx, int pos, int delta) {
    for (int i = idx; i <= N; i += i & -i) {
        bit_roots[i] = update_node(bit_roots[i], 0, M-1, pos, delta);
    }
}

int kth_query(const vector<int> &r_nodes, const vector<int> &l_nodes, int L, int R, int k) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    ll cnt_left = 0;
    for (int x : r_nodes) cnt_left += pool[ pool[x].lc ].cnt;
    for (int x : l_nodes) cnt_left -= pool[ pool[x].lc ].cnt;
    if (k <= cnt_left) {
        vector<int> nr, nl;
        nr.reserve(r_nodes.size()); nl.reserve(l_nodes.size());
        for (int x : r_nodes) nr.push_back(pool[x].lc);
        for (int x : l_nodes) nl.push_back(pool[x].lc);
        return kth_query(nr, nl, L, mid, k);
    } else {
        vector<int> nr, nl;
        nr.reserve(r_nodes.size()); nl.reserve(l_nodes.size());
        for (int x : r_nodes) nr.push_back(pool[x].rc);
        for (int x : l_nodes) nl.push_back(pool[x].rc);
        return kth_query(nr, nl, mid+1, R, k - cnt_left);
    }
}

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

    cin >> N >> Q;
    A.resize(N);
    vals.reserve(N + Q);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        vals.push_back(A[i]);
    }
    struct Qry { int t, i, x, l, r; };
    vector<Qry> qs(Q);
    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 vals
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    M = vals.size();
    auto getId = [&](int v) {
        return int(lower_bound(vals.begin(), vals.end(), v) - vals.begin());
    };
    
    // init BIT roots
    bit_roots.assign(N+1, 0);
    pool[0] = {0,0,0};
    
    // build initial
    for (int i = 0; i < N; i++) {
        int vid = getId(A[i]);
        bit_update(i+1, vid, +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) {
                bit_update(idx+1, oldv, -1);
                bit_update(idx+1, newv, +1);
                A[idx] = q.x;
            }
        } else {
            int l = q.l, r = q.r;
            int len = r - l + 1;
            int k = (len + 1) >> 1;
            vector<int> r_nodes, l_nodes;
            for (int i = r+1; i > 0; i -= i & -i) r_nodes.push_back(bit_roots[i]);
            for (int i = l;   i > 0; i -= i & -i) l_nodes.push_back(bit_roots[i]);
            int vid = kth_query(r_nodes, l_nodes, 0, M-1, k);
            cout << vals[vid] << '\n';
        }
    }
    return 0;
}
0