range_product_changes.hpp¶
按左端点枚举区间积的连续变化段，记录每段首次出现的右端点；支持结合运算，常用于 gcd、按位与、按位或。
\[
\displaystyle p_{l,r}=a_l\circ a_{l+1}\circ\cdots\circ a_{r-1}
\]
Complexity: Time: \(O(n + S)\) operation/equality calls, where \(S\) is the number of returned runs. Space: \(O(1)\) auxiliary values, excluding \(O(n + S)\) output.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + S) operation/equality calls, where S is the number
/// of returned runs. Space: O(1) auxiliary values, excluding O(n + S) output.
#include <utility>
#include <vector>
namespace noya {
/// @brief Compress consecutive equal products for each left endpoint.
/// The operation must be associative. Nonconsecutive repeated values are kept.
/// @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>>> res(N);
for (int l = N - 1; l >= 0; --l) {
auto &cur = res[l];
cur.reserve(l + 1 < N ? res[l + 1].size() + 1 : 1);
cur.emplace_back(l + 1, A[l]);
if (l + 1 == N) continue;
for (const auto &[r, prd] : res[l + 1]) {
T ext = op(A[l], prd);
if (!(cur.back().second == ext)) cur.emplace_back(r, std::move(ext));
}
}
return res;
}
} // namespace noya
// NOYA_RANGE_PRODUCT_CHANGES_HPP
#ifndef NOYA_RANGE_PRODUCT_CHANGES_HPP
#define NOYA_RANGE_PRODUCT_CHANGES_HPP 1
/// @complexity Time: O(n + S) operation/equality calls, where S is the number
/// of returned runs. Space: O(1) auxiliary values, excluding O(n + S) output.
#include <utility>
#include <vector>
namespace noya {
/// @brief Compress consecutive equal products for each left endpoint.
/// The operation must be associative. Nonconsecutive repeated values are kept.
/// @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>>> res(N);
for (int l = N - 1; l >= 0; --l) {
auto &cur = res[l];
cur.reserve(l + 1 < N ? res[l + 1].size() + 1 : 1);
cur.emplace_back(l + 1, A[l]);
if (l + 1 == N) continue;
for (const auto &[r, prd] : res[l + 1]) {
T ext = op(A[l], prd);
if (!(cur.back().second == ext)) cur.emplace_back(r, std::move(ext));
}
}
return res;
}
} // namespace noya
#endif // NOYA_RANGE_PRODUCT_CHANGES_HPP
/// @complexity Time: O(n + S) operation/equality calls, where S is the number
/// of returned runs. Space: O(1) auxiliary values, excluding O(n + S) output.
#include <utility>
#include <vector>
namespace noya {
/// @brief Compress consecutive equal products for each left endpoint.
/// The operation must be associative. Nonconsecutive repeated values are kept.
/// @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>>> res(N);
for (int l = N - 1; l >= 0; --l) {
auto &cur = res[l];
cur.reserve(l + 1 < N ? res[l + 1].size() + 1 : 1);
cur.emplace_back(l + 1, A[l]);
if (l + 1 == N) continue;
for (const auto &[r, prd] : res[l + 1]) {
T ext = op(A[l], prd);
if (!(cur.back().second == ext)) cur.emplace_back(r, std::move(ext));
}
}
return res;
}
} // namespace noya
// NOYA_RANGE_PRODUCT_CHANGES_HPP