competitive-programming-library
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
data_structure/segment_tree_beats.DSL_2_G.test.cpp
- View this file on GitHub
- Last update: 2021-08-30 04:35:37+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
Depends on
- Segment Tree Beats (range {chmin, chmax, add, update} + range {min, max, sum}, 完全二分木)
(data_structure/segment_tree_beats.hpp)
- hack/fastio.hpp
- utils/macros.hpp
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"
#include "../data_structure/segment_tree_beats.hpp"
#include <cstdint>
#include <vector>
#include "../utils/macros.hpp"
#include "../hack/fastio.hpp"
int main() {
int n = in<int>();
int q = in<int>();
segment_tree_beats beats(n);
while (q --) {
int ty = in<int>();
int l = in<int>();
int r = in<int>();
-- l;
if (ty == 0) {
int64_t x = in<int64_t>();
beats.range_add(l, r, x);
} else {
int64_t sum = beats.range_sum(l, r);
out<int64_t>(sum);
out<char>('\n');
}
}
return 0;
}#line 1 "data_structure/segment_tree_beats.DSL_2_G.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"
#line 2 "data_structure/segment_tree_beats.hpp"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 8 "data_structure/segment_tree_beats.hpp"
/**
* @brief Segment Tree Beats (range {chmin, chmax, add, update} + range {min, max, sum}, 完全二分木)
* @docs data_structure/segment_tree_beats.md
* @see https://codeforces.com/blog/entry/57319
*/
class segment_tree_beats {
// MEMO: values for queries (max, min, lazy_add, and lazy_update) already apply to the current node; but not for children
typedef struct {
int64_t max;
int64_t max_second;
int max_count;
int64_t min;
int64_t min_second;
int min_count;
int64_t lazy_add;
int64_t lazy_update;
int64_t sum;
} value_type;
int n;
std::vector<value_type> a;
public:
segment_tree_beats() = default;
segment_tree_beats(int n_) {
n = 1; while (n < n_) n *= 2;
a.resize(2 * n - 1);
tag<UPDATE>(0, 0);
}
template <class InputIterator>
segment_tree_beats(InputIterator first, InputIterator last) {
int n_ = std::distance(first, last);
n = 1; while (n < n_) n *= 2;
a.resize(2 * n - 1);
REP (i, n_) {
tag<UPDATE>(n - 1 + i, *(first + i));
}
REP3 (i, n_, n) {
tag<UPDATE>(n - 1 + i, 0);
}
REP_R (i, n - 1) {
update(i);
}
}
void range_chmin(int l, int r, int64_t value) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
range_apply<CHMIN>(0, 0, n, l, r, value);
}
void range_chmax(int l, int r, int64_t value) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
range_apply<CHMAX>(0, 0, n, l, r, value);
}
void range_add(int l, int r, int64_t value) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
range_apply<ADD>(0, 0, n, l, r, value);
}
void range_update(int l, int r, int64_t value) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
range_apply<UPDATE>(0, 0, n, l, r, value);
}
int64_t range_min(int l, int r) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
return range_get<MIN>(0, 0, n, l, r);
}
int64_t range_max(int l, int r) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
return range_get<MAX>(0, 0, n, l, r);
}
int64_t range_sum(int l, int r) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
return range_get<SUM>(0, 0, n, l, r);
}
private:
static constexpr char CHMIN = 0;
static constexpr char CHMAX = 1;
static constexpr char ADD = 2;
static constexpr char UPDATE = 3;
static constexpr char MIN = 10;
static constexpr char MAX = 11;
static constexpr char SUM = 12;
template <char TYPE>
void range_apply(int i, int il, int ir, int l, int r, int64_t g) {
if (ir <= l or r <= il or break_condition<TYPE>(i, g)) {
// break
} else if (l <= il and ir <= r and tag_condition<TYPE>(i, g)) {
tag<TYPE>(i, g);
} else {
pushdown(i);
range_apply<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r, g);
range_apply<TYPE>(2 * i + 2, (il + ir) / 2, ir, l, r, g);
update(i);
}
}
template <char TYPE>
inline bool break_condition(int i, int64_t g) {
switch (TYPE) {
case CHMIN: return a[i].max <= g;
case CHMAX: return g <= a[i].min;
case ADD: return false;
case UPDATE: return false;
default: assert (false);
}
}
template <char TYPE>
inline bool tag_condition(int i, int64_t g) {
switch (TYPE) {
case CHMIN: return a[i].max_second < g and g < a[i].max;
case CHMAX: return a[i].min < g and g < a[i].min_second;
case ADD: return true;
case UPDATE: return true;
default: assert (false);
}
}
template <char TYPE>
inline void tag(int i, int64_t g) {
int length = n >> (32 - __builtin_clz(i + 1) - 1);
if (TYPE == CHMIN) {
if (a[i].max == a[i].min or g <= a[i].min) {
tag<UPDATE>(i, g);
return;
}
if (a[i].max != INT64_MIN) {
a[i].sum -= a[i].max * a[i].max_count;
}
a[i].max = g;
a[i].min_second = std::min(a[i].min_second, g);
if (a[i].lazy_update != INT64_MAX) {
a[i].lazy_update = std::min(a[i].lazy_update, g);
}
a[i].sum += g * a[i].max_count;
} else if (TYPE == CHMAX) {
if (a[i].max == a[i].min or a[i].max <= g) {
tag<UPDATE>(i, g);
return;
}
if (a[i].min != INT64_MAX) {
a[i].sum -= a[i].min * a[i].min_count;
}
a[i].min = g;
a[i].max_second = std::max(a[i].max_second, g);
if (a[i].lazy_update != INT64_MAX) {
a[i].lazy_update = std::max(a[i].lazy_update, g);
}
a[i].sum += g * a[i].min_count;
} else if (TYPE == ADD) {
if (a[i].max != INT64_MAX) {
a[i].max += g;
}
if (a[i].max_second != INT64_MIN) {
a[i].max_second += g;
}
if (a[i].min != INT64_MIN) {
a[i].min += g;
}
if (a[i].min_second != INT64_MAX) {
a[i].min_second += g;
}
a[i].lazy_add += g;
if (a[i].lazy_update != INT64_MAX) {
a[i].lazy_update += g;
}
a[i].sum += g * length;
} else if (TYPE == UPDATE) {
a[i].max = g;
a[i].max_second = INT64_MIN;
a[i].max_count = length;
a[i].min = g;
a[i].min_second = INT64_MAX;
a[i].min_count = length;
a[i].lazy_add = 0;
a[i].lazy_update = INT64_MAX;
a[i].sum = g * length;
} else {
assert (false);
}
}
void pushdown(int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
// update
if (a[i].lazy_update != INT64_MAX) {
tag<UPDATE>(l, a[i].lazy_update);
tag<UPDATE>(r, a[i].lazy_update);
a[i].lazy_update = INT64_MAX;
return;
}
// add
if (a[i].lazy_add != 0) {
tag<ADD>(l, a[i].lazy_add);
tag<ADD>(r, a[i].lazy_add);
a[i].lazy_add = 0;
}
// chmin
if (a[i].max < a[l].max) {
tag<CHMIN>(l, a[i].max);
}
if (a[i].max < a[r].max) {
tag<CHMIN>(r, a[i].max);
}
// chmax
if (a[l].min < a[i].min) {
tag<CHMAX>(l, a[i].min);
}
if (a[r].min < a[i].min) {
tag<CHMAX>(r, a[i].min);
}
}
void update(int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
// chmin
std::vector<int64_t> b { a[l].max, a[l].max_second, a[r].max, a[r].max_second };
std::sort(b.rbegin(), b.rend());
b.erase(std::unique(ALL(b)), b.end());
a[i].max = b[0];
a[i].max_second = b[1];
a[i].max_count = (b[0] == a[l].max ? a[l].max_count : 0) + (b[0] == a[r].max ? a[r].max_count : 0);
// chmax
std::vector<int64_t> c { a[l].min, a[l].min_second, a[r].min, a[r].min_second };
std::sort(ALL(c));
c.erase(std::unique(ALL(c)), c.end());
a[i].min = c[0];
a[i].min_second = c[1];
a[i].min_count = (c[0] == a[l].min ? a[l].min_count : 0) + (c[0] == a[r].min ? a[r].min_count : 0);
// add
a[i].lazy_add = 0;
// update
a[i].lazy_update = INT64_MAX;
// sum
a[i].sum = a[l].sum + a[r].sum;
}
template <char TYPE>
int64_t range_get(int i, int il, int ir, int l, int r) {
if (ir <= l or r <= il) {
switch (TYPE) {
case MIN: return INT64_MAX;
case MAX: return INT64_MIN;
case SUM: return 0;
default: assert (false);
}
} else if (l <= il and ir <= r) {
// base
switch (TYPE) {
case MIN: return a[i].min;
case MAX: return a[i].max;
case SUM: return a[i].sum;
default: assert (false);
}
} else {
pushdown(i);
int64_t value_l = range_get<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r);
int64_t value_r = range_get<TYPE>(2 * i + 2, (il + ir) / 2, ir, l, r);
// mult
switch (TYPE) {
case MIN: return std::min(value_l, value_r);
case MAX: return std::max(value_l, value_r);
case SUM: return value_l + value_r;
default: assert (false);
}
}
}
};
#line 3 "data_structure/segment_tree_beats.DSL_2_G.test.cpp"
#line 3 "hack/fastio.hpp"
#include <cstdio>
#include <string>
#include <type_traits>
template <class Char, std::enable_if_t<std::is_same_v<Char, char>, int> = 0>
inline Char in() { return getchar_unlocked(); }
template <class String, std::enable_if_t<std::is_same_v<String, std::string>, int> = 0>
inline std::string in() {
char c; do { c = getchar_unlocked(); } while (isspace(c));
std::string s;
do { s.push_back(c); } while (not isspace(c = getchar_unlocked()));
return s;
}
template <class Integer, std::enable_if_t<std::is_integral_v<Integer> and not std::is_same_v<Integer, char>, int> = 0>
inline Integer in() {
char c; do { c = getchar_unlocked(); } while (isspace(c));
if (std::is_signed<Integer>::value and c == '-') return -in<Integer>();
Integer n = 0;
do { n = n * 10 + c - '0'; } while (not isspace(c = getchar_unlocked()));
return n;
}
template <class Char, std::enable_if_t<std::is_same_v<Char, char>, int> = 0>
inline void out(char c) { putchar_unlocked(c); }
template <class String, std::enable_if_t<std::is_same_v<String, std::string>, int> = 0>
inline void out(const std::string & s) { for (char c : s) putchar_unlocked(c); }
template <class Integer, std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
inline void out(Integer n) {
char s[20];
int i = 0;
if (std::is_signed<Integer>::value and n < 0) { putchar_unlocked('-'); n *= -1; }
do { s[i ++] = n % 10; n /= 10; } while (n);
while (i) putchar_unlocked(s[-- i] + '0');
}
#line 8 "data_structure/segment_tree_beats.DSL_2_G.test.cpp"
int main() {
int n = in<int>();
int q = in<int>();
segment_tree_beats beats(n);
while (q --) {
int ty = in<int>();
int l = in<int>();
int r = in<int>();
-- l;
if (ty == 0) {
int64_t x = in<int64_t>();
beats.range_add(l, r, x);
} else {
int64_t sum = beats.range_sum(l, r);
out<int64_t>(sum);
out<char>('\n');
}
}
return 0;
}