結果

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

ソースコード

diff # 

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

struct Node {
    vector<int> pos;
    vector<int> bit;
};

vector<Node> seg;
int Mvals;
vector<int> vals; // decompress

void collect(int idx, int L, int R, int vid, int p) {
    seg[idx].pos.push_back(p);
    if (L == R) return;
    int mid = (L + R) >> 1;
    if (vid <= mid) collect(idx<<1, L, mid, vid, p);
    else collect(idx<<1|1, mid+1, R, vid, p);
}

void build(int idx, int L, int R) {
    auto &nd = seg[idx];
    auto &v = nd.pos;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    nd.bit.assign(v.size()+1, 0);
    if (L == R) return;
    int mid = (L + R) >> 1;
    build(idx<<1, L, mid);
    build(idx<<1|1, mid+1, R);
}

// BIT utilities on nd.bit
inline void bit_update(vector<int> &bit, int i, int delta) {
    int n = bit.size();
    for (; i < n; i += i & -i) bit[i] += delta;
}
inline int bit_sum(const vector<int> &bit, int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

void updateBit(int idx, int L, int R, int vid, int p, int delta) {
    // update node idx
    auto &nd = seg[idx];
    int i = lower_bound(nd.pos.begin(), nd.pos.end(), p) - nd.pos.begin();
    // i is 0-based index in pos; BIT is 1-based
    bit_update(nd.bit, i+1, delta);
    if (L == R) return;
    int mid = (L + R) >> 1;
    if (vid <= mid) updateBit(idx<<1, L, mid, vid, p, delta);
    else updateBit(idx<<1|1, mid+1, R, vid, p, delta);
}

int queryCount(int idx, int L, int R, int ql, int qr) {
    auto &nd = seg[idx];
    // count positions in [ql,qr]
    auto &v = nd.pos;
    int li = lower_bound(v.begin(), v.end(), ql) - v.begin();
    int ri = upper_bound(v.begin(), v.end(), qr) - v.begin() - 1;
    if (ri < li) return 0;
    return bit_sum(nd.bit, ri+1) - bit_sum(nd.bit, li);
}

int queryKth(int idx, int L, int R, int ql, int qr, int k) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    int cntLeft = queryCount(idx<<1, L, mid, ql, qr);
    if (cntLeft >= k) return queryKth(idx<<1, L, mid, ql, qr, k);
    else return queryKth(idx<<1|1, mid+1, R, ql, qr, k - cntLeft);
}

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; int i, l, r, x; };
    vector<Query> queries(Q);
    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;
        queries[qi].type = t;
        if (t == 1) {
            int idx, x;
            cin >> idx >> x;
            queries[qi].i = idx - 1;
            queries[qi].x = x;
            vals.push_back(x);
        } else {
            int l, r;
            cin >> l >> r;
            queries[qi].type = 2;
            queries[qi].l = l - 1;
            queries[qi].r = r - 1;
        }
    }
    // compress values
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    Mvals = vals.size();
    auto getId = [&](int x){
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin());
    };
    // build segtree
    seg.resize(4 * Mvals + 4);
    // collect positions for initial
    for (int i = 0; i < N; i++) {
        int vid = getId(A[i]);
        collect(1, 0, Mvals-1, vid, i);
    }
    // collect for updates
    for (int qi = 0; qi < Q; qi++) {
        if (queries[qi].type == 1) {
            int vid = getId(queries[qi].x);
            int p = queries[qi].i;
            collect(1, 0, Mvals-1, vid, p);
        }
    }
    // build BIT arrays
    build(1, 0, Mvals-1);
    // initialize with initial A
    vector<int> Avid(N);
    for (int i = 0; i < N; i++) {
        int vid = getId(A[i]);
        Avid[i] = vid;
        updateBit(1, 0, Mvals-1, vid, i, 1);
    }
    // process queries
    for (int qi = 0; qi < Q; qi++) {
        auto &q = queries[qi];
        if (q.type == 1) {
            int p = q.i;
            int oldv = Avid[p];
            int newv = getId(q.x);
            if (oldv != newv) {
                updateBit(1, 0, Mvals-1, oldv, p, -1);
                updateBit(1, 0, Mvals-1, newv, p, +1);
                Avid[p] = newv;
            }
        } else {
            int l = q.l;
            int r = q.r;
            int len = r - l + 1;
            int k = (len + 1) >> 1;
            int vid = queryKth(1, 0, Mvals-1, l, r, k);
            cout << vals[vid] << '\n';
        }
    }
    return 0;
}
0