#include <bits/stdc++.h>
using namespace std;
#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset
using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif
namespace segtree {
/**
* Range set
* Range query: longest sequence of same numbers
*/
const ll INF = 4'234'567'890'123'456'789;
struct QueryOut {
int ans;
ll lnum, rnum;
int llen, rlen;
bool same;
int len;
QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
QueryOut() {len = 0;}
};
QueryOut combine(QueryOut x, QueryOut y) {
if(x.len == 0) return y;
if(y.len == 0) return x;
int new_ans = max({x.ans, y.ans});
if(x.rnum == y.lnum) new_ans = max(new_ans, x.rlen + y.llen);
return QueryOut(
new_ans,
x.lnum,
(x.same && x.rnum == y.lnum) ? x.llen + y.llen : x.llen,
y.rnum,
(y.same && x.rnum == y.lnum) ? y.rlen + x.rlen : y.rlen,
x.same && y.same && x.rnum == y.lnum,
x.len + y.len
);
}
struct Node {
Node *l, *r;
int lo, hi;
ll mset = -INF;
ll madd = 0;
QueryOut qout;
Node(int lo, int hi, vll &v): lo(lo), hi(hi) {
if(lo + 1 == hi){
// same = true;
// lnum = rnum = v[lo];
// llen = rlen = 1;
qout = QueryOut(1, v[lo], 1, v[lo], 1, true, 1);
} else {
int mid = lo + (hi - lo) / 2;
l = new Node(lo, mid, v);
r = new Node(mid, hi, v);
update();
}
}
void update() {
qout = combine(l->qout, r->qout);
}
void push() {
if(mset != -INF) {
l->set(lo, hi, mset);
r->set(lo, hi, mset);
mset = -INF;
} else if(madd) {
l->add(lo, hi, madd);
r->add(lo, hi, madd);
madd = 0;
}
}
void set(int left, int right, ll val) {
assert(val != -INF);
if(right <= lo || hi <= left) return;
if(left <= lo && hi <= right) {
mset = val;
madd = 0;
qout = QueryOut(hi - lo, val, hi - lo, val, hi - lo, true, hi - lo);
} else {
push();
l->set(left, right, val);
r->set(left, right, val);
update();
}
}
void add(int left, int right, ll val) {
if(right <= lo || hi <= left) return;
if(left <= lo && hi <= right) {
if(mset != -INF) {
mset += val;
} else {
madd += val;
}
debug("add proc", left, right, lo, hi, val);
qout = QueryOut(qout.ans, qout.lnum + val, qout.llen, qout.rnum + val, qout.rlen, qout.same, hi - lo);
} else {
push();
l->add(left, right, val);
r->add(left, right, val);
update();
}
}
QueryOut query(int left, int right) {
if(right <= lo || hi <= left) return QueryOut(-1, -1, -1, -1, -1, false, 0); // dummy
if(left <= lo && hi <= right){
return qout;
} else {
push();
return combine(l->query(left, right), r->query(left, right));
}
}
};
}
namespace lichao {
const ll INF = 2'000'000'000'000'000'005;
struct Line{
ll m, c;
Line(ll _m, ll _c) : m(_m), c(_c) {}
ll eval(ll x){
return m * x + c;
}
bool nonzero() {
return m != 0 || c != 0;
}
};
Line operator+(Line &a, Line &b) { return Line(a.m + b.m, a.c + b.c); }
ostream& operator<<(ostream &os, Line x) { return os << "{m=" << x.m << ", c=" << x.c << '}'; }
struct Node {
Node *l = 0, *r = 0;
int lo, hi; // [lo, hi)
Line line = Line(0, INF);
Line madd = Line(0, 0);
bool mwipe = false;
Node(int lo, int hi): lo(lo), hi(hi) {}
void push() {
assert(lo + 1 < hi);
if(!l) {
int mid = lo + (hi - lo) / 2;
l = new Node(lo, mid);
r = new Node(mid, hi);
}
if(madd.nonzero()) {
l->add_affine(lo, hi, madd);
r->add_affine(lo, hi, madd);
madd = Line(0, 0);
}
if(mwipe) {
l->wipe(lo, hi);
r->wipe(lo, hi);
mwipe = false;
}
}
// Reset all lines on [left, right).
void wipe(int left, int right) {
if(right <= lo || hi <= left) return;
if(left <= lo && hi <= right) {
madd = Line(0, 0);
mwipe = true;
line = Line(0, INF);
} else {
push();
l->wipe(left, right);
r->wipe(left, right);
}
}
// Insert new_line on [left, right). O(log^2 n) / O(log n) if left=0, right=n.
void insert_line(int left, int right, Line new_line) {
if(right <= lo || hi <= left) return;
if(left <= lo && hi <= right) {
bool ldiff = line.eval(lo) <= new_line.eval(lo);
bool rdiff = line.eval(hi - 1) <= new_line.eval(hi - 1);
if(ldiff && rdiff) return;
if(!ldiff && !rdiff){
line = new_line;
return;
}
}
push();
l->insert_line(left, right, new_line);
r->insert_line(left, right, new_line);
}
// Add the value of the line to everything in [left, right). O(log^2 n).
void add_affine(int left, int right, Line add) {
if(right <= lo || hi <= left) return;
if(left <= lo && hi <= right) {
line = line + add;
madd = madd + add;
} else {
push();
l->insert_line(lo, hi, line);
r->insert_line(lo, hi, line);
line = Line(0, INF);
l->add_affine(left, right, add);
r->add_affine(left, right, add);
}
}
// Get min at x. O(log n).
ll query(int x){
assert(lo <= x && x < hi);
if(!l){
return line.eval(x);
}
push();
ll rec;
int mid = lo + (hi - lo) / 2;
if(x >= mid) {
rec = r->query(x);
} else {
rec = l->query(x);
}
return min(line.eval(x), rec);
}
};
}
void solve(){
int n, q;
cin >> n >> q;
vi v(n);
for(int i = 0; i < n; i++) cin >> v[i];
vll diff(n-1);
for(int i = 0; i < n-1; i++) {
diff[i] = v[i+1] - v[i];
}
debug(diff);
lichao::Node* lct = new lichao::Node(0, n);
for(int i = 0; i < n; i++){
lct->insert_line(i, i+1, lichao::Line(0, v[i]));
}
segtree::Node* st = new segtree::Node(0, n-1, diff);
while(q--){
int t;
cin >> t;
if(t == 1){
int l, r; ll s, c;
cin >> l >> r >> s >> c;
l--;
lichao::Line ln = lichao::Line(c, s - c * l);
lct->add_affine(l, r, ln);
st->add(l, r, c);
// debug(lct->query(r) - lct->query(r-1));
if(l > 0) st->set(l-1, l, lct->query(l) - lct->query(l-1));
if(r < n) st->set(r-1, r, lct->query(r) - lct->query(r-1));
debug(st->qout.ans, st->qout.lnum, st->qout.llen, st->qout.rnum, st->qout.rlen, st->qout.same);
}else if(t == 2){
int l, r; ll s, c;
cin >> l >> r >> s >> c;
l--;
lichao::Line ln = lichao::Line(c, s - c * l);
lct->wipe(l, r);
lct->insert_line(l, r, ln);
st->set(l, r, c);
if(l > 0) st->set(l-1, l, lct->query(l) - lct->query(l-1));
if(r < n) st->set(r-1, r, lct->query(r) - lct->query(r-1));
}else{
int l, r;
cin >> l >> r;
l--;
if(l + 1 == r){
cout << 1 << endl;
} else {
segtree::QueryOut qout = st->query(l, r-1);
debug(qout.ans, qout.lnum, qout.llen, qout.rnum, qout.rlen, qout.same);
cout << qout.ans + 1 << endl;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Compilation message
Progression.cpp: In constructor 'segtree::QueryOut::QueryOut(int, ll, int, ll, int, bool, int)':
Progression.cpp:44:13: warning: 'segtree::QueryOut::llen' will be initialized after [-Wreorder]
44 | int llen, rlen;
| ^~~~
Progression.cpp:43:18: warning: 'll segtree::QueryOut::rnum' [-Wreorder]
43 | ll lnum, rnum;
| ^~~~
Progression.cpp:47:9: warning: when initialized here [-Wreorder]
47 | QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
115856 KB |
Output is correct |
| 2 |
Correct |
232 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
226 ms |
3624 KB |
Output is correct |
| 4 |
Correct |
223 ms |
3532 KB |
Output is correct |
| 5 |
Correct |
239 ms |
3656 KB |
Output is correct |
| 6 |
Correct |
223 ms |
3572 KB |
Output is correct |
| 7 |
Correct |
243 ms |
3532 KB |
Output is correct |
| 8 |
Runtime error |
692 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
824 ms |
114248 KB |
Output is correct |
| 2 |
Correct |
420 ms |
2932 KB |
Output is correct |
| 3 |
Correct |
426 ms |
3108 KB |
Output is correct |
| 4 |
Correct |
407 ms |
2888 KB |
Output is correct |
| 5 |
Correct |
424 ms |
3304 KB |
Output is correct |
| 6 |
Correct |
399 ms |
3060 KB |
Output is correct |
| 7 |
Correct |
419 ms |
3084 KB |
Output is correct |
| 8 |
Runtime error |
538 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1396 ms |
117104 KB |
Output is correct |
| 2 |
Correct |
328 ms |
3660 KB |
Output is correct |
| 3 |
Correct |
325 ms |
3640 KB |
Output is correct |
| 4 |
Correct |
326 ms |
3748 KB |
Output is correct |
| 5 |
Correct |
334 ms |
3764 KB |
Output is correct |
| 6 |
Correct |
323 ms |
3664 KB |
Output is correct |
| 7 |
Correct |
313 ms |
3644 KB |
Output is correct |
| 8 |
Runtime error |
535 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
824 ms |
114248 KB |
Output is correct |
| 2 |
Correct |
420 ms |
2932 KB |
Output is correct |
| 3 |
Correct |
426 ms |
3108 KB |
Output is correct |
| 4 |
Correct |
407 ms |
2888 KB |
Output is correct |
| 5 |
Correct |
424 ms |
3304 KB |
Output is correct |
| 6 |
Correct |
399 ms |
3060 KB |
Output is correct |
| 7 |
Correct |
419 ms |
3084 KB |
Output is correct |
| 8 |
Runtime error |
538 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
115856 KB |
Output is correct |
| 2 |
Correct |
232 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
226 ms |
3624 KB |
Output is correct |
| 4 |
Correct |
223 ms |
3532 KB |
Output is correct |
| 5 |
Correct |
239 ms |
3656 KB |
Output is correct |
| 6 |
Correct |
223 ms |
3572 KB |
Output is correct |
| 7 |
Correct |
243 ms |
3532 KB |
Output is correct |
| 8 |
Runtime error |
692 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
