Submission #50801097

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  02.03.2024 17:45
**/
#include <bits/stdc++.h>

template <typename Info>
class Segtree {
    int n;
    std::vector<Info> info;

    Info query(int p, int l, int r, int ql, int qr) {
        if (ql <= l and r <= qr)
            return info[p];
        int m = (l + r) / 2;
        return qr <= m ? query(2 * p, l, m, ql, qr)
                            : ql >= m ? query(2 * p + 1, m, r, ql, qr)
                                : query(2 * p, l, m, ql, m) + query(2 * p + 1, m, r, m, qr);
    }
    void update(int p, int l, int r, int i, const auto &v) {
        if (r - l == 1) {
            info[p].apply(v);
            return;
        }
        int m = (l + r) / 2;
        i < m ? update(2 * p, l, m, i, v) : update(2 * p + 1, m, r, i, v);
        info[p] = info[2 * p] + info[2 * p + 1];
    }

public:
    Segtree() : n(0) {}
    Segtree(int _n, Info _v = {}) : Segtree(std::vector(_n, _v)) {}

    template <std::convertible_to<Info> U>
    Segtree(const std::vector<U> &a) : n(a.size()) {
        assert(n > 0);
        int cap = ((1 + !!(n & (n - 1))) << std::__lg(2 * n)) + 1;
        info.resize(cap);
        auto build = [&](auto &&self, int p, int l, int r) -> void {
            if (r - l == 1) {
                info[p] = a[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, 2 * p, l, m);
            self(self, 2 * p + 1, m, r);
            info[p] = info[2 * p] + info[2 * p + 1];
        };
        build(build, 1, 0, n);
    }

    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void update(int p, auto v) {
        return update(1, 0, n, p, v);
    }
};

struct Info {
    std::array<int, 2> a, b;
    Info(int _a = -1, int _b = -1) : a({_a, 0}), b({_b, 0}) {
        if (~_a) a[1] = 1;
        if (~_b) b[1] = 1;
    }

    void apply(auto t) {
        a = {t, 1};
    }
};

Info operator+(Info l, Info r) {
    std::array<std::array<int, 2>, 4> x;
    x[0] = l.a;
    x[1] = l.b;
    x[2] = r.a;
    x[3] = r.b;
    std::ranges::sort(x, std::greater{});
    Info res;
    res.a = x[0];
    int i = 1;
    if (x[1][0] == x[0][0])
        res.a[1] += x[1][1], ++i;
    res.b = x[i];
    if (x[i + 1][0] == res.b[0])
        res.b[1] += x[i + 1][1];
    return res;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto &x : a)
        std::cin >> x;

    Segtree<Info> st(a);

    while (q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int p, x;
            std::cin >> p >> x;
            st.update(--p, x);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << st.query(--l, r).b[1] << '\n';
        }
    }
}

Submission Info

Judge Result