#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>
#include <set>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
struct Node {
int maxseg; //
ll maxsegval; //
int maxpref; //
ll first; //
int maxsuff; //
ll last; //
ll addval; //
ll setval; //
bool hasset; //
int len; //
bool neutral; //
ll summ;
Node() :addval(0), setval(0), hasset(false), len(0), neutral(false), summ(0) {}
Node(bool _) :neutral(true) {}
Node(ll x) {
maxseg = 1;
maxsegval = x;
maxpref = 1;
first = x;
maxsuff = 1;
last = x;
addval = 0;
setval = 0;
hasset = false;
len = 1;
neutral = false;
summ = 0;
}
};
void push(int v, vector<Node>& t) {
if (!t[v].hasset) {
t[2 * v + 1].addval += t[v].addval;
t[2 * v + 2].addval += t[v].addval;
t[v].addval = 0;
} else {
t[2 * v + 1].setval = t[v].setval;
t[2 * v + 1].addval = t[v].addval;
t[2 * v + 1].hasset = true;
t[2 * v + 2].setval = t[v].setval;
t[2 * v + 2].addval = t[v].addval;
t[2 * v + 2].hasset = true;
t[v].setval = 0;
t[v].addval = 0;
t[v].hasset = false;
}
}
Node selfpush(const Node& a) {
Node b = a;
if (!a.hasset) {
b.first += b.addval;
b.last += b.addval;
b.maxsegval += b.addval;
b.summ += b.addval * b.len;
b.addval = 0;
} else {
b.first = b.setval + b.addval;
b.last = b.setval + b.addval;
b.maxsegval = b.setval + b.addval;
b.maxpref = b.len;
b.maxsuff = b.len;
b.maxseg = b.len;
b.summ = (b.setval + b.addval) * b.len;
b.hasset = 0;
b.setval = 0;
b.addval = 0;
}
return b;
}
Node unite(const Node& a_, const Node& b_) {
Node a = selfpush(a_), b = selfpush(b_);
if (a_.neutral) {
return b;
} else if (b_.neutral) {
return a;
}
Node c;
c.neutral = false;
c.len = a.len + b.len;
c.summ = a.summ + b.summ;
/*ll afirstreal = (a.hasset ? a.setval + a.addval : a.first + a.addval);
ll alastreal = (a.hasset ? a.setval + a.addval : a.last + a.addval);
ll bfirstreal = (b.hasset ? b.setval + b.addval : b.first + b.addval);
ll blastreal = (b.hasset ? b.setval + b.addval : b.last + b.addval);
c.first = afirstreal;
c.maxpref = a.maxpref + (a.maxpref == a.len && afirstreal == bfirstreal ? b.maxpref : 0);
c.last = blastreal;
c.maxsuff = b.maxsuff + (b.maxsuff == b.len && blastreal == alastreal ? a.maxsuff : 0);
ll amaxreal = (a.hasset ? a.setval + a.addval : a.maxsegval + a.addval);
ll bmaxreal = (b.hasset ? b.setval + b.addval : b.maxsegval + b.addval);
if (a.maxseg > b.maxseg) {
c.maxseg = a.maxseg;
c.maxsegval = amaxreal;
} else {
c.maxseg = b.maxseg;
c.maxsegval = bmaxreal;
}
if (alastreal == bfirstreal && a.maxsuff + b.maxpref > c.maxseg) {
c.maxseg = a.maxsuff + b.maxpref;
c.maxsegval = alastreal;
}*/
c.first = a.first;
c.maxpref = a.maxpref + (a.maxpref == a.len && a.first == b.first ? b.maxpref : 0);
c.last = b.last;
c.maxsuff = b.maxsuff + (b.maxsuff == b.len && b.last == a.last ? a.maxsuff : 0);
if (a.maxseg > b.maxseg) {
c.maxseg = a.maxseg;
c.maxsegval = a.maxsegval;
} else {
c.maxseg = b.maxseg;
c.maxsegval = b.maxsegval;
}
if (a.last == b.first && a.maxsuff + b.maxpref > c.maxseg) {
c.maxseg = a.maxsuff + b.maxpref;
c.maxsegval = a.last;
}
return c;
}
void build(int v, int l, int r, vector<Node>& t, const vector<ll>& a) {
if (l == r - 1) {
t[v] = Node(a[l]);
return;
}
int m = (l + r) / 2;
build(2 * v + 1, l, m, t, a);
build(2 * v + 2, m, r, t, a);
t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}
Node query(int v, int l, int r, int askl, int askr, vector<Node>& t) {
if (l >= askr || r <= askl) {
return Node(true);
}
if (l >= askl && r <= askr) {
return selfpush(t[v]);
}
push(v, t);
int m = (l + r) / 2;
auto ans_left = query(2 * v + 1, l, m, askl, askr, t);
auto ans_right = query(2 * v + 2, m, r, askl, askr, t);
t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
return unite(ans_left, ans_right);
}
void range_add(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) {
if (l >= askr || r <= askl) {
return;
}
if (l >= askl && r <= askr) {
t[v].addval += val;
return;
}
push(v, t);
int m = (l + r) / 2;
range_add(2 * v + 1, l, m, askl, askr, val, t);
range_add(2 * v + 2, m, r, askl, askr, val, t);
t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}
void range_set(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) {
if (l >= askr || r <= askl) {
return;
}
if (l >= askl && r <= askr) {
t[v].hasset = true;
t[v].setval = val;
t[v].addval = 0;
return;
}
push(v, t);
int m = (l + r) / 2;
range_set(2 * v + 1, l, m, askl, askr, val, t);
range_set(2 * v + 2, m, r, askl, askr, val, t);
t[v] = unite(t[2 * v + 1], t[2 * v + 2]);
}
ll get_elem(int i, int n, vector<Node>& t) {
return query(0, 0, n, i, i + 1, t).maxsegval;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<ll> orig(n);
for (int i = 0; i < n; ++i) {
cin >> orig[i];
}
orig.insert(orig.begin(), 1e9);
n++;
vector<ll> diff(n);
diff[0] = orig[0];
for (int i = 1; i < n; ++i) {
diff[i] = orig[i] - orig[i - 1];
}
vector<Node> t(4 * n);
build(0, 0, n, t, diff);
for (int _ = 0; _ < q; ++_) {
int type;
cin >> type;
if (type == 1) {
int l, r;
ll s, c;
cin >> l >> r >> s >> c;
//l--, r--;
range_add(0, 0, n, l, l + 1, s, t);
range_add(0, 0, n, l + 1, r + 1, c, t);
if (r + 1 < n) {
range_add(0, 0, n, r + 1, r + 2, -(s + (r - l) * c), t);
}
} else if (type == 2) {
int l, r;
ll s, c;
cin >> l >> r >> s >> c;
//l--, r--;
ll realr = query(0, 0, n, 0, r + 1, t).summ;
ll prv = (l == 0 ? 0ll : get_elem(l - 1, n, t));
range_set(0, 0, n, l, l + 1, s - prv, t);
range_set(0, 0, n, l + 1, r + 1, c, t);
if (r + 1 < n) {
ll nxt = get_elem(r + 1, n, t);
range_add(0, 0, n, r + 1, r + 2, realr - (s + (r - l) * c), t);
}
} else {
int l, r;
cin >> l >> r;
//l--, r--;
cout << query(0, 0, n, l, r + 1, t).maxseg + 1 << '\n';
}
}
}
/*
10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |