#include <bits/stdc++.h>
using namespace std;
const int MAX = 300300;
const long long inf = (long long) 1e18;
struct Value {
struct Node {
long long sum;
long long coeff;
};
int n;
Node st[8 * MAX];
void Modify(int id, int l, int r, int ll, int rr, long long x, long long y) {
if (ll <= l && r <= rr) {
st[id].sum += x;
st[id].coeff += y;
return;
}
int mid = (l + r) >> 1;
if (rr <= mid) {
Modify(id * 2, l, mid, ll, rr, x, y);
} else if (ll > mid) {
Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y);
} else {
Modify(id * 2, l, mid, ll, rr, x, y);
Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y);
}
}
Node Query(int id, int l, int r, int p) {
if (l == r) {
return st[id];
}
int mid = (l + r) >> 1;
Node nd;
if (p <= mid) {
nd = Query(id * 2, l, mid, p);
} else {
nd = Query(id * 2 + 1, mid + 1, r, p);
}
return {st[id].sum + nd.sum, st[id].coeff + nd.coeff};
}
long long Get(int i) {
Node nd = Query(1, 0, n - 1, i);
return nd.sum + nd.coeff * i;
}
} val;
struct Solver {
struct Node {
int len;
int mx;
int mx_l;
int mx_r;
long long val_l;
long long val_r;
long long lzy_add;
long long lzy_set;
Node() {
lzy_set = inf;
lzy_add = 0;
}
};
Node Merge(Node a, Node b) {
Node nd;
nd.len = a.len + b.len;
nd.mx = max(a.mx, b.mx);
nd.mx_l = a.mx_l;
nd.mx_r = b.mx_r;
if (a.val_r == b.val_l) {
nd.mx = max(nd.mx, a.mx_l + b.mx_r);
if (a.mx_l == a.len) {
nd.mx_l = max(nd.mx_l, a.len + b.mx_l);
}
if (b.mx_r == b.len) {
nd.mx_r = max(nd.mx_r, a.mx_r + b.len);
}
}
nd.val_l = a.val_l;
nd.val_r = b.val_r;
return nd;
}
Node st[8 * MAX];
void Push(int id) {
if (st[id].lzy_set == inf) {
st[id * 2].val_l += st[id].lzy_add;
st[id * 2].val_r += st[id].lzy_add;
st[id * 2 + 1].val_l += st[id].lzy_add;
st[id * 2 + 1].val_r += st[id].lzy_add;
st[id * 2].lzy_add += st[id].lzy_add;
st[id * 2 + 1].lzy_add += st[id].lzy_add;
st[id].lzy_add = 0;
} else {
st[id * 2].val_l = st[id].lzy_set + st[id].lzy_add;
st[id * 2].val_r = st[id].lzy_set + st[id].lzy_add;
st[id * 2 + 1].val_l = st[id].lzy_set + st[id].lzy_add;
st[id * 2 + 1].val_r = st[id].lzy_set + st[id].lzy_add;
st[id * 2].lzy_set = st[id].lzy_set;
st[id * 2].lzy_add = st[id].lzy_add;
st[id * 2 + 1].lzy_set = st[id].lzy_set;
st[id * 2 + 1].lzy_add = st[id].lzy_add;
st[id * 2].mx = st[id * 2].mx_l = st[id * 2].mx_r = st[id * 2].len;
st[id * 2 + 1].mx = st[id * 2 + 1].mx_l = st[id * 2 + 1].mx_r = st[id * 2 + 1].len;
st[id].lzy_set = inf;
st[id].lzy_add = 0;
}
}
void Build(int id, int l, int r) {
if (l == r) {
st[id].val_l = st[id].val_r = 0;
st[id].len = 1;
st[id].mx = st[id].mx_l = st[id].mx_r = 1;
return;
}
int mid = (l + r) >> 1;
Build(id * 2, l, mid);
Build(id * 2 + 1, mid + 1, r);
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
void Set(int id, int l, int r, int ll, int rr, long long x) {
if (ll <= l && r <= rr) {
st[id].mx = st[id].mx_l = st[id].mx_r = st[id].len;
st[id].val_l = x;
st[id].val_r = x;
st[id].lzy_set = x;
st[id].lzy_add = 0;
Push(id);
return;
}
int mid = (l + r) >> 1;
if (rr <= mid) {
Set(id * 2, l, mid, ll, rr, x);
} else if (ll > mid) {
Set(id * 2 + 1, mid + 1, r, ll, rr, x);
} else {
Set(id * 2, l, mid, ll, rr, x);
Set(id * 2 + 1, mid + 1, r, ll, rr, x);
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
void Add(int id, int l, int r, int ll, int rr, long long x) {
if (ll <= l && r <= rr) {
st[id].lzy_add += x;
Push(id);
return;
}
int mid = (l + r) >> 1;
if (rr <= mid) {
Add(id * 2, l, mid, ll, rr, x);
} else if (ll > mid) {
Add(id * 2 + 1, mid + 1, r, ll, rr, x);
} else {
Add(id * 2, l, mid, ll, rr, x);
Add(id * 2 + 1, mid + 1, r, ll, rr, x);
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
}
Node Query(int id, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return st[id];
}
Push(id);
int mid = (l + r) >> 1;
Node ret;
if (rr <= mid) {
ret = Query(id * 2, l, mid, ll, rr);
} else if (ll > mid) {
ret = Query(id * 2 + 1, mid + 1, r, ll, rr);
} else {
ret = Merge(Query(id * 2, l, mid, ll, rr), Query(id * 2 + 1, mid + 1, r, ll, rr));
}
st[id] = Merge(st[id * 2], st[id * 2 + 1]);
return ret;
}
} st;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
int d;
cin >> d;
val.Modify(1, 0, n - 1, i, i, d, 0);
}
val.n = n;
st.Build(1, 0, n - 1);
for (int i = 0; i + 1 < n; i++) {
st.Set(1, 0, n - 1, i, i, val.Get(i) - val.Get(i + 1));
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
}
if (op == 2) {
}
if (op == 3) {
int l, r;
cin >> l >> r;
--l; --r;
if (l == r) {
cout << 1 << '\n';
} else {
cout << st.Query(1, 0, n - 1, l, r - 1).mx + 1 << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
131924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
113496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
134668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
132024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
134668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
131924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
