Range Map
(datastructure/range_map.hpp)

• View this file on GitHub
• Last update: 2024-06-30 18:54:38+09:00
• Include: #include "datastructure/range_map.hpp"

概要

• 各区間に値を持たせることができる、区間を set で管理するテクニック。
• すべて閉区間。

使い方

• range_map(merge_adjacent_segment = true): コンストラクタ。区間 [l, m] と [m + 1, r] を [l, r] にマージしない場合は、merge_adjacent_segment を false にする。
• get(p): p を含む区間のイテレータ（存在しない場合は end()）を返す。
• get({l, r}): 区間 [l, r] を完全に含む区間のイテレータ（存在しない場合は end()）を返す。
• set({l, r}, x): 区間 [l, r] に値 x を持たせる。
• set({l, r}, x, f, g): 区間 [l, r] に値 x を持たせる。そのとき、区間が追加されるたびに f を、区間が削除されるたびに g を実行する。f, g はともに (T l, T r, U x) -> void。

問題例

ABC255 Ex - Range Harvest Query（問題）（提出）

#include <atcoder/modint>
#include <iostream>

#include "datastructure/range_map.hpp"
using mint = atcoder::modint998244353;
int main() {
    long long n;
    int q;
    std::cin >> n >> q;
    range_map<long long, long long> mp;
    mp.set({0, n}, 0);
    while (q--) {
        long long d, l, r;
        std::cin >> d >> l >> r;
        mint ans = 0;
        mp.set(
            {l, r}, d,
            [&](long long l, long long r, long long x) {
                ans -= mint(r - l + 1) * (r + l) / 2 * (d - x);
            },
            [&](long long l, long long r, long long x) {
                ans += mint(r - l + 1) * (r + l) / 2 * (d - x);
            });
        std::cout << ans.val() << '\n';
    }
}

第六回PAST M - 等しい数（問題）（提出）

#include <iostream>

#include "datastructure/range_map.hpp"
int main() {
    int n;
    std::cin >> n;
    range_map<int, long long> mp;
    long long ans = 0;
    std::map<int, long long> cnt;
    auto f = [&](long long l, long long r, long long x) {
        ans -= cnt[x] * (cnt[x] - 1) / 2;
        cnt[x] += r - l + 1;
        ans += cnt[x] * (cnt[x] - 1) / 2;
    };
    auto g = [&](long long l, long long r, long long x) {
        ans -= cnt[x] * (cnt[x] - 1) / 2;
        cnt[x] -= r - l + 1;
        ans += cnt[x] * (cnt[x] - 1) / 2;
    };
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
        mp.set({i, i}, a, f, g);
    }
    int q;
    std::cin >> q;
    while (q--) {
        int l, r, x;
        std::cin >> l >> r >> x;
        mp.set({l, r}, x, f, g);
        std::cout << ans << '\n';
    }
}

Verified with

• test/yukicoder/1601_2.test.cpp

Code

#pragma once
#include <map>
#include <vector>
template <typename T, typename S>
struct range_map {
public:
    range_map(bool merge_adjacent = true) : _merge_adjacent(merge_adjacent) {
    }
    typename std::map<T, std::pair<T, S>>::const_iterator get(T p) const {
        auto it = values.upper_bound(p);
        if (it == values.begin()) return values.end();
        if (std::prev(it)->second.first < p) return values.end();
        return std::prev(it);
    }
    typename std::map<T, std::pair<T, S>>::const_iterator get(
        std::pair<T, T> range) const {
        auto [l, r] = range;
        auto it = get(l);
        if (it == values.end()) return values.end();
        if (it->second.first < r) return values.end();
        return it;
    }
    void set(std::pair<T, T> range, S x) {
        set(range, x, [](T, T, S) {}, [](T, T, S) {});
    }
    template <class op_insert, class op_erase>
    void set(std::pair<T, T> range, S x, const op_insert &f,
             const op_erase &g) {
        auto [l, r] = range;
        auto it_l = values.upper_bound(l);
        if (it_l != values.begin() &&
            l - T(_merge_adjacent) <= std::prev(it_l)->second.first) {
            it_l--;
        }
        auto it_r = values.upper_bound(r + T(_merge_adjacent));
        std::vector<std::tuple<T, T, S>> restore;
        restore.reserve(3);
        if (it_l != values.end() && it_l->first < l) {
            if (it_l->second.second != x) {
                restore.emplace_back(it_l->first, l - 1, it_l->second.second);
            } else {
                l = it_l->first;
            }
        }
        if (it_l != it_r && r < std::prev(it_r)->second.first) {
            if (std::prev(it_r)->second.second != x) {
                restore.emplace_back(r + 1, std::prev(it_r)->second.first,
                                     std::prev(it_r)->second.second);
            } else {
                r = std::prev(it_r)->second.first;
            }
        }
        restore.emplace_back(l, r, x);
        for (auto it = it_l; it != it_r; it = values.erase(it)) {
            g(it->first, it->second.first, it->second.second);
        }
        for (auto [l, r, x] : restore) {
            values[l] = {r, x};
            f(l, r, x);
        }
    }
    typename std::map<std::pair<T, T>, S>::const_iterator begin() const {
        return values.begin();
    }
    typename std::map<std::pair<T, T>, S>::const_iterator end() const {
        return values.end();
    }

protected:
    std::map<T, std::pair<T, S>> values;
    bool _merge_adjacent;
};

#line 2 "datastructure/range_map.hpp"
#include <map>
#include <vector>
template <typename T, typename S>
struct range_map {
public:
    range_map(bool merge_adjacent = true) : _merge_adjacent(merge_adjacent) {
    }
    typename std::map<T, std::pair<T, S>>::const_iterator get(T p) const {
        auto it = values.upper_bound(p);
        if (it == values.begin()) return values.end();
        if (std::prev(it)->second.first < p) return values.end();
        return std::prev(it);
    }
    typename std::map<T, std::pair<T, S>>::const_iterator get(
        std::pair<T, T> range) const {
        auto [l, r] = range;
        auto it = get(l);
        if (it == values.end()) return values.end();
        if (it->second.first < r) return values.end();
        return it;
    }
    void set(std::pair<T, T> range, S x) {
        set(range, x, [](T, T, S) {}, [](T, T, S) {});
    }
    template <class op_insert, class op_erase>
    void set(std::pair<T, T> range, S x, const op_insert &f,
             const op_erase &g) {
        auto [l, r] = range;
        auto it_l = values.upper_bound(l);
        if (it_l != values.begin() &&
            l - T(_merge_adjacent) <= std::prev(it_l)->second.first) {
            it_l--;
        }
        auto it_r = values.upper_bound(r + T(_merge_adjacent));
        std::vector<std::tuple<T, T, S>> restore;
        restore.reserve(3);
        if (it_l != values.end() && it_l->first < l) {
            if (it_l->second.second != x) {
                restore.emplace_back(it_l->first, l - 1, it_l->second.second);
            } else {
                l = it_l->first;
            }
        }
        if (it_l != it_r && r < std::prev(it_r)->second.first) {
            if (std::prev(it_r)->second.second != x) {
                restore.emplace_back(r + 1, std::prev(it_r)->second.first,
                                     std::prev(it_r)->second.second);
            } else {
                r = std::prev(it_r)->second.first;
            }
        }
        restore.emplace_back(l, r, x);
        for (auto it = it_l; it != it_r; it = values.erase(it)) {
            g(it->first, it->second.first, it->second.second);
        }
        for (auto [l, r, x] : restore) {
            values[l] = {r, x};
            f(l, r, x);
        }
    }
    typename std::map<std::pair<T, T>, S>::const_iterator begin() const {
        return values.begin();
    }
    typename std::map<std::pair<T, T>, S>::const_iterator end() const {
        return values.end();
    }

protected:
    std::map<T, std::pair<T, S>> values;
    bool _merge_adjacent;
};

Back to top page