data_structure/test/erasable_priority_queue.test.cpp

View this file on GitHub
Last update: 2026-04-11 00:41:57+09:00
Problem: https://judge.yosupo.jp/problem/aplusb
Link: https://atcoder.jp/contests/abc342/tasks/abc342_g

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#include "../../data_structure/erasable_priority_queue.hpp"
#include "../../misc/bit_ceil.hpp"
#include "../../segment_tree/enumerate_segment_tree_nodes.hpp"

std::vector<int> solve(std::vector<int>& a,
                       std::vector<std::tuple<int, int, int, int>>& query) {
    const int n = (int)(a.size());

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

    std::vector<int> ans;
    for (auto&& [type, l, r, x] : query) {
        if (type == 1) {
            l--;
            auto nodes =
                enumerate_segment_tree_range_covering_nodes(size, l, r);
            for (auto&& i : nodes) d[i].push(x);
        } else if (type == 2) {
            l--;
            auto [ptype, pl, pr, px] = query[l];
            auto nodes =
                enumerate_segment_tree_range_covering_nodes(size, pl, pr);
            for (auto&& i : nodes) d[i].erase(px);
        } else {
            l--;
            auto nodes = enumerate_segment_tree_point_containing_nodes(size, l);
            int mx = 0;
            for (auto&& i : nodes) {
                if (d[i].size() > 0) mx = std::max(mx, d[i].top());
            }
            ans.push_back(mx);
        }
    }
    return ans;
}

void test1_sample1() {
    std::vector<int> a = {2, 7, 1, 8, 2, 8};
    std::vector<std::tuple<int, int, int, int>> query = {
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {1, 1, 5, 4},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {1, 3, 6, 9},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {2, 4, -1, -1},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}};
    std::vector<int> sol = {2, 1, 8, 4, 4, 8, 4, 9, 9, 2, 9, 9};
    assert(solve(a, query) == sol);
}

void test2_sample2() {
    std::vector<int> a = {721, 78,  541, 256, 970, 478, 370, 467,
                          344, 542, 43,  166, 619, 17,  592, 222,
                          983, 729, 338, 747, 62,  452, 815, 838};
    std::vector<std::tuple<int, int, int, int>> query = {
        {3, 10, -1, -1}, {3, 8, -1, -1},  {3, 8, -1, -1},  {3, 13, -1, -1},
        {3, 9, -1, -1},  {1, 1, 17, 251}, {3, 3, -1, -1},  {3, 19, -1, -1},
        {3, 13, -1, -1}, {3, 22, -1, -1}, {3, 1, -1, -1},  {3, 15, -1, -1},
        {3, 18, -1, -1}, {3, 10, -1, -1}, {3, 15, -1, -1}, {1, 16, 19, 883},
        {1, 8, 23, 212}, {3, 5, -1, -1},  {3, 13, -1, -1}, {2, 6, -1, -1},
        {3, 15, -1, -1}, {1, 5, 18, 914}, {2, 17, -1, -1}, {3, 20, -1, -1},
        {1, 23, 23, 56}, {3, 13, -1, -1}, {2, 25, -1, -1}, {3, 13, -1, -1},
        {3, 13, -1, -1}, {3, 10, -1, -1}, {2, 16, -1, -1}, {1, 17, 22, 308},
        {3, 19, -1, -1}, {3, 17, -1, -1}, {3, 7, -1, -1}};
    std::vector<int> sol = {542, 467, 467, 619, 344, 541, 338, 619, 452,
                            721, 592, 729, 542, 592, 970, 619, 592, 747,
                            914, 914, 914, 914, 338, 983, 914};
    assert(solve(a, query) == sol);
}

int main() {
    // https://atcoder.jp/contests/abc342/tasks/abc342_g
    test1_sample1();
    test2_sample2();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}

#line 1 "data_structure/test/erasable_priority_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#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 "misc/bit_ceil.hpp"

#line 4 "misc/bit_ceil.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// bit_ceil
// (0, 1, 2, 3, 4) -> (1, 1, 2, 4, 4)
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int x) {
    unsigned int p = 1;
    while (p < x) p *= 2;
    return p;
}
unsigned long long int bit_ceil(unsigned long long int x) {
    unsigned long long int p = 1;
    while (p < x) p *= 2;
    return p;
}
#endif
int bit_ceil(int x) {
    assert(x >= 0);
    return bit_ceil((unsigned int)(x));
}
long long int bit_ceil(long long int x) {
    assert(x >= 0);
    return bit_ceil((unsigned long long int)(x));
}
#line 2 "segment_tree/enumerate_segment_tree_nodes.hpp"

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

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 8 "segment_tree/enumerate_segment_tree_nodes.hpp"

// 長さ 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 = topbit(size);
    // i の最上位ビット
    const int topbiti = topbit(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 8 "data_structure/test/erasable_priority_queue.test.cpp"

std::vector<int> solve(std::vector<int>& a,
                       std::vector<std::tuple<int, int, int, int>>& query) {
    const int n = (int)(a.size());

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

    std::vector<int> ans;
    for (auto&& [type, l, r, x] : query) {
        if (type == 1) {
            l--;
            auto nodes =
                enumerate_segment_tree_range_covering_nodes(size, l, r);
            for (auto&& i : nodes) d[i].push(x);
        } else if (type == 2) {
            l--;
            auto [ptype, pl, pr, px] = query[l];
            auto nodes =
                enumerate_segment_tree_range_covering_nodes(size, pl, pr);
            for (auto&& i : nodes) d[i].erase(px);
        } else {
            l--;
            auto nodes = enumerate_segment_tree_point_containing_nodes(size, l);
            int mx = 0;
            for (auto&& i : nodes) {
                if (d[i].size() > 0) mx = std::max(mx, d[i].top());
            }
            ans.push_back(mx);
        }
    }
    return ans;
}

void test1_sample1() {
    std::vector<int> a = {2, 7, 1, 8, 2, 8};
    std::vector<std::tuple<int, int, int, int>> query = {
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {1, 1, 5, 4},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {1, 3, 6, 9},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}, {2, 4, -1, -1},
        {3, 1, -1, -1}, {3, 3, -1, -1}, {3, 4, -1, -1}};
    std::vector<int> sol = {2, 1, 8, 4, 4, 8, 4, 9, 9, 2, 9, 9};
    assert(solve(a, query) == sol);
}

void test2_sample2() {
    std::vector<int> a = {721, 78,  541, 256, 970, 478, 370, 467,
                          344, 542, 43,  166, 619, 17,  592, 222,
                          983, 729, 338, 747, 62,  452, 815, 838};
    std::vector<std::tuple<int, int, int, int>> query = {
        {3, 10, -1, -1}, {3, 8, -1, -1},  {3, 8, -1, -1},  {3, 13, -1, -1},
        {3, 9, -1, -1},  {1, 1, 17, 251}, {3, 3, -1, -1},  {3, 19, -1, -1},
        {3, 13, -1, -1}, {3, 22, -1, -1}, {3, 1, -1, -1},  {3, 15, -1, -1},
        {3, 18, -1, -1}, {3, 10, -1, -1}, {3, 15, -1, -1}, {1, 16, 19, 883},
        {1, 8, 23, 212}, {3, 5, -1, -1},  {3, 13, -1, -1}, {2, 6, -1, -1},
        {3, 15, -1, -1}, {1, 5, 18, 914}, {2, 17, -1, -1}, {3, 20, -1, -1},
        {1, 23, 23, 56}, {3, 13, -1, -1}, {2, 25, -1, -1}, {3, 13, -1, -1},
        {3, 13, -1, -1}, {3, 10, -1, -1}, {2, 16, -1, -1}, {1, 17, 22, 308},
        {3, 19, -1, -1}, {3, 17, -1, -1}, {3, 7, -1, -1}};
    std::vector<int> sol = {542, 467, 467, 619, 344, 541, 338, 619, 452,
                            721, 592, 729, 542, 592, 970, 619, 592, 747,
                            914, 914, 914, 914, 338, 983, 914};
    assert(solve(a, query) == sol);
}

int main() {
    // https://atcoder.jp/contests/abc342/tasks/abc342_g
    test1_sample1();
    test2_sample2();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}