1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1000000000000000000LL;
const int maxn = 100005;
const int size = 350;
LL ans;
int L[maxn / size + 5], R[maxn / size + 5], con[maxn / size + 5][size + 5], pos[maxn];
double ri[maxn / size + 5][size + 5];
LL a[maxn], k[maxn / size + 5], b[maxn / size + 5];
int cnt[maxn];
inline double GetCrossX(int i, int j) { return double(a[i] - a[j]) / double(j - i); }
inline void update_convex(int x) {
cnt[x] = 0;
for (int i = L[x]; i <= R[x]; ++i) {
while (cnt[x] >= 2 && GetCrossX(i, con[x][cnt[x]]) <= GetCrossX(i, con[x][cnt[x] - 1])) --cnt[x];
con[x][++cnt[x]] = i;
}
for (int i = 1; i < cnt[x]; ++i) ri[x][i] = GetCrossX(con[x][i], con[x][i+1]);
ri[x][cnt[x]] = INF;
}
inline void bf_modify_a(int l, int r, LL k, LL b) {
for (int i = l; i <= r; ++i) a[i] += b + k * (i - l);
update_convex(pos[l]);
}
inline void modify_a(int l, int r, LL val) {
if (pos[l] == pos[r]) return bf_modify_a(l, r, val, val);
bf_modify_a(l, R[pos[l]], val, val); bf_modify_a(L[pos[r]], r, val, val * (L[pos[r]] - l + 1));
for (int i = pos[l] + 1; i < pos[r]; ++i) {
k[i] += val;
b[i] += val * (L[i] - l + 1);
}
}
inline void bf_query(int l, int r) {
int j = pos[l];
for (int i = l; i <= r; ++i) ans = max(ans, a[i] + b[j] + k[j] * (i - L[j]));
}
inline void query(int i) {
int l = 1, r = cnt[i], mid;
while (l < r) {
mid = (l + r) >> 1;
if (ri[i][mid] >= k[i]) r = mid;
else l = mid + 1;
}
ans = max(ans, b[i] + k[i] * (con[i][r] - L[i]) + a[con[i][r]]);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
int cnt_block = (n + size - 1) / size;
for (int i = 1; i <= cnt_block; ++i) {
L[i] = R[i - 1] + 1; R[i] = min(n, L[i] + size - 1);
for (int j = L[i]; j <= R[i]; ++j) pos[j] = i;
update_convex(i);
}
int ty, x, y;
LL z;
while (m--) {
scanf("%d %d %d", &ty, &x, &y);
if (x > y) swap(x, y);
if (ty == 3) {
scanf("%lld", &z);
modify_a(x, y, z);
continue;
}
if (ty == 2) {
int i = pos[x], j = pos[y];
if (i == j) {
bf_modify_a(L[i], R[i], k[i], b[i]);
k[i] = b[i] = 0;
}
else {
bf_modify_a(L[i], R[i], k[i], b[i]);
k[i] = b[i] = 0;
bf_modify_a(L[j], R[j], k[j], b[j]);
k[j] = b[j] = 0;
}
swap(a[x], a[y]);
update_convex(i);
if (i != j) update_convex(j);
continue;
}
ans = -INF;
if (pos[x] == pos[y]) bf_query(x, y);
else {
bf_query(x, R[pos[x]]); bf_query(L[pos[y]], y);
for (int i = pos[x] + 1; i < pos[y]; ++i) query(i);
}
printf("%lld\n", max(ans - a[1] - b[1], 0ll));
}
}
|
