Skip to content

range_set_range_product.hpp

SECTIONData Structure INCLUDEnoya/range_set_range_product.hpp

支持区间赋成同一个值，并查询区间上的非交换乘积；适合矩阵或函数复合等有顺序的聚合。

Complexity: Time: O(n) construction and O(log n) per range assignment or ordered range product. Space: O(n).

AC 记录：range_set_range_composite。

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n) construction and O(log n) per range assignment or
/// ordered range product.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Segment tree for assigning one value to a range and taking an
/// ordered monoid product. For every assigned value, powers for all segment
/// lengths are cached in a circular table. Lazy nodes refer to those cached
/// powers, so a full-cover assignment is constant time and no idempotence or
/// commutativity is required from the monoid.
template <class S, auto op, auto e> struct range_set_range_product {
  int n = 0;
  int sz = 1;
  int log = 0;
  int ptr = 0;
  std::vector<int> lz;
  std::vector<int> len;
  std::vector<S> pw;
  std::vector<S> prd;

  range_set_range_product() = default;
  explicit range_set_range_product(const std::vector<S> &a) {
    build(a);
  }

  void build(const std::vector<S> &a) {
    n = int(a.size());
    sz = 1;
    log = 0;
    while (sz < std::max(1, n)) {
      sz <<= 1;
      log++;
    }
    ptr = 0;
    lz.assign(sz, -1);
    len.assign(sz * 2, sz);
    for (int u = sz - 1; u >= 1; u--) {
      len[u] = len[u << 1] >> 1;
    }
    pw.assign(sz * 2, e());
    prd.assign(sz * 2, e());
    for (int i = 0; i < n; i++) {
      prd[sz + i] = a[i];
    }
    for (int u = sz - 1; u >= 1; u--) {
      prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
    }
  }

  void assign(int l, int r, S val) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return;
    }
    int tag = ptr++;
    if (ptr == sz * 2) {
      ptr = 0;
    }
    pw[index(tag - sz)] = val;
    for (int h = 1; h <= log; h++) {
      val = op(val, val);
      pw[index(tag - (sz >> h))] = val;
    }
    assign_rec(l, r, tag, 1, 0, sz);
    propagate_path(bit_reverse(tag & (sz - 1)));
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    return l == r ? e() : prod_rec(l, r, 1, 0, sz);
  }

private:
  int index(int val) const { return val & (sz * 2 - 1); }

  int bit_reverse(int val) const {
    int res = 0;
    for (int bit = 0; bit < log; bit++) {
      res = (res << 1) | (val & 1);
      val >>= 1;
    }
    return res;
  }

  void apply(int u, int tag) {
    if (u < sz) {
      lz[u] = tag;
    }
    prd[u] = pw[index(tag - len[u])];
  }

  void push(int u) {
    if (u >= sz || lz[u] == -1) {
      return;
    }
    apply(u << 1, lz[u]);
    apply(u << 1 | 1, lz[u]);
    lz[u] = -1;
  }

  void propagate_path(int pos) {
    pos += sz;
    for (int h = log; h >= 1; h--) {
      push(pos >> h);
    }
  }

  void assign_rec(int l, int r, int tag, int u, int low, int hi) {
    if (hi <= l || r <= low) {
      return;
    }
    if (l <= low && hi <= r) {
      apply(u, tag);
      return;
    }
    push(u);
    int mid = (low + hi) / 2;
    assign_rec(l, r, tag, u << 1, low, mid);
    assign_rec(l, r, tag, u << 1 | 1, mid, hi);
    prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
  }

  S prod_rec(int l, int r, int u, int low, int hi) {
    if (l <= low && hi <= r) {
      return prd[u];
    }
    push(u);
    int mid = (low + hi) / 2;
    if (r <= mid) {
      return prod_rec(l, r, u << 1, low, mid);
    }
    if (mid <= l) {
      return prod_rec(l, r, u << 1 | 1, mid, hi);
    }
    return op(prod_rec(l, r, u << 1, low, mid),
              prod_rec(l, r, u << 1 | 1, mid, hi));
  }
};

} // namespace noya

#ifndef NOYA_RANGE_SET_RANGE_PRODUCT_HPP
#define NOYA_RANGE_SET_RANGE_PRODUCT_HPP 1

/// @complexity Time: O(n) construction and O(log n) per range assignment or
/// ordered range product.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Segment tree for assigning one value to a range and taking an
/// ordered monoid product. For every assigned value, powers for all segment
/// lengths are cached in a circular table. Lazy nodes refer to those cached
/// powers, so a full-cover assignment is constant time and no idempotence or
/// commutativity is required from the monoid.
template <class S, auto op, auto e> struct range_set_range_product {
  int n = 0;
  int sz = 1;
  int log = 0;
  int ptr = 0;
  std::vector<int> lz;
  std::vector<int> len;
  std::vector<S> pw;
  std::vector<S> prd;

  range_set_range_product() = default;
  explicit range_set_range_product(const std::vector<S> &a) {
    build(a);
  }

  void build(const std::vector<S> &a) {
    n = int(a.size());
    sz = 1;
    log = 0;
    while (sz < std::max(1, n)) {
      sz <<= 1;
      log++;
    }
    ptr = 0;
    lz.assign(sz, -1);
    len.assign(sz * 2, sz);
    for (int u = sz - 1; u >= 1; u--) {
      len[u] = len[u << 1] >> 1;
    }
    pw.assign(sz * 2, e());
    prd.assign(sz * 2, e());
    for (int i = 0; i < n; i++) {
      prd[sz + i] = a[i];
    }
    for (int u = sz - 1; u >= 1; u--) {
      prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
    }
  }

  void assign(int l, int r, S val) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return;
    }
    int tag = ptr++;
    if (ptr == sz * 2) {
      ptr = 0;
    }
    pw[index(tag - sz)] = val;
    for (int h = 1; h <= log; h++) {
      val = op(val, val);
      pw[index(tag - (sz >> h))] = val;
    }
    assign_rec(l, r, tag, 1, 0, sz);
    propagate_path(bit_reverse(tag & (sz - 1)));
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    return l == r ? e() : prod_rec(l, r, 1, 0, sz);
  }

private:
  int index(int val) const { return val & (sz * 2 - 1); }

  int bit_reverse(int val) const {
    int res = 0;
    for (int bit = 0; bit < log; bit++) {
      res = (res << 1) | (val & 1);
      val >>= 1;
    }
    return res;
  }

  void apply(int u, int tag) {
    if (u < sz) {
      lz[u] = tag;
    }
    prd[u] = pw[index(tag - len[u])];
  }

  void push(int u) {
    if (u >= sz || lz[u] == -1) {
      return;
    }
    apply(u << 1, lz[u]);
    apply(u << 1 | 1, lz[u]);
    lz[u] = -1;
  }

  void propagate_path(int pos) {
    pos += sz;
    for (int h = log; h >= 1; h--) {
      push(pos >> h);
    }
  }

  void assign_rec(int l, int r, int tag, int u, int low, int hi) {
    if (hi <= l || r <= low) {
      return;
    }
    if (l <= low && hi <= r) {
      apply(u, tag);
      return;
    }
    push(u);
    int mid = (low + hi) / 2;
    assign_rec(l, r, tag, u << 1, low, mid);
    assign_rec(l, r, tag, u << 1 | 1, mid, hi);
    prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
  }

  S prod_rec(int l, int r, int u, int low, int hi) {
    if (l <= low && hi <= r) {
      return prd[u];
    }
    push(u);
    int mid = (low + hi) / 2;
    if (r <= mid) {
      return prod_rec(l, r, u << 1, low, mid);
    }
    if (mid <= l) {
      return prod_rec(l, r, u << 1 | 1, mid, hi);
    }
    return op(prod_rec(l, r, u << 1, low, mid),
              prod_rec(l, r, u << 1 | 1, mid, hi));
  }
};

} // namespace noya

#endif // NOYA_RANGE_SET_RANGE_PRODUCT_HPP

#include <algorithm>
#include <cassert>
#include <vector>

/// @complexity Time: O(n) construction and O(log n) per range assignment or
/// ordered range product.
/// Space: O(n).

namespace noya {

/// @brief Segment tree for assigning one value to a range and taking an
/// ordered monoid product. For every assigned value, powers for all segment
/// lengths are cached in a circular table. Lazy nodes refer to those cached
/// powers, so a full-cover assignment is constant time and no idempotence or
/// commutativity is required from the monoid.
template <class S, auto op, auto e> struct range_set_range_product {
  int n = 0;
  int sz = 1;
  int log = 0;
  int ptr = 0;
  std::vector<int> lz;
  std::vector<int> len;
  std::vector<S> pw;
  std::vector<S> prd;

  range_set_range_product() = default;
  explicit range_set_range_product(const std::vector<S> &a) {
    build(a);
  }

  void build(const std::vector<S> &a) {
    n = int(a.size());
    sz = 1;
    log = 0;
    while (sz < std::max(1, n)) {
      sz <<= 1;
      log++;
    }
    ptr = 0;
    lz.assign(sz, -1);
    len.assign(sz * 2, sz);
    for (int u = sz - 1; u >= 1; u--) {
      len[u] = len[u << 1] >> 1;
    }
    pw.assign(sz * 2, e());
    prd.assign(sz * 2, e());
    for (int i = 0; i < n; i++) {
      prd[sz + i] = a[i];
    }
    for (int u = sz - 1; u >= 1; u--) {
      prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
    }
  }

  void assign(int l, int r, S val) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) {
      return;
    }
    int tag = ptr++;
    if (ptr == sz * 2) {
      ptr = 0;
    }
    pw[index(tag - sz)] = val;
    for (int h = 1; h <= log; h++) {
      val = op(val, val);
      pw[index(tag - (sz >> h))] = val;
    }
    assign_rec(l, r, tag, 1, 0, sz);
    propagate_path(bit_reverse(tag & (sz - 1)));
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    return l == r ? e() : prod_rec(l, r, 1, 0, sz);
  }

private:
  int index(int val) const { return val & (sz * 2 - 1); }

  int bit_reverse(int val) const {
    int res = 0;
    for (int bit = 0; bit < log; bit++) {
      res = (res << 1) | (val & 1);
      val >>= 1;
    }
    return res;
  }

  void apply(int u, int tag) {
    if (u < sz) {
      lz[u] = tag;
    }
    prd[u] = pw[index(tag - len[u])];
  }

  void push(int u) {
    if (u >= sz || lz[u] == -1) {
      return;
    }
    apply(u << 1, lz[u]);
    apply(u << 1 | 1, lz[u]);
    lz[u] = -1;
  }

  void propagate_path(int pos) {
    pos += sz;
    for (int h = log; h >= 1; h--) {
      push(pos >> h);
    }
  }

  void assign_rec(int l, int r, int tag, int u, int low, int hi) {
    if (hi <= l || r <= low) {
      return;
    }
    if (l <= low && hi <= r) {
      apply(u, tag);
      return;
    }
    push(u);
    int mid = (low + hi) / 2;
    assign_rec(l, r, tag, u << 1, low, mid);
    assign_rec(l, r, tag, u << 1 | 1, mid, hi);
    prd[u] = op(prd[u << 1], prd[u << 1 | 1]);
  }

  S prod_rec(int l, int r, int u, int low, int hi) {
    if (l <= low && hi <= r) {
      return prd[u];
    }
    push(u);
    int mid = (low + hi) / 2;
    if (r <= mid) {
      return prod_rec(l, r, u << 1, low, mid);
    }
    if (mid <= l) {
      return prod_rec(l, r, u << 1 | 1, mid, hi);
    }
    return op(prod_rec(l, r, u << 1, low, mid),
              prod_rec(l, r, u << 1 | 1, mid, hi));
  }
};

} // namespace noya