結果

問題 No.3122 Median of Medians of Division
ユーザー Yu_212
提出日時 2025-04-20 11:59:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 403 ms / 2,000 ms
コード長 5,577 bytes
コンパイル時間 5,051 ms
コンパイル使用メモリ 287,560 KB
実行使用メモリ 17,460 KB
最終ジャッジ日時 2025-04-20 11:59:31
合計ジャッジ時間 19,925 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Segment Tree with half-open intervals [l, r):
//  - point update: set A[pos] = value
//  - range query: retrieve the maximum and second maximum in A[l..r)

struct Node {
    int mx1, mx2;
    Node(int a = INT_MIN, int b = INT_MIN) : mx1(a), mx2(b) {}
};

class SegTree {
private:
    int n;
    vector<Node> st;

    // Merge two child nodes into parent
    Node merge(const Node &L, const Node &R) {
        Node res;
        if (L.mx1 >= R.mx1) {
            res.mx1 = L.mx1;
            res.mx2 = max(L.mx2, R.mx1);
        } else {
            res.mx1 = R.mx1;
            res.mx2 = max(R.mx2, L.mx1);
        }
        return res;
    }

    // build node p covering [l, r)
    void build(int p, int l, int r, const vector<int> &A) {
        if (r - l == 1) {
            st[p] = Node(A[l], INT_MIN);
            return;
        }
        int m = (l + r) >> 1;
        build(p<<1,   l, m, A);
        build(p<<1|1, m, r, A);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }

    // update position idx to val in node p covering [l, r)
    void update(int p, int l, int r, int idx, int val) {
        if (r - l == 1) {
            st[p] = Node(val, INT_MIN);
            return;
        }
        int m = (l + r) >> 1;
        if (idx < m) update(p<<1,   l, m, idx, val);
        else         update(p<<1|1, m, r, idx, val);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }

    // query on [ql, qr) in node p covering [l, r)
    Node query(int p, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return Node();
        if (ql <= l && r <= qr) return st[p];
        int m = (l + r) >> 1;
        Node L = query(p<<1,   l, m, ql, qr);
        Node R = query(p<<1|1, m, r, ql, qr);
        return merge(L, R);
    }

public:
    // Initialize with array A (0-based)
    SegTree(const vector<int> &A) {
        n = A.size();
        st.assign(4*n, Node());
        build(1, 0, n, A);
    }

    // Point update: A[pos] = val
    void update(int pos, int val) {
        if (pos < 0 || pos >= n) return;
        update(1, 0, n, pos, val);
    }

    // Range query [l, r): returns Node with mx1, mx2
    Node query(int l, int r) {
        if (l < 0) l = 0;
        if (r > n) r = n;
        if (l >= r) return Node();
        return query(1, 0, n, l, r);
    }
};


// 2) Segment Tree for minimum on even and odd indices on half-open intervals [l, r)
struct NodeMin {
    int min_even, min_odd;
    NodeMin(int me = INT_MAX, int mo = INT_MAX) : min_even(me), min_odd(mo) {}
};

class SegTreeMinParity {
private:
    int n;
    vector<NodeMin> st;

    NodeMin merge(const NodeMin &L, const NodeMin &R) const {
        return NodeMin(
            min(L.min_even, R.min_even),
            min(L.min_odd,  R.min_odd)
        );
    }

    void build(int p, int l, int r, const vector<int> &A) {
        if (r - l == 1) {
            int me = (l % 2 == 0 ? A[l] : INT_MAX);
            int mo = (l % 2 == 1 ? A[l] : INT_MAX);
            st[p] = NodeMin(me, mo);
            return;
        }
        int m = (l + r) >> 1;
        build(p<<1, l, m, A);
        build(p<<1|1, m, r, A);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }

    void update(int p, int l, int r, int idx, int val) {
        if (r - l == 1) {
            int me = (l % 2 == 0 ? val : INT_MAX);
            int mo = (l % 2 == 1 ? val : INT_MAX);
            st[p] = NodeMin(me, mo);
            return;
        }
        int m = (l + r) >> 1;
        if (idx < m) update(p<<1, l, m, idx, val);
        else         update(p<<1|1, m, r, idx, val);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }

    NodeMin query(int p, int l, int r, int ql, int qr) const {
        if (qr <= l || r <= ql) return NodeMin();
        if (ql <= l && r <= qr) return st[p];
        int m = (l + r) >> 1;
        NodeMin L = query(p<<1, l, m, ql, qr);
        NodeMin R = query(p<<1|1, m, r, ql, qr);
        return merge(L, R);
    }

public:
    SegTreeMinParity(const vector<int> &A) {
        n = A.size();
        st.assign(4*n, NodeMin());
        build(1, 0, n, A);
    }

    void update(int pos, int val) {
        if (pos < 0 || pos >= n) return;
        update(1, 0, n, pos, val);
    }

    NodeMin query(int l, int r) const {
        if (l < 0) l = 0;
        if (r > n) r = n;
        if (l >= r) return NodeMin();
        return query(1, 0, n, l, r);
    }
};

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];
    vector<int> B(N-1);
    for (int i = 0; i < N-1; i++) {
        B[i] = min(A[i], A[i+1]);
    }

    SegTree st(B);
    SegTreeMinParity stMin(A);
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int idx, x;
            cin >> idx >> x;
            idx--;
            A[idx] = x;
            if (idx > 0) {
                B[idx-1] = min(A[idx], A[idx-1]);
                st.update(idx-1, B[idx-1]);
            }
            if (idx < N-1) {
                B[idx] = min(A[idx], A[idx+1]);
                st.update(idx, B[idx]);
            }
            stMin.update(idx, A[idx]);
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            l--;
            int ans = 0;
            Node res = st.query(l, r-1);
            ans = max(ans, min(A[l], A[r-1]));
            ans = max(ans, min(res.mx1, max(A[l], A[r-1])));
            ans = max(ans, res.mx2);
            cout << ans << endl;
        }
    }

    return 0;
}
0