test/verify/yosupo-range-linear-add-range-min.test.cpp

• View this file on GitHub
• Last update: 2024-07-28 19:56:12+09:00
• Problem: https://judge.yosupo.jp/problem/range_linear_add_range_min

Depends on

• Range Linear Add Range Min Segment Tree (structure/segment-tree/range-linear-add-range-min-segment-tree.hpp)
• template/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_linear_add_range_min

#include "../../template/template.hpp"

#include "../../structure/segment-tree/range-linear-add-range-min-segment-tree.hpp"

int main() {
  int n, q;
  cin >> n >> q;
  vector< int64 > as(n);
  for (auto &a: as) cin >> a;
  RangeLinearAddRangeMinSegmentTree< int64, int64, __int128_t > seg(as, infll);
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 0) {
      int b, c;
      cin >> b >> c;
      seg.apply(l, r, b, c);
    } else {
      cout << seg.prod(l, r) << "\n";
    }
  }
}

#line 1 "test/verify/yosupo-range-linear-add-range-min.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_linear_add_range_min

#line 1 "template/template.hpp"
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
  t = v;
}

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
  for (auto &e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F &&f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
inline decltype(auto) MFP(F &&f) {
  return FixPoint<F>{std::forward<F>(f)};
}
#line 4 "test/verify/yosupo-range-linear-add-range-min.test.cpp"

#line 1 "structure/segment-tree/range-linear-add-range-min-segment-tree.hpp"
template <typename T, typename T2, typename T3>
struct RangeLinearAddRangeMinSegmentTree {
 private:
  using Point = pair<int, T>;

  struct Node {
    Point lbr, rbr;

    T lza, lzb;

    Node(int x, T y) : lbr{x, y}, rbr{x, y}, lza{0}, lzb{0} {}

    Node() : lza{0}, lzb{0} {}
  };

#define x first
#define y second

  static constexpr T2 cross(const Point &a, const Point &b, const Point &c) {
    return T2(b.y - a.y) * (c.x - a.x) - T2(c.y - a.y) * (b.x - a.x);
  }

  size_t n, sz, height;
  const T ti;
  vector<int> mid;
  vector<Node> seg;

  void update(int k) {
    int l = 2 * k, r = 2 * k + 1;
    int split_x = mid[r];
    propagate(k);
    Point a = seg[l].lbr;
    Point b = seg[l].rbr;
    Point c = seg[r].lbr;
    Point d = seg[r].rbr;
    T lza_l = 0, lzb_l = 0, lza_r = 0, lzb_r = 0;
    auto move_left = [&](bool f) {
      lza_l += seg[l].lza;
      lzb_l += seg[l].lzb;
      l = l * 2 + f;
      a = seg[l].lbr;
      b = seg[l].rbr;
      a.y += lza_l * a.x + lzb_l;
      b.y += lza_l * b.x + lzb_l;
    };
    auto move_right = [&](bool f) {
      lza_r += seg[r].lza;
      lzb_r += seg[r].lzb;
      r = r * 2 + f;
      c = seg[r].lbr;
      d = seg[r].rbr;
      c.y += lza_r * c.x + lzb_r;
      d.y += lza_r * d.x + lzb_r;
    };
    while (l < sz or r < sz) {
      T3 s1 = cross(a, b, c);
      if (l < sz and s1 > 0) {
        move_left(0);
      } else if (r < sz and cross(b, c, d) > 0) {
        move_right(1);
      } else if (l >= sz) {
        move_right(0);
      } else if (r >= sz) {
        move_left(1);
      } else {
        T3 s2 = cross(b, a, d);
        if (s1 + s2 == 0 or s1 * (d.x - split_x) < s2 * (split_x - c.x)) {
          move_left(1);
        } else {
          move_right(0);
        }
      }
    }
    seg[k].lbr = a;
    seg[k].rbr = c;
  }

  void all_apply(int k, T a, T b) {
    seg[k].lbr.y += a * seg[k].lbr.x + b;
    seg[k].rbr.y += a * seg[k].rbr.x + b;
    if (k < sz) seg[k].lza += a, seg[k].lzb += b;
  }

  void propagate(int k) {
    if (seg[k].lza != 0 or seg[k].lzb != 0) {
      all_apply(2 * k, seg[k].lza, seg[k].lzb);
      all_apply(2 * k + 1, seg[k].lza, seg[k].lzb);
      seg[k].lza = seg[k].lzb = 0;
    }
  }

  T min_subtree(int k) {
    T a = 0, b = 0;
    while (k < sz) {
      bool f =
          (seg[k].lbr.y - seg[k].rbr.y) > a * (seg[k].rbr.x - seg[k].lbr.x);
      a += seg[k].lza;
      b += seg[k].lzb;
      k = k * 2 + f;
    }
    return seg[k].lbr.y + a * seg[k].lbr.x + b;
  }

 public:
  explicit RangeLinearAddRangeMinSegmentTree(const vector<T> &vs, const T &ti)
      : n(vs.size()), ti(ti) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    seg.resize(2 * sz);
    mid.resize(2 * sz);
    for (int k = 0; k < sz; k++) {
      seg[sz + k] = Node(k, k < n ? vs[k] : 0);
      mid[sz + k] = k;
    }
    for (int k = sz - 1; k > 0; k--) {
      mid[k] = mid[2 * k];
      update(k);
    }
  }

  T prod(int l, int r) {
    if (l >= r) return ti;
    l += sz;
    r += sz;
    for (int i = height; i > 0; i--) {
      if (((l >> i) << i) != l) propagate(l >> i);
      if (((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    T res = ti;
    while (l < r) {
      if (l & 1) res = min(res, min_subtree(l++));
      if (r & 1) res = min(res, min_subtree(--r));
      l >>= 1;
      r >>= 1;
    }
    return res;
  }

  void apply(int l, int r, T a, T b) {
    if (l >= r) return;
    l += sz;
    r += sz;
    for (int i = height; i > 0; i--) {
      if (((l >> i) << i) != l) propagate(l >> i);
      if (((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) all_apply(l++, a, b);
        if (r & 1) all_apply(--r, a, b);
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= height; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

#undef x
#undef y
};
#line 6 "test/verify/yosupo-range-linear-add-range-min.test.cpp"

int main() {
  int n, q;
  cin >> n >> q;
  vector< int64 > as(n);
  for (auto &a: as) cin >> a;
  RangeLinearAddRangeMinSegmentTree< int64, int64, __int128_t > seg(as, infll);
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 0) {
      int b, c;
      cin >> b >> c;
      seg.apply(l, r, b, c);
    } else {
      cout << seg.prod(l, r) << "\n";
    }
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_t0_00	AC	565 ms	17 MB
g++	almost_t0_01	AC	554 ms	17 MB
g++	almost_t0_02	AC	562 ms	17 MB
g++	almost_t1_00	AC	125 ms	17 MB
g++	almost_t1_01	AC	126 ms	17 MB
g++	almost_t1_02	AC	129 ms	17 MB
g++	example_00	AC	5 ms	3 MB
g++	max_random_00	AC	360 ms	17 MB
g++	max_random_01	AC	356 ms	17 MB
g++	max_random_02	AC	356 ms	17 MB
g++	random_00	AC	182 ms	7 MB
g++	random_01	AC	81 ms	17 MB
g++	random_02	AC	191 ms	10 MB
g++	small_00	AC	6 ms	3 MB
g++	small_01	AC	5 ms	3 MB
g++	small_02	AC	5 ms	3 MB
g++	small_03	AC	5 ms	3 MB
g++	small_04	AC	5 ms	3 MB
g++	small_05	AC	5 ms	3 MB
g++	small_06	AC	5 ms	3 MB
g++	small_07	AC	5 ms	3 MB
g++	small_08	AC	5 ms	3 MB
g++	small_09	AC	5 ms	3 MB
g++	small_random_00	AC	6 ms	4 MB
g++	small_random_01	AC	6 ms	4 MB
g++	width_almost_n_00	AC	224 ms	17 MB
g++	width_almost_n_01	AC	223 ms	17 MB
g++	width_almost_n_02	AC	218 ms	17 MB
clang++	almost_t0_00	AC	603 ms	17 MB
clang++	almost_t0_01	AC	587 ms	17 MB
clang++	almost_t0_02	AC	590 ms	17 MB
clang++	almost_t1_00	AC	141 ms	17 MB
clang++	almost_t1_01	AC	140 ms	17 MB
clang++	almost_t1_02	AC	138 ms	17 MB
clang++	example_00	AC	6 ms	3 MB
clang++	max_random_00	AC	370 ms	17 MB
clang++	max_random_01	AC	378 ms	17 MB
clang++	max_random_02	AC	374 ms	17 MB
clang++	random_00	AC	192 ms	7 MB
clang++	random_01	AC	81 ms	17 MB
clang++	random_02	AC	197 ms	10 MB
clang++	small_00	AC	6 ms	3 MB
clang++	small_01	AC	5 ms	3 MB
clang++	small_02	AC	5 ms	3 MB
clang++	small_03	AC	5 ms	3 MB
clang++	small_04	AC	5 ms	3 MB
clang++	small_05	AC	5 ms	3 MB
clang++	small_06	AC	5 ms	3 MB
clang++	small_07	AC	5 ms	3 MB
clang++	small_08	AC	5 ms	3 MB
clang++	small_09	AC	5 ms	3 MB
clang++	small_random_00	AC	6 ms	4 MB
clang++	small_random_01	AC	6 ms	4 MB
clang++	width_almost_n_00	AC	242 ms	17 MB
clang++	width_almost_n_01	AC	244 ms	17 MB
clang++	width_almost_n_02	AC	239 ms	17 MB

Back to top page