結果

問題 No.3122 Median of Medians of Division
ユーザー Naru820
提出日時 2025-04-17 11:26:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,127 bytes
コンパイル時間 4,193 ms
コンパイル使用メモリ 292,232 KB
実行使用メモリ 19,176 KB
最終ジャッジ日時 2025-04-17 11:27:23
合計ジャッジ時間 27,937 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MAXN = 1e5 + 5;
const int BUCKET_SIZE = 450;

int N, Q;
vector<int> A;

struct SegTreeMax {
    int size;
    vector<int> max_val, count;

    void init(const vector<int>& data) {
        int n = data.size();
        size = 1;
        while (size < n) size <<= 1;
        max_val.assign(2 * size, 0);
        count.assign(2 * size, 0);
        for (int i = 0; i < n; ++i) {
            max_val[size + i] = data[i];
            count[size + i] = 1;
        }
        for (int i = size - 1; i >= 1; --i) {
            int left = 2 * i, right = 2 * i + 1;
            if (max_val[left] > max_val[right]) {
                max_val[i] = max_val[left];
                count[i] = count[left];
            } else if (max_val[right] > max_val[left]) {
                max_val[i] = max_val[right];
                count[i] = count[right];
            } else {
                max_val[i] = max_val[left];
                count[i] = count[left] + count[right];
            }
        }
    }

    void update(int pos, int val) {
        pos += size;
        max_val[pos] = val;
        pos >>= 1;
        while (pos >= 1) {
            int left = 2 * pos, right = 2 * pos + 1;
            if (max_val[left] > max_val[right]) {
                max_val[pos] = max_val[left];
                count[pos] = count[left];
            } else if (max_val[right] > max_val[left]) {
                max_val[pos] = max_val[right];
                count[pos] = count[right];
            } else {
                max_val[pos] = max_val[left];
                count[pos] = count[left] + count[right];
            }
            pos >>= 1;
        }
    }

    pair<int, int> query_max(int l, int r) {
        int res = INT_MIN, cnt = 0;
        l += size;
        r += size;
        while (l <= r) {
            if (l % 2 == 1) {
                if (max_val[l] > res) {
                    res = max_val[l];
                    cnt = count[l];
                } else if (max_val[l] == res) {
                    cnt += count[l];
                }
                l++;
            }
            if (r % 2 == 0) {
                if (max_val[r] > res) {
                    res = max_val[r];
                    cnt = count[r];
                } else if (max_val[r] == res) {
                    cnt += count[r];
                }
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
        return {res, cnt};
    }
};

SegTreeMax seg;

vector<vector<int>> buckets, sorted_buckets;

void build_buckets() {
    buckets.clear();
    sorted_buckets.clear();
    vector<int> b, sb;
    for (int i = 0; i < N; ++i) {
        if (i % BUCKET_SIZE == 0 && !b.empty()) {
            buckets.push_back(b);
            sorted_buckets.push_back(sb);
            b.clear();
            sb.clear();
        }
        b.push_back(A[i]);
        sb.push_back(A[i]);
    }
    if (!b.empty()) {
        buckets.push_back(b);
        sort(sb.begin(), sb.end());
        sorted_buckets.push_back(sb);
    }
    else if (!sb.empty()) {
        sorted_buckets.push_back(sb);
    }
}

void update_sqrt(int pos, int old_val, int new_val) {
    int bucket_idx = pos / BUCKET_SIZE;
    int idx_in_bucket = pos % BUCKET_SIZE;
    buckets[bucket_idx][idx_in_bucket] = new_val;
    sorted_buckets[bucket_idx] = buckets[bucket_idx];
    sort(sorted_buckets[bucket_idx].begin(), sorted_buckets[bucket_idx].end());
}

int query_kth(int l, int r, int k) {
    vector<int> elems;

    int left_bucket = l / BUCKET_SIZE;
    if (l % BUCKET_SIZE != 0) {
        int end = min((left_bucket + 1) * BUCKET_SIZE - 1, r);
        for (int i = l; i <= end; ++i)
            elems.push_back(A[i]);
        left_bucket++;
    }

    int right_bucket = r / BUCKET_SIZE;
    if ((r + 1) % BUCKET_SIZE != 0 && left_bucket <= right_bucket) {
        int start = right_bucket * BUCKET_SIZE;
        for (int i = start; i <= r; ++i)
            elems.push_back(A[i]);
        right_bucket--;
    }

    for (int b = left_bucket; b <= right_bucket; ++b)
        elems.insert(elems.end(), sorted_buckets[b].begin(), sorted_buckets[b].end());

    sort(elems.begin(), elems.end());
    return elems[k];
}

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

    cin >> N >> Q;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    seg.init(A);
    build_buckets();

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;
            --i;
            int old_val = A[i];
            A[i] = x;
            seg.update(i, x);
            update_sqrt(i, old_val, x);
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            auto [max_val, cnt] = seg.query_max(l, r);
            if (cnt >= 2) {
                cout << max_val << '\n';
            } else {
                int len = r - l + 1;
                int k = (len + 1) / 2 - 1;
                int median = query_kth(l, r, k);
                cout << median << '\n';
            }
        }
    }

    return 0;
}
0