結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー Takao Obi
提出日時 2025-04-19 15:06:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,605 bytes
コンパイル時間 2,686 ms
コンパイル使用メモリ 213,588 KB
実行使用メモリ 155,844 KB
最終ジャッジ日時 2025-04-19 15:07:05
合計ジャッジ時間 11,007 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 2 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// Merge Sort Tree + Fenwick per node

struct Node {
    vector<int> pos;    // sorted unique positions
    vector<int> bit;    // Fenwick tree of size pos.size()+1
};

int N, Q;
vector<int> A;
vector<int> vals;    // compressed values
vector<Node> segtree;
int M;

// collect positions for vid along tree
void collect(int idx, int l, int r, int vid, int p) {
    segtree[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);
}

// build Fenwick per node
void build(int idx, int l, int r) {
    auto &node = segtree[idx];
    auto &v = node.pos;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    node.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);
}

// Fenwick helpers
inline void fenwicks_update(vector<int> &bit, int i, int d) {
    int n = bit.size();
    for (; i < n; i += i & -i) bit[i] += d;
}
inline int fenwicks_sum(const vector<int> &bit, int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

// update point p with delta at value vid
void updatePoint(int idx, int l, int r, int vid, int p, int delta) {
    auto &node = segtree[idx];
    int i = int(lower_bound(node.pos.begin(), node.pos.end(), p) - node.pos.begin()) + 1;
    fenwicks_update(node.bit, i, delta);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (vid <= mid) updatePoint(idx<<1, l, mid, vid, p, delta);
    else            updatePoint(idx<<1|1, mid+1, r, vid, p, delta);
}

// count positions in [ql,qr] in node idx
int countRange(int idx, int ql, int qr) {
    auto &node = segtree[idx];
    auto &v = node.pos;
    int li = int(lower_bound(v.begin(), v.end(), ql) - v.begin()) + 1;
    int ri = int(upper_bound(v.begin(), v.end(), qr) - v.begin());
    if (ri < li) return 0;
    return fenwicks_sum(node.bit, ri) - fenwicks_sum(node.bit, li-1);
}

// query k-th smallest valueID within positions [ql,qr]
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 cnt = countRange(idx<<1, ql, qr);
    if (cnt >= k) return queryKth(idx<<1, l, mid, ql, qr, k);
    else          return queryKth(idx<<1|1, mid+1, r, ql, qr, k - cnt);
}

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

    // build segment tree structure over [0,M-1]
    segtree.assign(4 * M + 4, Node());
    // collect positions: initial A
    for (int i = 0; i < N; i++) {
        int vid = getId(A[i]);
        collect(1, 0, M-1, vid, i);
    }
    // also collect for updates
    for (auto &q : queries) {
        int t = get<0>(q);
        if (t == 1) {
            int i = get<1>(q), x = get<2>(q);
            int vid = getId(x);
            collect(1, 0, M-1, vid, i);
        }
    }
    // build Fenwick trees
    build(1, 0, M-1);
    // initialize with initial A
    for (int i = 0; i < N; i++) {
        int vid = getId(A[i]);
        updatePoint(1, 0, M-1, vid, i, +1);
    }

    // answer queries
    for (auto &q : queries) {
        int t = get<0>(q);
        if (t == 1) {
            int i = get<1>(q), x = get<2>(q);
            int oldv = getId(A[i]);
            int newv = getId(x);
            if (oldv != newv) {
                updatePoint(1, 0, M-1, oldv, i, -1);
                updatePoint(1, 0, M-1, newv, i, +1);
                A[i] = x;
            }
        } else {
            int l = get<3>(q), r = get<4>(q);
            int len = r - l + 1;
            int k = (len + 1) >> 1;
            int vid = queryKth(1, 0, M-1, l, r, k);
            cout << vals[vid] << '\n';
        }
    }
    return 0;
}
0