結果

問題 No.3122 Median of Medians of Division
ユーザー Naru820
提出日時 2025-04-16 17:52:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 451 ms / 2,000 ms
コード長 2,475 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 103,856 KB
実行使用メモリ 16,080 KB
最終ジャッジ日時 2025-04-17 09:11:59
合計ジャッジ時間 17,973 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<vector>
#include<array>
#include<algorithm>
#include<iostream>
#include<cassert>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); i++)

template<typename S, S (*op)(S, S), S (*e)()> class SegmentTree {
    private:
    int _n, sz;
    vector<S> data;
    
    void calc(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); }
    
    public:
    SegmentTree() = default;
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())) {}
    explicit SegmentTree(const vector<S>& v) : _n(v.size()) {
        sz = 1;
        while(sz < _n) sz <<= 1;
        data.assign(sz << 1, e());
        for(int i = 0; i < _n; i++) data[sz + i] = v[i];
        for(int i = sz - 1; i >= 1; i--) calc(i);
    }
    
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += sz;
        data[p] = x;
        while(p >>= 1) calc(p);
    }
    
    S get(int p) {
        assert(0 <= p && p < _n);
        return data[p + sz];
    }
    
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sl = e(), sr = e();
        l += sz;
        r += sz;
        while(l < r) {
            if(l & 1) sl = op(sl, data[l++]);
            if(r & 1) sr = op(data[--r], sr);
            l >>= 1;
            r >>= 1;
        }
        return op(sl, sr);
    }
    
    S all_prod() { return data[1]; }
};


using S = array<ll, 2>;
S e() {return {0, 0};}
S op(S a, S b) {
    // 大きい方から二つを管理する
    if (a[0] < b[0]) swap(a, b);
    if (a[1] < b[0]) swap(a[1], b[0]);
    return a;
}

int main() {
    // 入力
    int n, q; 
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<S> data(n-1);
    rep(i, 0, n-1) {
        data[i] = {min(a[i], a[i+1]), 0};
    }
    // セグメント木の初期化
    SegmentTree<S, op, e> seg(data);
    
    // クエリ処理
    while (q--) {
        int t;
        cin >> t;
        if(t == 1){
            int i,x;
            cin >> i >> x;
            i--;
            a[i] = x;
            if(i < n - 1){
                seg.set(i, {min(a[i], a[i+1]), 0});
            }
            if(i > 0){
                seg.set(i - 1, {min(a[i - 1], a[i]), 0});
            }
        }
        else{
            int l,r;
            cin >> l >> r;
            l--, r--;
            auto res = op(op({a[l], 0}, seg.prod(l, r)), {a[r], 0});
            cout << res[1] << endl;
        }
    }
}
0