結果

問題 No.3122 Median of Medians of Division
ユーザー Yu_212
提出日時 2025-04-20 02:59:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,675 bytes
コンパイル時間 4,827 ms
コンパイル使用メモリ 329,244 KB
実行使用メモリ 426,668 KB
最終ジャッジ日時 2025-04-20 02:59:14
合計ジャッジ時間 12,196 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ll = long long;
using namespace __gnu_pbds;

// Order-statistic tree for pairs (value, unique_id) to allow duplicates
using OST = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

// Fenwick tree of OSTs supporting point updates and range count_ge queries
struct Fenwick {
    int n;
    vector<OST> bit;
    Fenwick(int _n): n(_n), bit(n+1) {}
    // add==true -> insert val; add==false -> erase val
    void update(int idx, const pair<int,int>& val, bool add) {
        for (; idx <= n; idx += idx & -idx) {
            if (add) bit[idx].insert(val);
            else bit[idx].erase(val);
        }
    }
    // count >= x in prefix [1..idx]
    int prefix_count_ge(int idx, int x) {
        int res = 0;
        pair<int,int> key = {x, INT_MIN};
        for (; idx > 0; idx -= idx & -idx) {
            int sz = bit[idx].size();
            int less = bit[idx].order_of_key(key);
            res += sz - less;
        }
        return res;
    }
    // count >= x in [l..r]
    int range_count_ge(int l, int r, int x) {
        if (l > r) return 0;
        return prefix_count_ge(r, x) - prefix_count_ge(l - 1, x);
    }
};

struct Query { int type, a, b; };

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N+1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++)
        cin >> queries[i].type >> queries[i].a >> queries[i].b;

    // Fenwicks for A, D1=min(A[i],A[i+1]), E=max(A[i],A[i+1])
    Fenwick ftA(N), ftD1(max(N-1,1)), ftE(max(N-1,1));
    // build initial
    for (int i = 1; i <= N; i++)
        ftA.update(i, {A[i], i}, true);
    for (int i = 1; i < N; i++) {
        int d1 = min(A[i], A[i+1]);
        int e  = max(A[i], A[i+1]);
        ftD1.update(i, {d1, i}, true);
        ftE.update(i, {e, i}, true);
    }

    auto delAdj = [&](int pos) {
        if (pos < 1 || pos >= N) return;
        int old_d1 = min(A[pos], A[pos+1]);
        int old_e  = max(A[pos], A[pos+1]);
        ftD1.update(pos, {old_d1, pos}, false);
        ftE.update(pos, {old_e, pos}, false);
    };

    auto updAdj = [&](int pos) {
        if (pos < 1 || pos >= N) return;
        int new_d1 = min(A[pos], A[pos+1]);
        int new_e  = max(A[pos], A[pos+1]);
        ftD1.update(pos, {new_d1, pos}, true);
        ftE.update(pos, {new_e, pos}, true);
    };

    auto check = [&](int m, int l, int r) {
        int len = r - l + 1;
        int ones = ftA.range_count_ge(l, r, m);
        int a = ftD1.range_count_ge(l, r - 1, m);
        int total_pairs = r - l;
        int z = total_pairs - ftE.range_count_ge(l, r - 1, m);
        int left_zero = (A[l] < m ? 1 : 0);
        int seg0 = ((len) - a - z + left_zero) / 2;
        return ones > seg0;
    };

    for (auto &q : queries) {
        if (q.type == 1) {
            int i = q.a, newv = q.b;
            ftA.update(i, {A[i], i}, false);
            ftA.update(i, {newv, i}, true);
            delAdj(i - 1);
            delAdj(i);
            A[i] = newv;
            updAdj(i - 1);
            updAdj(i);
        } else {
            int l = q.a, r = q.b;
            int lo = 1, hi = 1000000001, ans = 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (check(mid, l, r)) {
                    ans = mid;
                    lo = mid + 1;
                } else hi = mid - 1;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}
0