Luzhiled's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub ei1333/library

:heavy_check_mark: test/unittest/range-weighted-longest-increasing-subsequence.test.cpp

Depends on

Code

// 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);
}
Back to top page