range_product_changes.hpp¶
离线回答序列区间乘积在相邻时刻或端点变化时的差异；适合非交换运算下复用大量重叠区间。
\[
\displaystyle p_{l,r}=a_l\circ a_{l+1}\circ\cdots\circ a_{r-1}
\]
Complexity: Time: O(n log A) distinct-product transitions for bounded integer-like values. Space: O(log A) frontier values, excluding output.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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>>> res(N);
std::vector<std::pair<int, T>> cur;
for (int l = N - 1; l >= 0; l--) {
std::vector<std::pair<int, T>> nxt;
nxt.reserve(cur.size() + 1);
for (const auto &[r, prd] : cur) {
T ext = op(A[l], prd);
if (!nxt.empty() && nxt.back().second == ext) {
nxt.back().first = r;
} else {
nxt.emplace_back(r, std::move(ext));
}
}
if (!nxt.empty() && nxt.back().second == A[l]) {
nxt.back().first = l + 1;
} else {
nxt.emplace_back(l + 1, A[l]);
}
cur = std::move(nxt);
res[l] = cur;
std::reverse(res[l].begin(), res[l].end());
}
return res;
}
} // namespace noya
#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>>> res(N);
std::vector<std::pair<int, T>> cur;
for (int l = N - 1; l >= 0; l--) {
std::vector<std::pair<int, T>> nxt;
nxt.reserve(cur.size() + 1);
for (const auto &[r, prd] : cur) {
T ext = op(A[l], prd);
if (!nxt.empty() && nxt.back().second == ext) {
nxt.back().first = r;
} else {
nxt.emplace_back(r, std::move(ext));
}
}
if (!nxt.empty() && nxt.back().second == A[l]) {
nxt.back().first = l + 1;
} else {
nxt.emplace_back(l + 1, A[l]);
}
cur = std::move(nxt);
res[l] = cur;
std::reverse(res[l].begin(), res[l].end());
}
return res;
}
} // 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>>> res(N);
std::vector<std::pair<int, T>> cur;
for (int l = N - 1; l >= 0; l--) {
std::vector<std::pair<int, T>> nxt;
nxt.reserve(cur.size() + 1);
for (const auto &[r, prd] : cur) {
T ext = op(A[l], prd);
if (!nxt.empty() && nxt.back().second == ext) {
nxt.back().first = r;
} else {
nxt.emplace_back(r, std::move(ext));
}
}
if (!nxt.empty() && nxt.back().second == A[l]) {
nxt.back().first = l + 1;
} else {
nxt.emplace_back(l + 1, A[l]);
}
cur = std::move(nxt);
res[l] = cur;
std::reverse(res[l].begin(), res[l].end());
}
return res;
}
} // namespace noya