library/util/BubbleNumber.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/util/BubbleNumber.hpp"

Depends on

Code

#pragma once
#include "library/util/InversionNumber.hpp"
template <typename T>
long long bubble_number(const std::vector<T> &v, const std::vector<T> &w) {
    int n = v.size();
    assert(w.size() == n);
    std::map<T, std::queue<int>> mp;
    for (int i = 0; i < n; i++)
        mp[w[i]].push(i);
    std::vector<int> idx(n);
    REP (i, n) {
        if (!mp[v[i]].size())
            return -1;
        idx[i] = mp[v[i]].front();
        mp[v[i]].pop();
    }
    return inversion_number(idx);
}

#line 1 "library/util/InversionNumber.hpp"
#include <atcoder/fenwicktree>

#line 2 "library/util/Compress.hpp"
template <typename T, bool Sentinel = false> class Compress {
    std::vector<T> v;
    bool prepared;

  public:
    Compress() : prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v = {std::numeric_limits<T>::min(), std::numeric_limits<T>::max()};
        }
    }
    Compress(const std::vector<T> &w) : v(w), prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v.push_back(std::numeric_limits<T>::min());
            v.push_back(std::numeric_limits<T>::max());
        }
        build();
    }

    void add(T a) {
        assert(!prepared);
        v.push_back(a);
    }
    void build() {
        assert(!prepared);
        prepared = true;
        std::ranges::sort(v);
        auto result = std::ranges::unique(v);
        v.erase(result.begin(), result.end());
    }

    bool is_prepared() const { return prepared; }

    int operator[](const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        assert(*it == a);
        return std::distance(v.begin(), it);
    }
    int geq(const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int gt(const T &a) const {
        assert(prepared);
        auto it = std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int leq(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int lt(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    T r(int id) const {
        assert(prepared);
        return v[id];
    }
    bool exist(const T &a) const {
        assert(prepared);
        return (*std::ranges::lower_bound(v, a)) == a;
    }
    int size() const { return v.size(); }
    T max() const { return v.back(); }
    T min() const { return v[0]; }

    friend std::ostream &operator<<(std::ostream &os, const Compress &C) {
        for (int i = 0; i < C.v.size(); i++)
            os << C.v[i] << ":" << i << " ";
        return os;
    }
};
#line 4 "library/util/InversionNumber.hpp"

template <typename T> long long inversion_number(const std::vector<T> &v) {
    Compress cmp(v);
    atcoder::fenwick_tree<int> ft(cmp.size());
    long long res = 0;
    for (int i = int(v.size()) - 1; i >= 0; i--) {
        int j = cmp[v[i]];
        res += ft.sum(0, j);
        ft.add(j, 1);
    }
    return res;
}
#line 3 "library/util/BubbleNumber.hpp"
template <typename T>
long long bubble_number(const std::vector<T> &v, const std::vector<T> &w) {
    int n = v.size();
    assert(w.size() == n);
    std::map<T, std::queue<int>> mp;
    for (int i = 0; i < n; i++)
        mp[w[i]].push(i);
    std::vector<int> idx(n);
    REP (i, n) {
        if (!mp[v[i]].size())
            return -1;
        idx[i] = mp[v[i]].front();
        mp[v[i]].pop();
    }
    return inversion_number(idx);
}