range_product_changes.hpp¶
Enumerate the distinct products of ranges sharing a left endpoint.
\[
\displaystyle p_{l,r}=a_l\circ a_{l+1}\circ\cdots\circ a_{r-1}
\]
Implementation¶
#ifndef NOYA_RANGE_PRODUCT_CHANGES_HPP
#define NOYA_RANGE_PRODUCT_CHANGES_HPP 1
/// @complexity Time: O(n log A) distinct-product transitions for bounded integer-like values.
/// Space: O(log A) frontier values, excluding output.
#include <algorithm>
#include <utility>
#include <vector>
namespace noya {
/// @brief Enumerate the distinct products of ranges sharing a left endpoint.
/// @return For every left, pairs (right, product(A[left:right])) at the first
/// right where the product changes, ordered by increasing right.
template <class T, auto op>
std::vector<std::vector<std::pair<int, T>>>
range_product_changes(const std::vector<T> &A) {
const int N = int(A.size());
std::vector<std::vector<std::pair<int, T>>> result(N);
std::vector<std::pair<int, T>> current;
for (int left = N - 1; left >= 0; left--) {
std::vector<std::pair<int, T>> next;
next.reserve(current.size() + 1);
for (const auto &[right, product] : current) {
T extended = op(A[left], product);
if (!next.empty() && next.back().second == extended) {
next.back().first = right;
} else {
next.emplace_back(right, std::move(extended));
}
}
if (!next.empty() && next.back().second == A[left]) {
next.back().first = left + 1;
} else {
next.emplace_back(left + 1, A[left]);
}
current = std::move(next);
result[left] = current;
std::reverse(result[left].begin(), result[left].end());
}
return result;
}
} // namespace noya
#endif // NOYA_RANGE_PRODUCT_CHANGES_HPP
#include <algorithm>
#include <utility>
#include <vector>
/// @complexity Time: O(n log A) distinct-product transitions for bounded integer-like values.
/// Space: O(log A) frontier values, excluding output.
namespace noya {
/// @brief Enumerate the distinct products of ranges sharing a left endpoint.
/// @return For every left, pairs (right, product(A[left:right])) at the first
/// right where the product changes, ordered by increasing right.
template <class T, auto op>
std::vector<std::vector<std::pair<int, T>>>
range_product_changes(const std::vector<T> &A) {
const int N = int(A.size());
std::vector<std::vector<std::pair<int, T>>> result(N);
std::vector<std::pair<int, T>> current;
for (int left = N - 1; left >= 0; left--) {
std::vector<std::pair<int, T>> next;
next.reserve(current.size() + 1);
for (const auto &[right, product] : current) {
T extended = op(A[left], product);
if (!next.empty() && next.back().second == extended) {
next.back().first = right;
} else {
next.emplace_back(right, std::move(extended));
}
}
if (!next.empty() && next.back().second == A[left]) {
next.back().first = left + 1;
} else {
next.emplace_back(left + 1, A[left]);
}
current = std::move(next);
result[left] = current;
std::reverse(result[left].begin(), result[left].end());
}
return result;
}
} // namespace noya