#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 11;
int d[MAXN];
struct SegTree{
struct tag{
tag() = default;
tag(int _type, int _s, int _c) : type(_type), s(_s), c(_c) {};
int type, s, c;
void operator+= (const tag& t) {
if(t.type == 1) s += t.s, c += t.c;
else s = t.s, c = t.c;
}
tag shift(int n) {
return {type, s + n * c, c};
}
} lazy[MAXN << 2];
struct node{
int ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size;
node() = default;
node(int idx, int val) {
if(idx == -1) { ans = -1; return; }
_size = 1; pf_s = sf_s = val; pf_c = sf_c = 0; pf_x = sf_x = 1;
}
friend node operator+ (const node& a, const node& b) {
if(a.ans == -1 || b.ans == -1) return a.ans == -1 ? b : a;
node res; res.ans = max(a.ans, b.ans); res._size = a._size + b._size;
res.pf_s = a.pf_s, res.pf_c = a.pf_c, res.pf_x = a.pf_x;
if(a.pf_x == a._size){
if(a._size == 1){
res.pf_c = b.pf_s - a.sf_s;
res.pf_x = res.pf_c == b.pf_c ? 1 + b.pf_x : 2;
}else if(a.sf_s + a.sf_c == b.pf_s){
res.pf_x = a.pf_x + (a.pf_c == b.pf_c ? b.pf_x : 1);
}
}
res.sf_s = b.sf_s, res.sf_c = b.sf_c, res.sf_x = b.sf_x;
if(b.sf_x == b._size){
if(b._size == 1){
res.sf_c = b.pf_s - a.sf_s;
res.sf_x = res.sf_c == a.sf_c ? 1 + a.sf_x : 2;
}else if(a.sf_s + b.pf_c == b.pf_s){
res.sf_x = b.sf_x + (b.sf_c == a.sf_c ? a.sf_x : 1);
}
}
res.ans = max(res.ans, max(res.pf_x, res.sf_x));
res.ans = max(res.ans, 2LL);
if(a.sf_s + b.pf_c == b.pf_s){
res.ans = max(res.ans, 1 + b.pf_x);
}
if(a.sf_s + a.sf_c == b.pf_s){
res.ans = max(res.ans, 1 + a.sf_x);
}
if(a.sf_s + a.sf_c == b.pf_s && a.sf_c == b.pf_c){
res.ans = max(res.ans, a.sf_x + b.pf_x);
}
return res;
}
void operator+= (const tag& t) {
if(t.type == 1) pf_s += t.s, pf_c += t.c, sf_s += t.s + t.c * (_size - 1), sf_c += t.c;
else ans = pf_x = sf_x = _size, pf_s = t.s, pf_c = t.c, sf_s = t.s + t.c * (_size - 1), sf_c = t.c;
}
void pr() {
printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
}
} t[MAXN << 2];
void push(int v){
t[v * 2 + 1] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
t[v * 2 + 2] += lazy[v].shift(t[v * 2 + 1]._size);
lazy[v * 2 + 2] += lazy[v].shift(t[v * 2 + 1]._size);
lazy[v] = tag(1, 0, 0);
}
void build(int v, int l, int r){
lazy[v] = tag(1, 0, 0);
if(l == r) {
t[v] = node(l, d[l]);
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m + 1, r);
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
void patch(int ql, int qr, int s, int c, int v, int l, int r){
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) {
tag _t(1, s, c);
lazy[v] += _t;
t[v] += _t;
return;
}
push(v);
int m = (l + r) / 2;
patch(ql, qr, s, c, v * 2 + 1, l, m);
patch(ql, qr, s, c, v * 2 + 2, m + 1, r);
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
void rewrite(int ql, int qr, int s, int c, int v, int l, int r){
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) {
tag _t(2, s, c);
lazy[v] += _t;
t[v] += _t;
return;
}
push(v);
int m = (l + r) / 2;
rewrite(ql, qr, s, c, v * 2 + 1, l, m);
rewrite(ql, qr, s, c, v * 2 + 2, m + 1, r);
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
node eval(int ql, int qr, int v, int l, int r){
if(qr < l || r < ql) return node(-1, 0);
if(ql <= l && r <= qr) return t[v];
push(v);
int m = (l + r) / 2;
node a = eval(ql, qr, v * 2 + 1, l, m);
node b = eval(ql, qr, v * 2 + 2, m + 1, r);
return a + b;
}
} segTree;
int32_t main(){
int n, q; cin >> n >> q;
for(int i = 0; i < n; i++) cin >> d[i];
segTree.build(0, 0, n - 1);
for(int i = 0; i < q; i++){
int ty, l, r, s, c; cin >> ty >> l >> r; l--; r--;
if(ty == 1){
cin >> s >> c;
segTree.patch(l, r, s, c, 0, 0, n - 1);
}else if(ty == 2){
cin >> s >> c;
segTree.rewrite(l, r, s, c, 0, 0, n - 1);
}else{
SegTree::node _node = segTree.eval(l, r, 0, 0, n - 1);
cout << _node.ans << endl;
}
}
}
Compilation message
Progression.cpp: In member function 'void SegTree::node::pr()':
Progression.cpp:77:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~
| | |
| int long long int
| %lld
Progression.cpp:77:19: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:22: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:25: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:32: warning: format '%d' expects argument of type 'int', but argument 6 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:35: warning: format '%d' expects argument of type 'int', but argument 7 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:38: warning: format '%d' expects argument of type 'int', but argument 8 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~
| | |
| int long long int
| %lld
Progression.cpp:77:42: warning: format '%d' expects argument of type 'int', but argument 9 has type 'long long int' [-Wformat=]
77 | printf("%d pf(%d %d %d) sf(%d %d %d) %d\n", ans, pf_s, pf_c, pf_x, sf_s, sf_c, sf_x, _size);
| ~^ ~~~~~
| | |
| int long long int
| %lld
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
534 ms |
101224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
869 ms |
99848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1000 ms |
102748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
869 ms |
99848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
534 ms |
101224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
