显示原始代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5, inf = 1e18;
int a[maxn];
int mx[maxn << 2];
#define lson p << 1
#define rson p << 1 | 1
void pushup(int p) { mx[p] = max(mx[lson], mx[rson]); }
void build(int p, int l, int r) {
if (l == r) {
mx[p] = a[l];
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(p);
}
void modify(int p, int l, int r, int x, int k) {
if (l == r) {
mx[p] = k;
return;
}
int mid = l + r >> 1;
if (x <= mid)
modify(lson, l, mid, x, k);
if (x > mid)
modify(rson, mid + 1, r, x, k);
pushup(p);
}
int query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return mx[p];
}
int mid = l + r >> 1;
int ans = -inf;
if (L <= mid)
ans = max(ans, query(lson, l, mid, L, R));
if (R > mid)
ans = max(ans, query(rson, mid + 1, r, L, R));
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
modify(1, 1, n, x, y);
}
if (op == 2) {
int res = inf;
for (int i = x + 1; i <= y - 1; i++) {
res = min(res, query(1, 1, n, x, i - 1) + query(1, 1, n, i, i) + query(1, 1, n, i + 1, y));
}
cout << res << endl;
}
}
return 0;
}