提出 #50848281

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/segtree>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

void ins(std::set<std::pair<Num, Num>>& s, Num v, Num ct) {
    auto it = s.lower_bound(std::make_pair(v,-1));

    if (it == s.end()) {
        s.insert(std::make_pair(v,ct));
    } else if (it->first != v) {
        s.insert(std::make_pair(v,ct));
    } else {
        Num c = it->second + ct;
        s.erase(it);
        if (c != 0) {
            s.insert(std::make_pair(v,c));
        }
    }
}

struct Node {
    std::array<std::pair<Num, Num>, 2> elements {{{0, 0}, {0, 0}}};

    Node(void) = default;

    explicit Node(Num d) {
        elements.at(0).first = d;
        elements.at(0).second = 1;
    }

    Node merge(const Node& rhs) const {
        std::set<std::pair<Num, Num>> s;
        ins(s, elements.at(0).first, elements.at(0).second);
        ins(s, elements.at(1).first, elements.at(1).second);
        ins(s, rhs.elements.at(0).first, rhs.elements.at(0).second);
        ins(s, rhs.elements.at(1).first, rhs.elements.at(1).second);

        Node result;
        Num idx = 0;
        for(auto it = s.rbegin(); (idx < 2) && (it != s.rend()); ++it) {
            result.elements.at(idx).first = it->first;
            result.elements.at(idx).second = it->second;
            ++idx;
        };
        return result;
    }
};

Node apply(const Node& a, const Node& b) {
    return a.merge(b);
}

Node unit() {
    return Node();
}

void solve(std::istream& is, std::ostream& os) {
    Num n, q;
    is >> n >> q;

    atcoder::segtree<Node, apply, unit> tree(n);
    for(Num i{0}; i<n; ++i) {
        Num a;
        is >> a;
        tree.set(i, Node(a));
    }

    while(q-- > 0) {
        Num cmd, a, b;
        is >> cmd >> a >> b;
        if (cmd == 1) {
            --a;
            tree.set(a, Node(b));
        } else {
            auto ll = a - 1;
            auto rr = b;
            auto result = tree.prod(ll, rr);
            if (result.elements.at(1).first <= 0) {
                os << "0\n";
            } else {
                os << result.elements.at(1).second << "\n";
            }
        }
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

提出情報

ジャッジ結果