rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: verify/data_structure/erasable_priority_queue.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc342/tasks/abc342_g"

#include <iostream>
#include "data_structure/erasable_priority_queue.hpp"
#include "data_structure/enumerate_segment_tree_nodes.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];

    // 削除可能な priority_queue を乗せたセグ木を作成
    int log = 0;
    while ((1 << log) < N) log++;
    int size = 1 << log;
    std::vector<ErasablePriorityQueue<int>> d(size << 1);
    for (int i = 0; i < N; i++) d[i + size].push(A[i]);

    int Q;
    std::cin >> Q;
    std::vector<int> l(Q, -1), r(Q, -1), x(Q, -1), id(Q, -1);
    for (int qq = 0; qq < Q; qq++) {
        int type;
        std::cin >> type;
        if (type == 1) {
            std::cin >> l[qq] >> r[qq] >> x[qq];
            l[qq]--;
            auto nodes = enumerate_segment_tree_range_covering_nodes(size, l[qq], r[qq]);
            for (auto&& i : nodes) d[i].push(x[qq]);
        } else if (type == 2) {
            std::cin >> id[qq];
            id[qq]--;
            auto nodes = enumerate_segment_tree_range_covering_nodes(size, l[id[qq]], r[id[qq]]);
            for (auto&& i : nodes) d[i].erase(x[id[qq]]);
        } else {
            std::cin >> id[qq];
            id[qq]--;
            auto nodes = enumerate_segment_tree_point_containing_nodes(size, id[qq]);
            int mx = 0;
            for (auto&& i : nodes) {
                if (d[i].size() > 0) mx = std::max(mx, d[i].top());
            }
            std::cout << mx << '\n';
        }
    }
    return 0;
}
#line 1 "verify/data_structure/erasable_priority_queue.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc342/tasks/abc342_g"

#include <iostream>
#line 2 "data_structure/erasable_priority_queue.hpp"

#include <queue>
#include <cassert>

// 削除可能な優先度付きキュー
// キューに含まれていない要素を削除しようとした場合壊れる
// std::multiset よりも定数倍が良い
template <class T, class Container = std::vector<T>, class Compare = std::less<T>> struct ErasablePriorityQueue {
   private:
    std::priority_queue<T, Container, Compare> que, erase_que;
    void reduce() {
        while (que.size() and erase_que.size()) {
            if (que.top() == erase_que.top()) {
                que.pop();
                erase_que.pop();
            } else {
                // Compare = std::less<T> なら que.top() < erase_que.top()
                // Compare()(que.top(), erase_que.top()) == true
                assert(!Compare()(que.top(), erase_que.top()));
                break;
            }
        }
    }

   public:
    size_t size() const {
        assert(que.size() >= erase_que.size());
        return que.size() - erase_que.size();
    }
    void push(const T t) { que.push(t); }
    void erase(const T t) { erase_que.push(t); }
    const T& top() {
        reduce();
        return que.top();
    }
    void pop() {
        reduce();
        que.pop();
    }
};
// ErasablePriorityQueue<int, std::vector<int>, std::greater<int>> que; // 最小のものから取り出せる
#line 2 "data_structure/enumerate_segment_tree_nodes.hpp"

#include <vector>
#line 5 "data_structure/enumerate_segment_tree_nodes.hpp"
#include <algorithm>

// 長さ size (2べき) の Segment Tree において区間 [l, r) をカバーする区間のノード番号を返す
// 区間の位置が小さい順に (左から) 返す
template <class T> std::vector<T> enumerate_segment_tree_range_covering_nodes(const T size, T l, T r) {
    std::vector<T> ret, ret_rev;
    l += size;
    r += size;
    while (l < r) {
        if (l & 1) ret.push_back(l++);
        if (r & 1) ret_rev.push_back(--r);
        l >>= 1;
        r >>= 1;
    }
    std::reverse(ret_rev.begin(), ret_rev.end());
    ret.insert(ret.end(), ret_rev.begin(), ret_rev.end());
    return ret;
}

// 長さ size (2べき) の Segment Tree において seg[p] が含まれる区間のノード番号を返す
// 区間の幅が小さい順に (下から) 返す
template <class T> std::vector<T> enumerate_segment_tree_point_containing_nodes(const T size, T p) {
    p += size;
    std::vector<T> ret;
    for (int i = 0; (1LL << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

// 長さ size (2べき) の Segment Tree においてノード番号 i に対応する区間 [l, r) を返す
// https://atcoder.jp/contests/abc349/tasks/abc349_d
// https://atcoder.jp/contests/abc355/tasks/abc355_e
template <class T> std::pair<T, T> segment_tree_node_to_range(const T size, const T i) {
    assert(size > 0 and i > 0);
    // (1 << n) = size
    const int n = 63 - __builtin_clzll(size);
    // i の最上位ビット
    const int topbiti = 63 - __builtin_clzll(i);
    // [(2 ^ x) * y, (2 ^ x) * (y + 1))
    const int x = n - topbiti;
    const T y = i - (1LL << topbiti);
    return {(1LL << x) * y, (1LL << x) * (y + 1)};
}
#line 6 "verify/data_structure/erasable_priority_queue.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];

    // 削除可能な priority_queue を乗せたセグ木を作成
    int log = 0;
    while ((1 << log) < N) log++;
    int size = 1 << log;
    std::vector<ErasablePriorityQueue<int>> d(size << 1);
    for (int i = 0; i < N; i++) d[i + size].push(A[i]);

    int Q;
    std::cin >> Q;
    std::vector<int> l(Q, -1), r(Q, -1), x(Q, -1), id(Q, -1);
    for (int qq = 0; qq < Q; qq++) {
        int type;
        std::cin >> type;
        if (type == 1) {
            std::cin >> l[qq] >> r[qq] >> x[qq];
            l[qq]--;
            auto nodes = enumerate_segment_tree_range_covering_nodes(size, l[qq], r[qq]);
            for (auto&& i : nodes) d[i].push(x[qq]);
        } else if (type == 2) {
            std::cin >> id[qq];
            id[qq]--;
            auto nodes = enumerate_segment_tree_range_covering_nodes(size, l[id[qq]], r[id[qq]]);
            for (auto&& i : nodes) d[i].erase(x[id[qq]]);
        } else {
            std::cin >> id[qq];
            id[qq]--;
            auto nodes = enumerate_segment_tree_point_containing_nodes(size, id[qq]);
            int mx = 0;
            for (auto&& i : nodes) {
                if (d[i].size() > 0) mx = std::max(mx, d[i].top());
            }
            std::cout << mx << '\n';
        }
    }
    return 0;
}
Back to top page