Skip to content

gcd_maintenance.hpp

#include "noya/gcd_maintenance.hpp"

View on GitHub

#ifndef NOYA_GCD_MAINTENANCE_HPP
#define NOYA_GCD_MAINTENANCE_HPP 1

#include <algorithm>
#include <vector>
namespace noya {

/// @brief For each starting position l, returns the positions where op-product changes.
template <class T, auto op>
std::vector<std::vector<int>> get_suffix(const std::vector<T> &A) {
  int N = int(A.size());
  std::vector<std::vector<int>> position(N);
  std::vector<std::pair<T, int>> cur;
  for (int i = N - 1; i >= 0; i--) {
    T x = A[i];
    if (!cur.empty()) {
      std::vector<std::pair<T, int>> new_cur;
      std::reverse(cur.begin(), cur.end());
      T g = x;
      for (const auto &[value, pos] : cur) {
        g = op(g, value);
        if (new_cur.empty() || new_cur.back().first != g) {
          new_cur.push_back({g, pos});
        }
      }
      cur.swap(new_cur);
      std::reverse(cur.begin(), cur.end());
    }
    cur.push_back({x, i + 1});
    for (const auto &[value, pos] : cur) {
      position[i].push_back(pos);
    }
  }
  return position;
};

/// @brief For each starting position l, returns (position, op-product) pairs.
template <class T, auto op>
std::vector<std::vector<std::pair<int, T>>>
get_suffix_values(const std::vector<T> &A) {
  int N = int(A.size());
  std::vector<std::vector<std::pair<int, T>>> values(N);
  std::vector<std::pair<int, T>> cur;
  for (int i = N - 1; i >= 0; i--) {
    T x = A[i];
    if (!cur.empty()) {
      std::vector<std::pair<int, T>> new_cur;
      std::reverse(cur.begin(), cur.end());
      T g = x;
      for (const auto &[pos, val] : cur) {
        g = op(val, g);
        if (new_cur.empty() || new_cur.back().second != g) {
          new_cur.push_back({pos, g});
        }
      }
      cur.swap(new_cur);
      std::reverse(cur.begin(), cur.end());
    }
    cur.push_back({i + 1, x});
    values[i] = cur;
  }
  return values;
};

} // namespace noya

#endif // NOYA_GCD_MAINTENANCE_HPP

#include <algorithm>
#include <vector>

namespace noya {

/// @brief For each starting position l, returns the positions where op-product changes.
template <class T, auto op>
std::vector<std::vector<int>> get_suffix(const std::vector<T> &A) {
  int N = int(A.size());
  std::vector<std::vector<int>> position(N);
  std::vector<std::pair<T, int>> cur;
  for (int i = N - 1; i >= 0; i--) {
    T x = A[i];
    if (!cur.empty()) {
      std::vector<std::pair<T, int>> new_cur;
      std::reverse(cur.begin(), cur.end());
      T g = x;
      for (const auto &[value, pos] : cur) {
        g = op(g, value);
        if (new_cur.empty() || new_cur.back().first != g) {
          new_cur.push_back({g, pos});
        }
      }
      cur.swap(new_cur);
      std::reverse(cur.begin(), cur.end());
    }
    cur.push_back({x, i + 1});
    for (const auto &[value, pos] : cur) {
      position[i].push_back(pos);
    }
  }
  return position;
};

/// @brief For each starting position l, returns (position, op-product) pairs.
template <class T, auto op>
std::vector<std::vector<std::pair<int, T>>>
get_suffix_values(const std::vector<T> &A) {
  int N = int(A.size());
  std::vector<std::vector<std::pair<int, T>>> values(N);
  std::vector<std::pair<int, T>> cur;
  for (int i = N - 1; i >= 0; i--) {
    T x = A[i];
    if (!cur.empty()) {
      std::vector<std::pair<int, T>> new_cur;
      std::reverse(cur.begin(), cur.end());
      T g = x;
      for (const auto &[pos, val] : cur) {
        g = op(val, g);
        if (new_cur.empty() || new_cur.back().second != g) {
          new_cur.push_back({pos, g});
        }
      }
      cur.swap(new_cur);
      std::reverse(cur.begin(), cur.end());
    }
    cur.push_back({i + 1, x});
    values[i] = cur;
  }
  return values;
};

} // namespace noya