#include <bits/stdc++.h>
using namespace std;
template <class T, class F, int N>
class SegmentTree_ {
private:
int n;
T st[4 * N];
F lz[4 * N];
void push_down(int id) {
for (int j : {0, 1}) {
st[id << 1 | j] += lz[id];
lz[id << 1 | j] += lz[id];
}
lz[id] = F::ZERO();
}
void build(int id, int l, int r, int64_t arr[]) {
lz[id] = F::ZERO();
if (l == r) {
st[id] = T(arr[l], l);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m, arr);
build(id << 1 | 1, m + 1, r, arr);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int id, int l, int r, int left, int right, F f) {
if (r < left or right < l)
return;
if (left <= l and r <= right) {
st[id] += f;
lz[id] += f;
return;
}
push_down(id);
int m = (l + r) >> 1;
update(id << 1, l, m, left, right, f);
update(id << 1 | 1, m + 1, r, left, right, f);
st[id] = st[id << 1] + st[id << 1 | 1];
}
T get(int id, int l, int r, int left, int right) {
if (r < left or right < l)
return T::ZERO();
if (left <= l and r <= right)
return st[id];
push_down(id);
int m = (l + r) >> 1;
return get(id << 1, l, m, left, right) + get(id << 1 | 1, m + 1, r, left, right);
}
public:
void init(int _n, int64_t arr[]) {
n = _n;
build(1, 1, n, arr);
}
void update(int left, int right, F f) { update(1, 1, n, left, right, f); }
T get(int left, int right) { return get(1, 1, n, left, right); }
};
struct F_ {
bool _is_set;
int64_t da, db;
F_(bool __is_set = false, int64_t _da = 0, int64_t _db = 0) {
_is_set = __is_set;
da = _da, db = _db;
}
inline bool is_set() { return _is_set; }
inline bool is_add() { return not _is_set; }
static F_ ADD(int64_t da, int64_t db) { return F_(false, da, db); }
static F_ UPDATE(int64_t da, int64_t db) { return F_(true, da, db); }
static F_ ZERO() { return F_(); }
F_ operator + (const F_& oth) const {
if (oth._is_set) return oth;
return F_(_is_set, da + oth.da, db + oth.db);
}
void operator += (const F_& oth) { (*this) = (*this) + oth; }
};
struct T_ {
// y = a * i + b
int64_t sum_i = 0, sum_a = 0, sum_b = 0, sum_ai = 0;
int left_i, right_i;
int64_t val_first = 0, val_last = 0;
int64_t diff_first = 0, diff_last = 0;
int best_len_prefix = 0, best_len_suffix = 0, best_len = 0;
T_(int64_t val = 0, int64_t i = 0) {
left_i = right_i = i;
sum_i = i;
sum_a = 0;
sum_b = val;
sum_ai = 0;
val_first = val_last = val;
best_len_prefix = best_len_suffix = best_len = 1;
}
static T_ ZERO() { return T_(); }
inline bool is_single() const { return left_i == right_i; }
inline int len() const { return right_i - left_i + 1; }
void print() const {
cerr
<< "| range: "
<< setw(3) << left_i
<< setw(3) << right_i
<< "| sums: "
<< setw(4) << sum_i
<< setw(4) << sum_a
<< setw(4) << sum_b
<< setw(4) << sum_ai
<< "| vals: "
<< setw(4) << val_first
<< setw(4) << val_last
<< "| diffs: "
<< setw(4) << diff_first
<< setw(4) << diff_last
<< "| best_lens: "
<< setw(3) << best_len_prefix
<< setw(3) << best_len_suffix
<< setw(3) << best_len
<< endl;
}
T_ operator + (const T_& right) {
T_ res;
T_& left = *this;
res.sum_i = left.sum_i + right.sum_i;
res.sum_a = left.sum_a + right.sum_a;
res.sum_b = left.sum_b + right.sum_b;
res.sum_ai = left.sum_ai + right.sum_ai;
res.left_i = left.left_i;
res.right_i = right.right_i;
res.val_first = left.val_first;
res.val_last = right.val_last;
int64_t mid_diff = right.val_first - left.val_last;
res.diff_first = ( left.is_single()) ? mid_diff : left.diff_first;
res.diff_last = (right.is_single()) ? mid_diff : right.diff_last;
auto merge_parts = [&](int p1, int p2, bool cond_p1, bool cond_mid, bool cond_p2) {
int res = p1;
if (not cond_p1 or not cond_mid)
return res;
res += 1;
if (not cond_p2)
return res;
res += p2 - 1;
return res;
};
res.best_len_prefix = merge_parts(
left.best_len_prefix,
right.best_len_prefix,
left.best_len_prefix == left.len(),
mid_diff == left.diff_first or left.is_single(),
mid_diff == right.diff_first or right.is_single()
);
res.best_len_suffix = merge_parts(
right.best_len_suffix,
left.best_len_suffix,
right.best_len_suffix == right.len(),
mid_diff == right.diff_first or right.is_single(),
mid_diff == left.diff_first or left.is_single()
);
res.best_len = max(
max(left.best_len, right.best_len),
max(res.best_len_prefix, res.best_len_suffix)
);
if (left.diff_last == mid_diff)
res.best_len = max(res.best_len, left.best_len_suffix + 1);
if (mid_diff == right.diff_first)
res.best_len = max(res.best_len, right.best_len_prefix + 1);
if (left.diff_last == mid_diff and mid_diff == right.diff_first)
res.best_len = max(
res.best_len,
left.best_len_suffix + right.best_len_prefix
);
/*
cerr << "==================================" << endl;
cerr << "left: "; left.print();
cerr << "right: "; right.print();
cerr << "-------mid_diff = " << mid_diff << "-----------------" << endl;
cerr << "add: "; res.print();
cerr << "==================================" << endl;
*/
return res;
}
T_ operator + (const F_& f) const {
T_ res = *this;
if (f._is_set) {
res.sum_a = f.da;
res.sum_b = f.db;
res.sum_ai = f.da * res.sum_i;
res.val_first = f.da * res.left_i + f.db;
res.val_last = f.da * res.right_i + f.db;
res.diff_first = f.da;
res.diff_last = f.da;
// Special case due to overwriting!
res.best_len_prefix = res.best_len_suffix = res.best_len = res.len();
}
else {
res.sum_a += f.da;
res.sum_b += f.db;
res.sum_ai += f.da * res.sum_i;
res.val_first += f.da * res.left_i + f.db;
res.val_last += f.da * res.right_i + f.db;
res.diff_first += f.da;
res.diff_last += f.da;
}
return res;
}
void operator += (const F_& oth) { (*this) = (*this) + oth; }
};
template <int N>
using SegmentTree = SegmentTree_<T_, F_, N>;
const int MAX = 3e5 + 7;
int N, Q;
int64_t arr[MAX];
SegmentTree<MAX> st;
void update_1(int l, int r, int64_t s, int64_t c) {
st.update(l, r, F_::ADD(c, s - l * c));
}
void update_2(int l, int r, int64_t s, int64_t c) {
st.update(l, r, F_::UPDATE(c, s - l * c));
}
int64_t evaluate(int l, int r) {
return st.get(l, r).best_len;
}
void print(int l, int r) {
for (int i = l; i <= r; i++) {
T_ node = st.get(i, i);
int64_t x = node.sum_ai + node.sum_b;
cerr << setw(5) << x;
}
cerr << endl;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++)
cin >> arr[i];
st.init(N, arr);
while (Q--) {
int t; cin >> t;
if (t == 1) {
int l, r; int64_t s, c;
cin >> l >> r >> s >> c;
update_1(l, r, s, c);
}
if (t == 2) {
int l, r; int64_t s, c;
cin >> l >> r >> s >> c;
update_2(l, r, s, c);
}
if (t == 3) {
int l, r;
cin >> l >> r;
cout << evaluate(l, r) << '\n';
// print(l, r);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
142920 KB |
Output is correct |
| 2 |
Correct |
76 ms |
137068 KB |
Output is correct |
| 3 |
Correct |
69 ms |
137032 KB |
Output is correct |
| 4 |
Correct |
69 ms |
137128 KB |
Output is correct |
| 5 |
Incorrect |
77 ms |
137232 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
133940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
141148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
637 ms |
144008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
141148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
142920 KB |
Output is correct |
| 2 |
Correct |
76 ms |
137068 KB |
Output is correct |
| 3 |
Correct |
69 ms |
137032 KB |
Output is correct |
| 4 |
Correct |
69 ms |
137128 KB |
Output is correct |
| 5 |
Incorrect |
77 ms |
137232 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
