結果

問題 No.3122 Median of Medians of Division
ユーザー Takao Obi
提出日時 2025-04-19 14:49:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,558 bytes
コンパイル時間 2,425 ms
コンパイル使用メモリ 206,236 KB
実行使用メモリ 127,124 KB
最終ジャッジ日時 2025-04-19 14:51:36
合計ジャッジ時間 87,679 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 1 RE * 19 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Persistent segment-tree nodes pooled
struct Node { int lc, rc; int cnt; };
static const int MAXN = 200000;
static const int MAXQ = 200000;
static const int POOL_SIZE = (MAXN + MAXQ) * 25;
static Node pool[POOL_SIZE];
static int pool_ptr = 1;

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) {
        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, M;
vector<int> vals;
vector<int> A;
vector<int> bit_root; // size N+1

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

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

    bit_root.assign(N+1, 0);
    pool[0] = {0,0,0};

    for (int i = 0; i < N; i++){
        bit_update(i+1, getId(A[i]), +1);
    }

    // scratch arrays for nodes (max BIT height ~18)
    int maxH = 0;
    while((1<<maxH) <= N) maxH++;
    vector<int> r_nodes(maxH), l_nodes(maxH);

    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 k = ((r-l+1) + 1) >> 1;
            int sz = 0;
            for (int i = r+1; i > 0; i -= i & -i) r_nodes[sz++] = bit_root[i];
            int sz2 = 0;
            for (int i = l; i > 0; i -= i & -i) l_nodes[sz2++] = bit_root[i];
            int L = 0, R = M-1;
            while (L < R){
                int mid = (L+R) >> 1;
                ll cntL = 0;
                for (int j = 0; j < sz; j++) cntL += pool[ pool[r_nodes[j]].lc ].cnt;
                for (int j = 0; j < sz2; j++) cntL -= pool[ pool[l_nodes[j]].lc ].cnt;
                if (k <= cntL){
                    for (int j = 0; j < sz; j++) r_nodes[j] = pool[r_nodes[j]].lc;
                    for (int j = 0; j < sz2; j++) l_nodes[j] = pool[l_nodes[j]].lc;
                    R = mid;
                } else {
                    k -= cntL;
                    for (int j = 0; j < sz; j++) r_nodes[j] = pool[r_nodes[j]].rc;
                    for (int j = 0; j < sz2; j++) l_nodes[j] = pool[l_nodes[j]].rc;
                    L = mid+1;
                }
            }
            cout << vals[L] << '\n';
        }
    }
    return 0;
}
0