This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: STANDALONE
#include "../../dp/range-weighted-longest-increasing-subsequence.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <random>
#include <string>
#include <vector>
template <typename T, typename Weight>
void check_all_ranges(const std::vector<T>& values,
const std::vector<Weight>& weights) {
const int n = (int)values.size();
const RangeWeightedLongestIncreasingSubsequence<T, Weight> lis(values,
weights);
for (int left = n; left >= 0; --left) {
Weight expected{};
std::vector<Weight> dp(n);
for (int right = left; right <= n; ++right) {
if (left < right) {
const int last = right - 1;
Weight predecessor{};
for (int j = left; j < last; ++j) {
if (values[j] < values[last] && predecessor < dp[j]) {
predecessor = dp[j];
}
}
dp[last] = predecessor + weights[last];
if (expected < dp[last]) expected = dp[last];
}
const auto actual = lis.prod(left, right);
assert(!(actual < expected) && !(expected < actual));
const auto indices = lis.restore(left, right);
Weight total{};
int previous = left - 1;
for (int index : indices) {
assert(left <= index && index < right);
assert(previous < index);
if (previous >= left) assert(values[previous] < values[index]);
total = total + weights[index];
previous = index;
}
assert(!(total < expected) && !(expected < total));
assert(indices.empty() == (left == right));
}
}
// Revisit early versions after querying later right endpoints.
for (int right = n; right > 0; --right) {
const auto indices = lis.restore(right - 1, right);
assert((indices == std::vector<int>{right - 1}));
}
}
void check(const std::vector<int>& values,
const std::vector<long long>& weights) {
check_all_ranges(values, weights);
}
struct OrderedValue {
int value;
friend bool operator<(const OrderedValue& a, const OrderedValue& b) {
return a.value < b.value;
}
};
struct ExactWeight {
long long value;
explicit ExactWeight(long long value = 0) : value(value) {}
friend ExactWeight operator+(const ExactWeight& a, const ExactWeight& b) {
return ExactWeight(a.value + b.value);
}
friend bool operator<(const ExactWeight& a, const ExactWeight& b) {
return a.value < b.value;
}
};
void check_unit_weights(const std::vector<int>& values) {
const int n = (int)values.size();
const RangeWeightedLongestIncreasingSubsequence<int> lis(values);
for (int left = 0; left <= n; ++left) {
std::vector<int> tails;
for (int right = left; right <= n; ++right) {
if (left < right) {
int value = values[right - 1];
auto it = std::lower_bound(tails.begin(), tails.end(), value);
if (it == tails.end()) {
tails.push_back(value);
} else {
*it = value;
}
}
assert(lis.prod(left, right) == (long long)tails.size());
const auto indices = lis.restore(left, right);
assert(indices.size() == tails.size());
for (int j = 0; j < (int)indices.size(); ++j) {
assert(left <= indices[j] && indices[j] < right);
if (j) {
assert(indices[j - 1] < indices[j]);
assert(values[indices[j - 1]] < values[indices[j]]);
}
}
}
}
}
int main() {
check({}, {});
check({5}, {7});
check({1, 1}, {5, 1});
check({1, 1}, {1, 5});
check({7, 7, 7, 7, 7}, {3, 9, 1, 9, 2});
check({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5});
check({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5});
check({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1});
check({0, 2, 3, 1}, {1, 1, 1, 1});
check({3, 1, 2}, {100, 1, 1});
check({3, 1, 2, 3, 2, 4, 1}, {2, 1, 5, 2, 10, 1, 7});
check({2, 0, 3, 1, 4, 2, 5, 3, 6}, {1, 9, 2, 8, 3, 7, 4, 6, 5});
check({std::numeric_limits<int>::max(), std::numeric_limits<int>::min(),
std::numeric_limits<int>::min(), 0, std::numeric_limits<int>::max()},
{1, 2, 3, 4, 5});
check({0, 1, 2, 3, 4},
std::vector<long long>(5, std::numeric_limits<long long>::max() / 5));
check_all_ranges<int, std::uint64_t>(
{2, 0, 1, 3},
{4000000000ULL, 3000000000ULL, 2000000000ULL, 1000000000ULL});
check_all_ranges<std::string, long long>({"b", "a", "b", "aa", "c"},
{2, 4, 7, 6, 1});
check_all_ranges<OrderedValue, ExactWeight>(
{{2}, {1}, {1}, {3}, {0}, {4}},
{ExactWeight(3), ExactWeight(4), ExactWeight(2), ExactWeight(5),
ExactWeight(8), ExactWeight(1)});
// Exhaust all sequences of length at most five over three values and two
// positive weights, including duplicates and equal optimum scores.
for (int n = 0, count = 1; n <= 5; ++n, count *= 6) {
for (int code = 0; code < count; ++code) {
std::vector<int> values(n);
std::vector<long long> weights(n);
int remaining = code;
for (int i = 0; i < n; ++i) {
values[i] = remaining % 3;
weights[i] = remaining / 3 % 2 + 1;
remaining /= 6;
}
check(values, weights);
}
}
std::mt19937 random(123456789);
for (int n = 0; n <= 40; ++n) {
for (int trial = 0; trial < 10; ++trial) {
std::vector<int> values(n);
std::vector<long long> weights(n);
for (int i = 0; i < n; ++i) {
values[i] = (int)(random() % 17) - 8;
weights[i] = random() % 1000000000 + 1;
}
check(values, weights);
if (trial == 0) check_unit_weights(values);
}
}
// A long optimum exercises witness expansion without recursive traversal of
// a potentially very deep concatenation tree.
const int n = 16384;
std::vector<int> increasing(n);
std::iota(increasing.begin(), increasing.end(), 0);
const RangeWeightedLongestIncreasingSubsequence<int> lis(increasing);
for (int left : {0, 1, 123, n / 2, n - 1, n}) {
assert(lis.prod(left, n) == n - left);
const auto indices = lis.restore(left, n);
assert((int)indices.size() == n - left);
for (int i = 0; i < (int)indices.size(); ++i)
assert(indices[i] == left + i);
}
assert(lis.prod(3, 113) == 110);
const auto early = lis.restore(3, 113);
assert(early.front() == 3 && early.back() == 112 && early.size() == 110);
}
#line 1 "test/unittest/range-weighted-longest-increasing-subsequence.test.cpp"
// competitive-verifier: STANDALONE
#line 2 "dp/range-weighted-longest-increasing-subsequence.hpp"
#include <algorithm>
#include <cassert>
#include <deque>
#include <numeric>
#include <utility>
#include <vector>
template <typename T, typename Weight = long long>
struct RangeWeightedLongestIncreasingSubsequence {
private:
struct Witness {
Weight weight;
int left, right;
};
struct Node {
Weight last;
int left, right, suffix;
};
// Delay copying a function root until the view is retained in the result.
struct View {
int root, suffix;
};
int n;
// Segmented storage avoids reallocating and copying the entire node pool.
std::deque<Witness> witnesses;
std::deque<Node> nodes;
std::vector<int> roots;
int concatenate(int left, int right) {
if (left == 0) return right;
if (right == 0) return left;
witnesses.push_back(
{witnesses[left].weight + witnesses[right].weight, left, right});
return (int)witnesses.size() - 1;
}
int append(int root, int suffix) {
if (suffix == 0) return root;
// Copy the root to keep every saved version immutable.
Node node = nodes[root];
node.last = node.last + witnesses[suffix].weight;
node.suffix = concatenate(node.suffix, suffix);
nodes.push_back(node);
return (int)nodes.size() - 1;
}
Weight last(View view) const {
return nodes[view.root].last + witnesses[view.suffix].weight;
}
int materialize(View view) { return append(view.root, view.suffix); }
std::pair<View, View> children(View view) {
Node node = nodes[view.root];
int suffix = concatenate(node.suffix, view.suffix);
return {{node.left, suffix}, {node.right, suffix}};
}
int join(int left, int right) {
if (left == 0 && right == 0) return 0;
nodes.push_back({nodes[right].last, left, right, 0});
return (int)nodes.size() - 1;
}
int prefix_append(View view, int end, int suffix, int left, int right) {
if (end <= left) return materialize(view);
if (right <= end) {
return append(view.root, concatenate(view.suffix, suffix));
}
auto [a, b] = children(view);
int mid = left + (right - left) / 2;
if (end <= mid) {
return join(prefix_append(a, end, suffix, left, mid), materialize(b));
}
int updated = append(a.root, concatenate(a.suffix, suffix));
return join(updated, prefix_append(b, end, suffix, mid, right));
}
// f's endpoint values precede g's. The strict comparison g > f holds
// on a prefix, so only the half containing its boundary needs recursion.
View merge_view(View f, View g, int left, int right) {
if ((f.root == g.root && f.suffix == g.suffix) ||
(g.root == 0 && g.suffix == 0)) {
return f;
}
if ((f.root == 0 && f.suffix == 0) || last(f) < last(g)) {
return g;
}
if (left + 1 == right) return f;
// Equal children mean the two functions differ only by a constant suffix
// weight. This also stops at constant intervals, without expanding them.
if (nodes[f.root].left == nodes[g.root].left &&
nodes[f.root].right == nodes[g.root].right) {
return f;
}
auto [fl, fr] = children(f);
auto [gl, gr] = children(g);
int mid = left + (right - left) / 2;
// Reuse the original view when both halves select the same input.
if (last(fl) < last(gl)) {
View result = merge_view(fr, gr, mid, right);
if (result.root == gr.root && result.suffix == gr.suffix) return g;
return {join(materialize(gl), materialize(result)), 0};
}
View result = merge_view(fl, gl, left, mid);
if (result.root == fl.root && result.suffix == fl.suffix) return f;
return {join(materialize(result), materialize(fr)), 0};
}
int merge(View f, View g, int left, int right) {
return materialize(merge_view(f, g, left, right));
}
public:
RangeWeightedLongestIncreasingSubsequence(const std::vector<T>& a,
const std::vector<Weight>& w)
: n((int)a.size()), roots(n + 1, 0) {
assert(a.size() == w.size());
// Handle zero represents an empty witness / an all-zero function on any
// interval. Passing interval bounds preserves the common subdivision.
witnesses.push_back({Weight{}, 0, 0});
nodes.push_back({Weight{}, 0, 0, 0});
if (n == 0) return;
std::vector<int> order(n), rank(n);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int i, int j) {
if (a[i] < a[j]) return true;
if (a[j] < a[i]) return false;
// Equal values cannot extend a strictly increasing sequence.
return i > j;
});
for (int i = 0; i < n; ++i) rank[order[i]] = i;
int size = 1;
while (size < n) size <<= 1;
std::vector<int> outer(2 * size, 0), latest(2 * size, -1);
for (int i = 0; i < n; ++i) {
assert(Weight{} < w[i]);
int predecessor = 0, predecessor_latest = -1;
// Canonical intervals are visited from right to left; prepend each
// lower-value envelope to keep merge arguments in value order.
for (int k = size + rank[i]; k > 1; k >>= 1) {
if (k & 1) {
// A later endpoint in the higher-value set can extend every
// lower-value witness, so that envelope already dominates.
if (predecessor_latest < latest[k - 1]) {
predecessor = merge({outer[k - 1], 0}, {predecessor, 0}, 0, n);
predecessor_latest = latest[k - 1];
}
}
}
witnesses.push_back({w[i], 0, i});
int endpoint = prefix_append({predecessor, 0}, i + 1,
(int)witnesses.size() - 1, 0, n);
int k = size + rank[i];
outer[k] = endpoint;
latest[k] = i;
while (k > 1) {
if (k & 1) {
// The newest endpoint is in the right set. Every left-set witness
// can append it, so the right envelope dominates the left envelope.
outer[k >> 1] = outer[k];
} else {
outer[k >> 1] = merge({outer[k], 0}, {outer[k + 1], 0}, 0, n);
}
k >>= 1;
latest[k] = i;
}
roots[i + 1] = outer[1];
}
}
explicit RangeWeightedLongestIncreasingSubsequence(const std::vector<T>& a)
: RangeWeightedLongestIncreasingSubsequence(
a, std::vector<Weight>(a.size(), Weight{1})) {}
Weight prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
Weight result{};
if (l == r) return result;
int root = roots[r], left = 0, right = n;
while (root != 0) {
const Node& node = nodes[root];
result = result + witnesses[node.suffix].weight;
if (left + 1 == right) break;
int mid = left + (right - left) / 2;
if (l < mid) {
root = node.left;
right = mid;
} else {
root = node.right;
left = mid;
}
}
return result;
}
std::vector<int> restore(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
std::vector<int> result, pending;
if (l == r) return result;
int root = roots[r], left = 0, right = n;
while (root != 0) {
const Node& node = nodes[root];
if (node.suffix != 0) pending.push_back(node.suffix);
if (left + 1 == right) break;
int mid = left + (right - left) / 2;
if (l < mid) {
root = node.left;
right = mid;
} else {
root = node.right;
left = mid;
}
}
// Expand suffixes from leaf to root, each concatenation left to right.
// Witness trees can have linear depth, so expansion must be iterative.
while (!pending.empty()) {
int id = pending.back();
pending.pop_back();
const Witness& witness = witnesses[id];
if (witness.left == 0) {
result.push_back(witness.right);
} else {
pending.push_back(witness.right);
pending.push_back(witness.left);
}
}
return result;
}
};
#line 4 "test/unittest/range-weighted-longest-increasing-subsequence.test.cpp"
#line 7 "test/unittest/range-weighted-longest-increasing-subsequence.test.cpp"
#include <cstdint>
#include <limits>
#line 10 "test/unittest/range-weighted-longest-increasing-subsequence.test.cpp"
#include <random>
#include <string>
#line 13 "test/unittest/range-weighted-longest-increasing-subsequence.test.cpp"
template <typename T, typename Weight>
void check_all_ranges(const std::vector<T>& values,
const std::vector<Weight>& weights) {
const int n = (int)values.size();
const RangeWeightedLongestIncreasingSubsequence<T, Weight> lis(values,
weights);
for (int left = n; left >= 0; --left) {
Weight expected{};
std::vector<Weight> dp(n);
for (int right = left; right <= n; ++right) {
if (left < right) {
const int last = right - 1;
Weight predecessor{};
for (int j = left; j < last; ++j) {
if (values[j] < values[last] && predecessor < dp[j]) {
predecessor = dp[j];
}
}
dp[last] = predecessor + weights[last];
if (expected < dp[last]) expected = dp[last];
}
const auto actual = lis.prod(left, right);
assert(!(actual < expected) && !(expected < actual));
const auto indices = lis.restore(left, right);
Weight total{};
int previous = left - 1;
for (int index : indices) {
assert(left <= index && index < right);
assert(previous < index);
if (previous >= left) assert(values[previous] < values[index]);
total = total + weights[index];
previous = index;
}
assert(!(total < expected) && !(expected < total));
assert(indices.empty() == (left == right));
}
}
// Revisit early versions after querying later right endpoints.
for (int right = n; right > 0; --right) {
const auto indices = lis.restore(right - 1, right);
assert((indices == std::vector<int>{right - 1}));
}
}
void check(const std::vector<int>& values,
const std::vector<long long>& weights) {
check_all_ranges(values, weights);
}
struct OrderedValue {
int value;
friend bool operator<(const OrderedValue& a, const OrderedValue& b) {
return a.value < b.value;
}
};
struct ExactWeight {
long long value;
explicit ExactWeight(long long value = 0) : value(value) {}
friend ExactWeight operator+(const ExactWeight& a, const ExactWeight& b) {
return ExactWeight(a.value + b.value);
}
friend bool operator<(const ExactWeight& a, const ExactWeight& b) {
return a.value < b.value;
}
};
void check_unit_weights(const std::vector<int>& values) {
const int n = (int)values.size();
const RangeWeightedLongestIncreasingSubsequence<int> lis(values);
for (int left = 0; left <= n; ++left) {
std::vector<int> tails;
for (int right = left; right <= n; ++right) {
if (left < right) {
int value = values[right - 1];
auto it = std::lower_bound(tails.begin(), tails.end(), value);
if (it == tails.end()) {
tails.push_back(value);
} else {
*it = value;
}
}
assert(lis.prod(left, right) == (long long)tails.size());
const auto indices = lis.restore(left, right);
assert(indices.size() == tails.size());
for (int j = 0; j < (int)indices.size(); ++j) {
assert(left <= indices[j] && indices[j] < right);
if (j) {
assert(indices[j - 1] < indices[j]);
assert(values[indices[j - 1]] < values[indices[j]]);
}
}
}
}
}
int main() {
check({}, {});
check({5}, {7});
check({1, 1}, {5, 1});
check({1, 1}, {1, 5});
check({7, 7, 7, 7, 7}, {3, 9, 1, 9, 2});
check({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5});
check({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5});
check({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1});
check({0, 2, 3, 1}, {1, 1, 1, 1});
check({3, 1, 2}, {100, 1, 1});
check({3, 1, 2, 3, 2, 4, 1}, {2, 1, 5, 2, 10, 1, 7});
check({2, 0, 3, 1, 4, 2, 5, 3, 6}, {1, 9, 2, 8, 3, 7, 4, 6, 5});
check({std::numeric_limits<int>::max(), std::numeric_limits<int>::min(),
std::numeric_limits<int>::min(), 0, std::numeric_limits<int>::max()},
{1, 2, 3, 4, 5});
check({0, 1, 2, 3, 4},
std::vector<long long>(5, std::numeric_limits<long long>::max() / 5));
check_all_ranges<int, std::uint64_t>(
{2, 0, 1, 3},
{4000000000ULL, 3000000000ULL, 2000000000ULL, 1000000000ULL});
check_all_ranges<std::string, long long>({"b", "a", "b", "aa", "c"},
{2, 4, 7, 6, 1});
check_all_ranges<OrderedValue, ExactWeight>(
{{2}, {1}, {1}, {3}, {0}, {4}},
{ExactWeight(3), ExactWeight(4), ExactWeight(2), ExactWeight(5),
ExactWeight(8), ExactWeight(1)});
// Exhaust all sequences of length at most five over three values and two
// positive weights, including duplicates and equal optimum scores.
for (int n = 0, count = 1; n <= 5; ++n, count *= 6) {
for (int code = 0; code < count; ++code) {
std::vector<int> values(n);
std::vector<long long> weights(n);
int remaining = code;
for (int i = 0; i < n; ++i) {
values[i] = remaining % 3;
weights[i] = remaining / 3 % 2 + 1;
remaining /= 6;
}
check(values, weights);
}
}
std::mt19937 random(123456789);
for (int n = 0; n <= 40; ++n) {
for (int trial = 0; trial < 10; ++trial) {
std::vector<int> values(n);
std::vector<long long> weights(n);
for (int i = 0; i < n; ++i) {
values[i] = (int)(random() % 17) - 8;
weights[i] = random() % 1000000000 + 1;
}
check(values, weights);
if (trial == 0) check_unit_weights(values);
}
}
// A long optimum exercises witness expansion without recursive traversal of
// a potentially very deep concatenation tree.
const int n = 16384;
std::vector<int> increasing(n);
std::iota(increasing.begin(), increasing.end(), 0);
const RangeWeightedLongestIncreasingSubsequence<int> lis(increasing);
for (int left : {0, 1, 123, n / 2, n - 1, n}) {
assert(lis.prod(left, n) == n - left);
const auto indices = lis.restore(left, n);
assert((int)indices.size() == n - left);
for (int i = 0; i < (int)indices.size(); ++i)
assert(indices[i] == left + i);
}
assert(lis.prod(3, 113) == 110);
const auto early = lis.restore(3, 113);
assert(early.front() == 3 && early.back() == 112 && early.size() == 110);
}