Sortable Segment Tree
(data-structure/segtree/sortable_segment_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:09:47+09:00
• Include: #include "data-structure/segtree/sortable_segment_tree.hpp"

Description

通常のセグメント木の機能に加えて，区間ソートクエリを処理することができる．ソートされた区間を，キーを添字とする動的セグメント木で管理することでこれを実現する．キーは distinct な 64-bit 整数である．

空間計算量: $O(n\log m)$, $m$ はキーの最大値

Operations

• SortableSegmentTree(long long max_key, vector<pair<long long, T>> kv)
  • キーと値のペアの列から，ソート可能セグメント木を構築する
  • 時間計算量: $O(n \log m)$
• void update(int k, long long key, T val)
  • $k$ 番目の要素のキーを key に，値を val に更新する
  • 時間計算量: $O(\log m)$
• T fold(int l, int r)
  • 区間 $[l, r)$ の値を fold する
  • 時間計算量: $O(\log m)$
• void sort(int l, int r, bool descending = false)
  • 区間 $[l, r)$ をキーをもとにソートする
  • 時間計算量: $\mathrm{amortized}\ O(\log m)$

Reference

• Range Sort Range Product ってなんですか - Mathenachia

Depends on

• Segment Tree (data-structure/segtree/segment_tree.hpp)

Verified with

• test/yosupo/point_set_range_sort_range_composite.test.cpp

Code

#pragma once
#include <memory>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

#include "segment_tree.hpp"

template <typename M>
class SortableSegmentTree {
    using T = M::T;

   public:
    SortableSegmentTree() = default;
    explicit SortableSegmentTree(long long max_key,
                                 const std::vector<std::pair<long long, T>>& kv)
        : n(kv.size()), max_key(max_key), st_all(n), st_sorted(n), rev(n) {
        for (int k = 0; k < n; ++k) {
            auto [key, val] = kv[k];
            st_sorted[k] = std::make_unique<Node>();
            st_sorted[k]->update(key, val, 0, max_key);
            st_all.update(k, val);
            left.insert(k);
        }
        left.insert(n);
    }

    void update(int k, long long key, const T& val) {
        split(k), split(k + 1);
        st_sorted[k] = std::make_unique<Node>();
        st_sorted[k]->update(key, val, 0, max_key);
        st_all.update(k, val);
    }

    T fold(int l, int r) {
        split(l), split(r);
        return st_all.fold(l, r);
    }

    void sort(int l, int r, bool descending = false) {
        if (r - l <= 1) return;
        split(l), split(r);
        auto it = ++left.find(l);
        while (it != left.end() && *it < r) {
            st_sorted[l] =
                join(std::move(st_sorted[l]), std::move(st_sorted[*it]));
            st_all.update(*it, M::id());
            rev[*it] = false;
            it = left.erase(it);
        }
        if (st_sorted[l]) {
            st_all.update(l, !descending ? st_sorted[l]->val_forward
                                         : st_sorted[l]->val_backward);
            rev[l] = descending;
        }
    }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        int sz;
        T val_forward, val_backward;
        node_ptr left, right;
        Node()
            : sz(0),
              val_forward(M::id()),
              val_backward(M::id()),
              left(nullptr),
              right(nullptr) {}

        void recalc() {
            int sl = left ? left->sz : 0;
            int sr = right ? right->sz : 0;
            sz = sl + sr;
            T vl_forward = left ? left->val_forward : M::id();
            T vr_forward = right ? right->val_forward : M::id();
            val_forward = M::op(vl_forward, vr_forward);
            T vl_backward = left ? left->val_backward : M::id();
            T vr_backward = right ? right->val_backward : M::id();
            val_backward = M::op(vr_backward, vl_backward);
        }

        void update(long long key, const T& x, long long l, long long r) {
            if (r - l == 1) {
                sz = 1;
                val_forward = val_backward = x;
                return;
            }
            long long m = std::midpoint(l, r);
            if (key < m) {
                if (!left) left = std::make_unique<Node>();
                left->update(key, x, l, m);
            } else {
                if (!right) right = std::make_unique<Node>();
                right->update(key, x, m, r);
            }
            recalc();
        }
    };

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        if (k == 0) return {nullptr, std::move(t)};
        if (k == t->sz) return {std::move(t), nullptr};
        int szl = t->left ? t->left->sz : 0;
        auto t2 = std::make_unique<Node>();
        if (k < szl) {
            std::tie(t2->left, t->left) = split(std::move(t->left), k);
            std::swap(t, t2);
        } else {
            std::tie(t->right, t2->right) = split(std::move(t->right), k - szl);
        }
        t->recalc(), t2->recalc();
        return {std::move(t), std::move(t2)};
    }

    static node_ptr join(node_ptr t1, node_ptr t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        t1->left = join(std::move(t1->left), std::move(t2->left));
        t1->right = join(std::move(t1->right), std::move(t2->right));
        t1->recalc();
        return t1;
    }

    int n;
    long long max_key;
    std::set<int> left;
    SegmentTree<M> st_all;
    std::vector<node_ptr> st_sorted;
    std::vector<bool> rev;

    void split(int k) {
        int l = *--left.upper_bound(k);
        if (l == k) return;
        if (!rev[l]) {
            std::tie(st_sorted[l], st_sorted[k]) =
                split(std::move(st_sorted[l]), k - l);
        } else {
            std::tie(st_sorted[k], st_sorted[l]) =
                split(std::move(st_sorted[l]), l + st_sorted[l]->sz - k);
            rev[k] = true;
        }
        left.insert(k);
        if (st_sorted[l]) {
            st_all.update(l, !rev[l] ? st_sorted[l]->val_forward
                                     : st_sorted[l]->val_backward);
        }
        if (st_sorted[k]) {
            st_all.update(k, !rev[k] ? st_sorted[k]->val_forward
                                     : st_sorted[k]->val_backward);
        }
    }
};

#line 2 "data-structure/segtree/sortable_segment_tree.hpp"
#include <memory>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

#line 2 "data-structure/segtree/segment_tree.hpp"
#include <algorithm>
#include <bit>
#line 5 "data-structure/segtree/segment_tree.hpp"

template <typename M>
class SegmentTree {
    using T = M::T;

   public:
    SegmentTree() = default;
    explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, M::id())) {}
    explicit SegmentTree(const std::vector<T>& v)
        : size(std::bit_ceil(v.size())), node(2 * size, M::id()) {
        std::ranges::copy(v, node.begin() + size);
        for (int i = size - 1; i > 0; --i) {
            node[i] = M::op(node[2 * i], node[2 * i + 1]);
        }
    }

    T operator[](int k) const { return node[k + size]; }

    void update(int k, const T& x) {
        k += size;
        node[k] = x;
        while (k >>= 1) node[k] = M::op(node[2 * k], node[2 * k + 1]);
    }

    T fold(int l, int r) const {
        T vl = M::id(), vr = M::id();
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = M::op(vl, node[l++]);
            if (r & 1) vr = M::op(node[--r], vr);
        }
        return M::op(vl, vr);
    }

    template <typename F>
    int find_first(int l, F cond) const {
        T v = M::id();
        for (l += size; l > 0; l >>= 1) {
            if (l & 1) {
                T nv = M::op(v, node[l]);
                if (cond(nv)) {
                    while (l < size) {
                        nv = M::op(v, node[2 * l]);
                        if (cond(nv)) {
                            l = 2 * l;
                        } else {
                            v = nv, l = 2 * l + 1;
                        }
                    }
                    return l + 1 - size;
                }
                v = nv;
                ++l;
            }
        }
        return -1;
    }

    template <typename F>
    int find_last(int r, F cond) const {
        T v = M::id();
        for (r += size; r > 0; r >>= 1) {
            if (r & 1) {
                --r;
                T nv = M::op(node[r], v);
                if (cond(nv)) {
                    while (r < size) {
                        nv = M::op(node[2 * r + 1], v);
                        if (cond(nv)) {
                            r = 2 * r + 1;
                        } else {
                            v = nv, r = 2 * r;
                        }
                    }
                    return r - size;
                }
                v = nv;
            }
        }
        return -1;
    }

   private:
    int size;
    std::vector<T> node;
};
#line 9 "data-structure/segtree/sortable_segment_tree.hpp"

template <typename M>
class SortableSegmentTree {
    using T = M::T;

   public:
    SortableSegmentTree() = default;
    explicit SortableSegmentTree(long long max_key,
                                 const std::vector<std::pair<long long, T>>& kv)
        : n(kv.size()), max_key(max_key), st_all(n), st_sorted(n), rev(n) {
        for (int k = 0; k < n; ++k) {
            auto [key, val] = kv[k];
            st_sorted[k] = std::make_unique<Node>();
            st_sorted[k]->update(key, val, 0, max_key);
            st_all.update(k, val);
            left.insert(k);
        }
        left.insert(n);
    }

    void update(int k, long long key, const T& val) {
        split(k), split(k + 1);
        st_sorted[k] = std::make_unique<Node>();
        st_sorted[k]->update(key, val, 0, max_key);
        st_all.update(k, val);
    }

    T fold(int l, int r) {
        split(l), split(r);
        return st_all.fold(l, r);
    }

    void sort(int l, int r, bool descending = false) {
        if (r - l <= 1) return;
        split(l), split(r);
        auto it = ++left.find(l);
        while (it != left.end() && *it < r) {
            st_sorted[l] =
                join(std::move(st_sorted[l]), std::move(st_sorted[*it]));
            st_all.update(*it, M::id());
            rev[*it] = false;
            it = left.erase(it);
        }
        if (st_sorted[l]) {
            st_all.update(l, !descending ? st_sorted[l]->val_forward
                                         : st_sorted[l]->val_backward);
            rev[l] = descending;
        }
    }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        int sz;
        T val_forward, val_backward;
        node_ptr left, right;
        Node()
            : sz(0),
              val_forward(M::id()),
              val_backward(M::id()),
              left(nullptr),
              right(nullptr) {}

        void recalc() {
            int sl = left ? left->sz : 0;
            int sr = right ? right->sz : 0;
            sz = sl + sr;
            T vl_forward = left ? left->val_forward : M::id();
            T vr_forward = right ? right->val_forward : M::id();
            val_forward = M::op(vl_forward, vr_forward);
            T vl_backward = left ? left->val_backward : M::id();
            T vr_backward = right ? right->val_backward : M::id();
            val_backward = M::op(vr_backward, vl_backward);
        }

        void update(long long key, const T& x, long long l, long long r) {
            if (r - l == 1) {
                sz = 1;
                val_forward = val_backward = x;
                return;
            }
            long long m = std::midpoint(l, r);
            if (key < m) {
                if (!left) left = std::make_unique<Node>();
                left->update(key, x, l, m);
            } else {
                if (!right) right = std::make_unique<Node>();
                right->update(key, x, m, r);
            }
            recalc();
        }
    };

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        if (k == 0) return {nullptr, std::move(t)};
        if (k == t->sz) return {std::move(t), nullptr};
        int szl = t->left ? t->left->sz : 0;
        auto t2 = std::make_unique<Node>();
        if (k < szl) {
            std::tie(t2->left, t->left) = split(std::move(t->left), k);
            std::swap(t, t2);
        } else {
            std::tie(t->right, t2->right) = split(std::move(t->right), k - szl);
        }
        t->recalc(), t2->recalc();
        return {std::move(t), std::move(t2)};
    }

    static node_ptr join(node_ptr t1, node_ptr t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        t1->left = join(std::move(t1->left), std::move(t2->left));
        t1->right = join(std::move(t1->right), std::move(t2->right));
        t1->recalc();
        return t1;
    }

    int n;
    long long max_key;
    std::set<int> left;
    SegmentTree<M> st_all;
    std::vector<node_ptr> st_sorted;
    std::vector<bool> rev;

    void split(int k) {
        int l = *--left.upper_bound(k);
        if (l == k) return;
        if (!rev[l]) {
            std::tie(st_sorted[l], st_sorted[k]) =
                split(std::move(st_sorted[l]), k - l);
        } else {
            std::tie(st_sorted[k], st_sorted[l]) =
                split(std::move(st_sorted[l]), l + st_sorted[l]->sz - k);
            rev[k] = true;
        }
        left.insert(k);
        if (st_sorted[l]) {
            st_all.update(l, !rev[l] ? st_sorted[l]->val_forward
                                     : st_sorted[l]->val_backward);
        }
        if (st_sorted[k]) {
            st_all.update(k, !rev[k] ? st_sorted[k]->val_forward
                                     : st_sorted[k]->val_backward);
        }
    }
};

Back to top page