// Author: HolyK
// Created: Wed Nov 3 16:27:37 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(3e5 + 5);
int n, a[N];
#define ls o << 1
#define rs o << 1 | 1
struct SegTreeA {
struct Line {
LL k, b;
Line(LL k = 0, LL b = 0) : k(k), b(b) {}
bool empty() const {
return k == 0 && b == 0;
}
void operator+=(const Line &r) {
k += r.k, b += r.b;
}
LL f(LL x) {
return k * x + b;
}
} t[N << 2], add[N << 2], cov[N << 2];
bool isCov[N << 2];
void applyAdd(int o, const Line &r) {
t[o] += r;
add[o] += r;
}
void applyCov(int o, const Line &r) {
t[o] = r, add[o] = Line(), cov[o] = r;
isCov[o] = true;
}
void pushdown(int o) {
if (isCov[o]) {
applyCov(ls, cov[o]), applyCov(rs, cov[o]);
isCov[o] = false;
}
if (!add[o].empty()) {
applyAdd(ls, add[o]), applyAdd(rs, add[o]);
add[o] = Line();
}
}
void build(int o, int l, int r) {
if (l == r) {
t[o] = Line(0, a[l]);
return;
}
int m = l + r >> 1;
build(ls, l, m), build(rs, m + 1, r);
}
LL ask(int o, int l, int r, int x) {
if (l == r) return t[o].f(l);
int m = l + r >> 1;
pushdown(o);
return x <= m ? ask(ls, l, m, x) : ask(rs, m + 1, r, x);
}
void rangeAdd(int o, int l, int r, int x, int y, const Line &z) {
if (x <= l && r <= y) return applyAdd(o, z);
int m = l + r >> 1;
pushdown(o);
if (x <= m) rangeAdd(ls, l, m, x, y, z);
if (y > m) rangeAdd(rs, m + 1, r, x, y, z);
}
void rangeCov(int o, int l, int r, int x, int y, const Line &z) {
if (x <= l && r <= y) return applyCov(o, z);
int m = l + r >> 1;
pushdown(o);
if (x <= m) rangeCov(ls, l, m, x, y, z);
if (y > m) rangeCov(rs, m + 1, r, x, y, z);
}
} sta;
struct SegTreeB {
struct Info {
int l;
LL x;
friend Info operator+(const Info &a, const Info &b) {
if (a.l > 0 && b.l > 0 && a.x == b.x) return {a.l + b.l, a.x};
return {-1000000000, 0};
}
bool operator<(const Info &r) const {
return l < r.l;
}
void operator+=(LL r) {
x += r;
}
};
struct Node {
Info l, r, t, ans;
int len;
friend Node operator+(const Node &a, const Node &b) {
return {
std::max(a.l, a.t + b.l),
std::max(b.r, b.t + a.r),
a.t + b.t,
std::max({a.ans, b.ans, a.r + b.l}),
a.len + b.len
};
}
} t[N << 2];
LL cov[N << 2], add[N << 2];
bool isCov[N << 2];
void applyCov(int o, LL x) {
t[o].l = t[o].r = t[o].t = t[o].ans = {t[o].len, x};
cov[o] = x;
isCov[o] = true;
add[o] = 0;
}
void applyAdd(int o, LL x) {
t[o].l += x, t[o].r += x, t[o].t += x, t[o].ans += x;
add[o] += x;
}
void pushdown(int o) {
if (isCov[o]) {
applyCov(ls, cov[o]), applyCov(rs, cov[o]);
isCov[o] = false;
}
if (add[o]) {
applyAdd(ls, add[o]), applyAdd(rs, add[o]);
add[o] = 0;
}
}
void pushup(int o) {
t[o] = t[ls] + t[rs];
}
void build(int o, int l, int r) {
t[o].len = r - l + 1;
if (l == r) {
applyCov(o, a[l] - a[l - 1]);
return;
}
int m = l + r >> 1;
build(ls, l, m), build(rs, m + 1, r);
pushup(o);
}
void rangeAdd(int o, int l, int r, int x, int y, LL z) {
if (x <= l && r <= y) return applyAdd(o, z);
int m = l + r >> 1;
pushdown(o);
if (x <= m) rangeAdd(ls, l, m, x, y, z);
if (y > m) rangeAdd(rs, m + 1, r, x, y, z);
pushup(o);
}
void rangeCov(int o, int l, int r, int x, int y, LL z) {
if (x <= l && r <= y) return applyCov(o, z);
int m = l + r >> 1;
pushdown(o);
if (x <= m) rangeCov(ls, l, m, x, y, z);
if (y > m) rangeCov(rs, m + 1, r, x, y, z);
pushup(o);
}
Node ask(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[o];
int m = l + r >> 1;
pushdown(o);
if (y <= m) return ask(ls, l, m, x, y);
if (x > m) return ask(rs, m + 1, r, x, y);
return ask(ls, l, m, x, y) + ask(rs, m + 1, r, x, y);
}
} stb;
int main() {
// freopen("t.in", "r", stdin);
// freopen(".out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int q;
std::cin >> n >> q;
for (int i = 1; i <= n; i++) std::cin >> a[i];
sta.build(1, 1, n);
stb.build(1, 2, n);
// std::cerr << "build end\n";
while (q--) {
int opt, l, r, x, y;
std::cin >> opt >> l >> r;
if (opt == 3) {
std::cout << stb.ask(1, 2, n, l + 1, r).ans.l + 1 << "\n";
} else {
std::cin >> x >> y;
// std::cerr << opt << "\n";
if (opt == 1) {
sta.rangeAdd(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y));
// std::cerr << "rg\n";
stb.rangeAdd(1, 2, n, l + 1, r, y);
} else {
sta.rangeCov(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y));
stb.rangeCov(1, 2, n, l + 1, r, y);
}
#define ask(x) sta.ask(1, 1, n, x)
if (l > 1) {
stb.rangeCov(1, 2, n, l, l, ask(l) - ask(l - 1));
}
if (r < n) {
stb.rangeCov(1, 2, n, r + 1, r + 1, ask(r + 1) - ask(r));
}
// for (int i = 1; i <= n; i++) {
// std::cerr << ask(i) << " \n"[i == n];
// }
#undef ask
}
}
return 0;
}
Compilation message
Progression.cpp: In member function 'void SegTreeA::build(int, int, int)':
Progression.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'LL SegTreeA::ask(int, int, int, int)':
Progression.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeAdd(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeCov(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'void SegTreeB::build(int, int, int)':
Progression.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
160 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeAdd(int, int, int, int, int, LL)':
Progression.cpp:167:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
167 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeCov(int, int, int, int, int, LL)':
Progression.cpp:176:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
176 | int m = l + r >> 1;
| ~~^~~
Progression.cpp: In member function 'SegTreeB::Node SegTreeB::ask(int, int, int, int, int)':
Progression.cpp:185:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
185 | int m = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
190 ms |
153412 KB |
Output is correct |
| 2 |
Correct |
93 ms |
59844 KB |
Output is correct |
| 3 |
Correct |
93 ms |
59848 KB |
Output is correct |
| 4 |
Correct |
96 ms |
59840 KB |
Output is correct |
| 5 |
Correct |
98 ms |
59984 KB |
Output is correct |
| 6 |
Correct |
96 ms |
59972 KB |
Output is correct |
| 7 |
Correct |
97 ms |
59916 KB |
Output is correct |
| 8 |
Runtime error |
68 ms |
114860 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
70 ms |
115524 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
221 ms |
295928 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
240 ms |
297136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
221 ms |
295928 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
190 ms |
153412 KB |
Output is correct |
| 2 |
Correct |
93 ms |
59844 KB |
Output is correct |
| 3 |
Correct |
93 ms |
59848 KB |
Output is correct |
| 4 |
Correct |
96 ms |
59840 KB |
Output is correct |
| 5 |
Correct |
98 ms |
59984 KB |
Output is correct |
| 6 |
Correct |
96 ms |
59972 KB |
Output is correct |
| 7 |
Correct |
97 ms |
59916 KB |
Output is correct |
| 8 |
Runtime error |
68 ms |
114860 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
