Library

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

View the Project on GitHub ebi-fly13/Library

:heavy_check_mark: offline 2D dual segtree
(data_structure/offline_dual_segtree_2d.hpp)

説明

可換モノイドについて、長方形クエリ、 $1$ 点所得を行えるデータ構造。クエリ先読みにより、必要な部分だけ作ることでメモリ使用量を減らして点の座標が$10^9$とかでも使える。

pre_set(i, j)

所得クエリで用いる点 $(i,j)$ を追加する。

build()

クエリ先読み後（pre_set後）、セグ木を構築する。

apply(l,d,r,u,f)

$[l, r) \times [d, u)$ の長方形に $f$ を作用させる。

get(i, j)

$(i, j)$ の値を所得する。

Depends on

Verified with

Code

#pragma once

#include <bit>
#include <utility>
#include <vector>

#include "../data_structure/compress.hpp"
#include "../data_structure/dual_segtree.hpp"

namespace ebi {

template <class F, F (*merge)(F, F), F (*id)()> struct offline_dual_segtree_2d {
    offline_dual_segtree_2d() = default;

    void pre_set(std::pair<int, int> p) {
        ps.emplace_back(p);
    }

    void build() {
        for (auto [x, y] : ps) {
            xs.add(x);
        }
        xs.build();
        sz = std::bit_ceil((unsigned int)xs.size());
        ys.resize(2 * sz);
        for (auto [x, y] : ps) {
            int i = xs.get(x) + sz;
            ys[i].add(y);
            while (i > 1) {
                i >>= 1;
                ys[i].add(y);
            }
        }
        for (auto i : std::views::iota(0, 2 * sz)) {
            ys[i].build();
            seg.emplace_back(dual_segtree<F, merge, id>(ys[i].size()));
        }
    }

    F get(int i, int j) {
        i = xs.get(i) + sz;
        F x = seg[i].get(ys[i].get(j));
        while (i > 1) {
            i >>= 1;
            x = merge(x, seg[i].get(ys[i].get(j)));
        }
        return x;
    }

    void apply(int l, int d, int r, int u, F f) {
        l = xs.get(l) + sz;
        r = xs.get(r) + sz;
        while (l < r) {
            if (l & 1) {
                seg[l].apply(ys[l].get(d), ys[l].get(u), f);
                l++;
            }
            if (r & 1) {
                r--;
                seg[r].apply(ys[r].get(d), ys[r].get(u), f);
            }
            l >>= 1;
            r >>= 1;
        }
    }

  private:
    int sz = 1;
    std::vector<std::pair<int, int>> ps;
    compress<int> xs;
    std::vector<compress<int>> ys;
    std::vector<dual_segtree<F, merge, id>> seg;
};

}  // namespace ebi
#line 2 "data_structure/offline_dual_segtree_2d.hpp"

#include <bit>
#include <utility>
#include <vector>

#line 2 "data_structure/compress.hpp"

#include <algorithm>
#include <cassert>
#line 6 "data_structure/compress.hpp"

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

    void build() {
        std::sort(cp.begin(), cp.end());
        cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    }

    void add(const T &val) {
        cp.emplace_back(val);
    }

    int get(const T &val) const {
        return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin();
    }

    int size() const {
        return cp.size();
    }

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi
#line 2 "data_structure/dual_segtree.hpp"

#line 5 "data_structure/dual_segtree.hpp"
#include <ranges>
#line 7 "data_structure/dual_segtree.hpp"

namespace ebi {

template <class F, F (*merge)(F, F), F (*id)()> struct dual_segtree {
  private:
    void all_apply(int i, F f) {
        d[i] = merge(f, d[i]);
    }

    void push(int i) {
        assert(i < sz);
        all_apply(2 * i, d[i]);
        all_apply(2 * i + 1, d[i]);
        d[i] = id();
    }

  public:
    dual_segtree(int n) : dual_segtree(std::vector<F>(n, id())) {}

    dual_segtree(const std::vector<F> &a)
        : n(a.size()),
          sz(std::bit_ceil(a.size())),
          lg2(std::countr_zero((unsigned int)(sz))) {
        d = std::vector<F>(2 * sz, id());
        for (int i : std::views::iota(sz, sz + n)) {
            d[i] = a[i - sz];
        }
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;

        l += sz;
        r += sz;

        for (int i : std::views::iota(1, lg2 + 1) | std::views::reverse) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }

    F get(int p) {
        assert(0 <= p && p < n);
        p += sz;
        for (int i : std::views::iota(1, lg2 + 1) | std::views::reverse) {
            push(p >> i);
        }
        return d[p];
    }

  private:
    int n, sz, lg2;
    std::vector<F> d;
};

}  // namespace ebi
#line 9 "data_structure/offline_dual_segtree_2d.hpp"

namespace ebi {

template <class F, F (*merge)(F, F), F (*id)()> struct offline_dual_segtree_2d {
    offline_dual_segtree_2d() = default;

    void pre_set(std::pair<int, int> p) {
        ps.emplace_back(p);
    }

    void build() {
        for (auto [x, y] : ps) {
            xs.add(x);
        }
        xs.build();
        sz = std::bit_ceil((unsigned int)xs.size());
        ys.resize(2 * sz);
        for (auto [x, y] : ps) {
            int i = xs.get(x) + sz;
            ys[i].add(y);
            while (i > 1) {
                i >>= 1;
                ys[i].add(y);
            }
        }
        for (auto i : std::views::iota(0, 2 * sz)) {
            ys[i].build();
            seg.emplace_back(dual_segtree<F, merge, id>(ys[i].size()));
        }
    }

    F get(int i, int j) {
        i = xs.get(i) + sz;
        F x = seg[i].get(ys[i].get(j));
        while (i > 1) {
            i >>= 1;
            x = merge(x, seg[i].get(ys[i].get(j)));
        }
        return x;
    }

    void apply(int l, int d, int r, int u, F f) {
        l = xs.get(l) + sz;
        r = xs.get(r) + sz;
        while (l < r) {
            if (l & 1) {
                seg[l].apply(ys[l].get(d), ys[l].get(u), f);
                l++;
            }
            if (r & 1) {
                r--;
                seg[r].apply(ys[r].get(d), ys[r].get(u), f);
            }
            l >>= 1;
            r >>= 1;
        }
    }

  private:
    int sz = 1;
    std::vector<std::pair<int, int>> ps;
    compress<int> xs;
    std::vector<compress<int>> ys;
    std::vector<dual_segtree<F, merge, id>> seg;
};

}  // namespace ebi
Back to top page