test/yosupo/range_chmin_chmax_add_range_sum.SqrtDC.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum

Depends on

• 典型的な平方分割 (src/DataStructure/SortedPerBucket.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum
// competitive-verifier: TLE 3
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/DataStructure/SortedPerBucket.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<long long> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SortedPerBucket<long long> sqrtdc(a);
 while (Q--) {
  int op, l, r;
  cin >> op >> l >> r;
  if (op == 3) {
   cout << sqrtdc.sum(l, r) << '\n';
  } else {
   long long b;
   cin >> b;
   if (op == 0) sqrtdc.chmin(l, r, b);
   if (op == 1) sqrtdc.chmax(l, r, b);
   if (op == 2) sqrtdc.add(l, r, b);
  }
 }
 return 0;
}

#line 1 "test/yosupo/range_chmin_chmax_add_range_sum.SqrtDC.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum
// competitive-verifier: TLE 3
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/DataStructure/SortedPerBucket.hpp"
#include <limits>
#include <algorithm>
#include <array>
#line 6 "src/DataStructure/SortedPerBucket.hpp"
#include <numeric>
template <class T, size_t B= 700> class SortedPerBucket {
 static constexpr T INF= std::numeric_limits<T>::max() / 2;
 struct Dat {
  const size_t n;
  T a[B], sorted[B], acc[B + 1];
  T add, lb, ub;
  Dat(size_t b): n(b), a{0}, sorted{0}, acc{0}, add(0), lb(-INF), ub(INF) {}
  Dat(const T *bg, size_t b): n(b), a{0}, acc{0}, add(0), lb(-INF), ub(INF) {
   for (int i= n; i--;) a[i]= *(bg + i);
   build();
  }
  inline bool eval() {
   if (add == 0 && lb == -INF && ub == INF) return false;
   for (auto &x: a) x= std::clamp(x, lb, ub) + add;
   return add= 0, lb= -INF, ub= INF, true;
  }
  inline void build() { std::copy_n(a, B, sorted), std::sort(sorted, sorted + n), std::partial_sum(sorted, sorted + n, acc + 1); }
  inline size_t idx(T x) const { return std::lower_bound(sorted, sorted + n, x) - sorted; }
  inline size_t count(T x) const { return x-= add, (x <= lb ? 0 : ub < x ? n : idx(x)); }
  inline T sum() const {
   size_t l= idx(lb), u= idx(ub);
   return acc[u] - acc[l] + lb * l + ub * (n - u) + add * n;
  }
  inline T sum(T x) const {
   if (x-= add; x <= lb) return 0;
   if (ub < x) return sum();
   size_t l= idx(lb), u= idx(x);
   return acc[u] - acc[l] + lb * l + add * u;
  }
  inline T get(size_t k) const { return std::clamp(a[k], lb, ub) + add; }
 };
 const size_t n;
 std::vector<Dat> dat;
 template <class U, class All, class One> inline U prod(size_t l, size_t r, const All &all, const One &one) const {
  U ret= 0;
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (; k < dat[i].n; ++k) ret+= one(dat[i].get(k));
    ++i;
   }
   for (; i < j; ++i) ret+= all(dat[i]);
   for (; m--;) ret+= one(dat[j].get(m));
  } else
   for (; k < m; ++k) ret+= one(dat[i].get(k));
  return ret;
 }
 template <class All, class One> inline void update(size_t l, size_t r, const All &all, const One &one) {
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (dat[i].eval(); k < dat[i].n; k++) one(dat[i].a[k]);
    dat[i].build(), ++i;
   }
   for (; i < j; ++i) all(dat[i]);
   if (m) {
    for (dat[j].eval(); m--;) one(dat[j].a[m]);
    dat[j].build();
   }
  } else {
   for (dat[i].eval(); k < m; ++k) one(dat[i].a[k]);
   dat[i].build();
  }
 }
public:
 SortedPerBucket(size_t n): n(n) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(r - l);
 }
 SortedPerBucket(const std::vector<T> &a): n(a.size()) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(a.data() + l, r - l);
 }
 // count i s.t. (l <= i < r) && (a[i] < ub)
 size_t count(size_t l, size_t r, T ub) const {
  return prod<size_t>(l, r, [&](const Dat &d) { return d.count(ub); }, [&](T x) { return x < ub; });
 }
 // count i s.t. (l <= i < r) && (lb <= a[i] < ub)
 size_t count(size_t l, size_t r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
 // sum a[i] s.t. (l <= i < r)
 T sum(size_t l, size_t r) const {
  return prod<T>(l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
 }
 // sum a[i] s.t. (l <= i < r) && (a[i] < ub)
 T sum(size_t l, size_t r, T ub) const {
  return prod<T>(l, r, [&](const Dat &d) { return d.sum(ub); }, [&](T x) { return x < ub ? x : 0; });
 }
 // sum a[i] s.t. (l <= i < r)  && (lb <= a[i] < ub)
 T sum(size_t l, size_t r, T lb, T ub) const { return sum(l, r, ub) - sum(l, r, lb); }
 void set(size_t k, T x) {
  size_t i= k / B, j= k % B;
  dat[i].eval(), dat[i].a[j]= x, dat[i].build();
 }
 T get(size_t k) const { return dat[k / B].get(k % B); }
 T operator[](size_t k) const { return get(k); }
 void add(size_t l, size_t r, T v) {
  update(l, r, [&](Dat &d) { d.add+= v; }, [&](T &x) { x+= v; });
 }
 void chmin(size_t l, size_t r, T ub) {
  auto f= [&](Dat &d) {
   T b= ub - d.add;
   d.ub= std::min(d.ub, b), d.lb= std::min(d.lb, b);
  };
  update(l, r, f, [&](T &x) { x= std::min(x, ub); });
 }
 void chmax(size_t l, size_t r, T lb) {
  auto f= [&](Dat &d) {
   T a= lb - d.add;
   d.lb= std::max(d.lb, a), d.ub= std::max(d.ub, a);
  };
  update(l, r, f, [&](T &x) { x= std::max(x, lb); });
 }
 void chclamp(size_t l, size_t r, T lb, T ub) {
  auto f= [&](Dat &d) {
   T a= lb - d.add, b= ub - d.add;
   d.ub= std::clamp(d.ub, a, b), d.lb= std::clamp(d.lb, a, b);
  };
  update(l, r, f, [&](T &x) { x= std::clamp(x, lb, ub); });
 }
};
#line 7 "test/yosupo/range_chmin_chmax_add_range_sum.SqrtDC.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<long long> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SortedPerBucket<long long> sqrtdc(a);
 while (Q--) {
  int op, l, r;
  cin >> op >> l >> r;
  if (op == 3) {
   cout << sqrtdc.sum(l, r) << '\n';
  } else {
   long long b;
   cin >> b;
   if (op == 0) sqrtdc.chmin(l, r, b);
   if (op == 1) sqrtdc.chmax(l, r, b);
   if (op == 2) sqrtdc.add(l, r, b);
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	max_random_00	AC	1796 ms	15 MB
g++-13	max_random_01	AC	1808 ms	15 MB
g++-13	max_random_02	AC	1797 ms	15 MB
g++-13	medium_00	AC	11 ms	4 MB
g++-13	medium_01	AC	6 ms	4 MB
g++-13	medium_02	AC	6 ms	4 MB
g++-13	random2_00	AC	1688 ms	14 MB
g++-13	random2_01	AC	1694 ms	14 MB
g++-13	random2_02	AC	1701 ms	15 MB
g++-13	random3_00	AC	2264 ms	15 MB
g++-13	random3_01	AC	2271 ms	14 MB
g++-13	random3_02	AC	2261 ms	15 MB
g++-13	random_00	AC	1290 ms	10 MB
g++-13	random_01	AC	1315 ms	9 MB
g++-13	random_02	AC	1001 ms	6 MB
g++-13	small_00	AC	5 ms	4 MB
g++-13	small_01	AC	4 ms	4 MB
g++-13	small_02	AC	4 ms	4 MB
g++-13	small_03	AC	4 ms	4 MB
g++-13	small_04	AC	4 ms	4 MB
g++-13	small_05	AC	4 ms	4 MB
g++-13	small_06	AC	4 ms	4 MB
g++-13	small_07	AC	4 ms	4 MB
g++-13	small_08	AC	4 ms	4 MB
g++-13	small_09	AC	4 ms	4 MB
g++-13	small_absolute_values_00	AC	1279 ms	9 MB
g++-13	small_absolute_values_01	AC	1299 ms	9 MB
g++-13	small_absolute_values_02	AC	984 ms	6 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	max_random_00	AC	1437 ms	14 MB
clang++-18	max_random_01	AC	1435 ms	14 MB
clang++-18	max_random_02	AC	1438 ms	14 MB
clang++-18	medium_00	AC	10 ms	4 MB
clang++-18	medium_01	AC	6 ms	4 MB
clang++-18	medium_02	AC	6 ms	4 MB
clang++-18	random2_00	AC	1402 ms	13 MB
clang++-18	random2_01	AC	1415 ms	14 MB
clang++-18	random2_02	AC	1408 ms	15 MB
clang++-18	random3_00	AC	1823 ms	15 MB
clang++-18	random3_01	AC	1821 ms	15 MB
clang++-18	random3_02	AC	1822 ms	15 MB
clang++-18	random_00	AC	1018 ms	10 MB
clang++-18	random_01	AC	1040 ms	9 MB
clang++-18	random_02	AC	776 ms	6 MB
clang++-18	small_00	AC	5 ms	4 MB
clang++-18	small_01	AC	4 ms	4 MB
clang++-18	small_02	AC	4 ms	4 MB
clang++-18	small_03	AC	4 ms	4 MB
clang++-18	small_04	AC	4 ms	4 MB
clang++-18	small_05	AC	4 ms	4 MB
clang++-18	small_06	AC	4 ms	4 MB
clang++-18	small_07	AC	4 ms	4 MB
clang++-18	small_08	AC	4 ms	4 MB
clang++-18	small_09	AC	4 ms	4 MB
clang++-18	small_absolute_values_00	AC	1009 ms	10 MB
clang++-18	small_absolute_values_01	AC	1030 ms	10 MB
clang++-18	small_absolute_values_02	AC	763 ms	7 MB

Back to top page