ds/index_compression.hpp

• View this file on GitHub
• Last update: 2026-08-01 03:11:36+09:00
• Include: #include "ds/index_compression.hpp"

Required by

• ds/offline_query/coefficient_query_2d.hpp
• ds/offline_query/rectangle_add_rectangle_sum.hpp
• ds/wavelet_matrix/wavelet_matrix_2d_range.hpp
• string/basic_substring_structure.hpp
• string/lex_max_suffix_for_all_prefix.hpp
• string/longest_common_substring.hpp
• string/many_string_compare.hpp
• string/sort_substrings.hpp
• string/substring_shortest_border.hpp
• string/suffix_array.hpp
• string/suffix_lcp_change.hpp
• string/suffix_tree.hpp

Verified with

• test/1_mytest/index_compression.test.cpp
• test/1_mytest/lex_minmax_suffix.test.cpp
• test/1_mytest/longest_common_substr.test.cpp
• test/1_mytest/suffix_lcp_change.test.cpp
• test/2_library_checker/data_structure/point_add_rectangle_sum_wm_abel.test.cpp
• test/2_library_checker/data_structure/point_add_rectangle_sum_wm_mono.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_cf2d.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm_abel.test.cpp
• test/2_library_checker/data_structure/static_rectangle_add_rectangle_sum.test.cpp
• test/2_library_checker/string/longest_common_substring.test.cpp
• test/2_library_checker/string/number_of_substrings.test.cpp
• test/2_library_checker/string/suffix_array.test.cpp
• test/2_library_checker/string/suffix_array_vec.test.cpp
• test/3_yukicoder/1490.test.cpp
• test/3_yukicoder/1600_2.test.cpp
• test/3_yukicoder/1625_2.test.cpp
• test/3_yukicoder/1919_2.test.cpp
• test/3_yukicoder/2361.test.cpp
• test/3_yukicoder/2859.test.cpp

Code

template <typename T>
struct Index_Compression_DISTINCT_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<int> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1]++;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi]++;
    }
    FOR_R(i, 1, len(dat)) dat[i] = dat[i - 1];
    dat[0] = 0;
    return X;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_SAME_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<T> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1] = 1;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi];
    }
    return X;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_SAME_LARGE {
  vc<T> dat;
  vc<int> build(const vc<T>& X) {
    dat.reserve(len(X));
    vc<pair<T, int>> tmp(len(X));
    FOR(i, len(X)) tmp[i] = {X[i], i};
    sort(all(tmp));
    vc<int> ANS(len(X));
    for (auto [x, j] : tmp) {
      if (dat.empty() || dat.back() != x) dat.eb(x);
      ANS[j] = len(dat) - 1;
    }
    return ANS;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return LB(dat, x); }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_DISTINCT_LARGE {
  vc<T> dat;
  vc<int> build(vc<T> X) {
    dat.reserve(len(X));
    vc<pair<T, int>> tmp(len(X));
    FOR(i, len(X)) tmp[i] = {X[i], i};
    sort(all(tmp));
    vc<int> ANS(len(X));
    for (auto [x, j] : tmp) {
      dat.eb(x);
      ANS[j] = len(dat) - 1;
    }
    return ANS;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return LB(dat, x); }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T, bool SMALL>
using Index_Compression_DISTINCT =
    typename std::conditional<SMALL, Index_Compression_DISTINCT_SMALL<T>,
                              Index_Compression_DISTINCT_LARGE<T>>::type;
template <typename T, bool SMALL>
using Index_Compression_SAME =
    typename std::conditional<SMALL, Index_Compression_SAME_SMALL<T>,
                              Index_Compression_SAME_LARGE<T>>::type;

// SAME: [2,3,2] -> [0,1,0]
// DISTINCT: [2,2,3] -> [0,2,1]
// build で列を圧縮してくれる. そのあと
// (x): lower_bound(X,x) をかえす
template <typename T, bool SAME, bool SMALL>
using Index_Compression =
    typename std::conditional<SAME, Index_Compression_SAME<T, SMALL>,
                              Index_Compression_DISTINCT<T, SMALL>>::type;

#line 1 "ds/index_compression.hpp"
template <typename T>
struct Index_Compression_DISTINCT_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<int> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1]++;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi]++;
    }
    FOR_R(i, 1, len(dat)) dat[i] = dat[i - 1];
    dat[0] = 0;
    return X;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_SAME_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<T> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1] = 1;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi];
    }
    return X;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_SAME_LARGE {
  vc<T> dat;
  vc<int> build(const vc<T>& X) {
    dat.reserve(len(X));
    vc<pair<T, int>> tmp(len(X));
    FOR(i, len(X)) tmp[i] = {X[i], i};
    sort(all(tmp));
    vc<int> ANS(len(X));
    for (auto [x, j] : tmp) {
      if (dat.empty() || dat.back() != x) dat.eb(x);
      ANS[j] = len(dat) - 1;
    }
    return ANS;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return LB(dat, x); }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T>
struct Index_Compression_DISTINCT_LARGE {
  vc<T> dat;
  vc<int> build(vc<T> X) {
    dat.reserve(len(X));
    vc<pair<T, int>> tmp(len(X));
    FOR(i, len(X)) tmp[i] = {X[i], i};
    sort(all(tmp));
    vc<int> ANS(len(X));
    for (auto [x, j] : tmp) {
      dat.eb(x);
      ANS[j] = len(dat) - 1;
    }
    return ANS;
  }
  int size() const { return len(dat); }
  int val_to_idx(T x) const { return LB(dat, x); }
  int idx_to_val(int i) const { return dat[i]; }
};

template <typename T, bool SMALL>
using Index_Compression_DISTINCT =
    typename std::conditional<SMALL, Index_Compression_DISTINCT_SMALL<T>,
                              Index_Compression_DISTINCT_LARGE<T>>::type;
template <typename T, bool SMALL>
using Index_Compression_SAME =
    typename std::conditional<SMALL, Index_Compression_SAME_SMALL<T>,
                              Index_Compression_SAME_LARGE<T>>::type;

// SAME: [2,3,2] -> [0,1,0]
// DISTINCT: [2,2,3] -> [0,2,1]
// build で列を圧縮してくれる. そのあと
// (x): lower_bound(X,x) をかえす
template <typename T, bool SAME, bool SMALL>
using Index_Compression =
    typename std::conditional<SAME, Index_Compression_SAME<T, SMALL>,
                              Index_Compression_DISTINCT<T, SMALL>>::type;

Back to top page