rt,求调。

大致思路为跑两遍 query()，第一遍跑出最大值，第二遍排除最大值，跑出第二大，然后就是板子。

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010
#define ll long long
ll a[maxn], w[maxn * 4];
ll max1, max2;
int n, q;
void pushup(const int u) {
	w[u] = w[u * 2] + w[u * 2 + 1];
}
void build(const int u, int L, int R) {
	if(L == R) {
		w[u] = a[L];
		return ;
	}
	int M = (L + R) / 2;
	build(u * 2, L, M); build(u * 2 + 1, M + 1, R);
	pushup(u);
}
void update1(int u, int L, int R, int p, ll x) {
	if(L == R) {
		w[u] = x;
	} else {
		int M = (L + R) / 2;
		if(M >= p) update1(u * 2, L, M, p, x);
		else update1(u * 2 + 1, M + 1, R, p, x);
		pushup(u);
	}
}
bool InRange(int L, int R, int l, int r) {
	return (l <= L) && (R <= r);
}
bool OutofRange(int L, int R, int l, int r) {
	return (L > r) || (R < l);
}
ll query1(int u, int L, int R, int l, int r) {
	if(InRange(L, R, l, r)) {
		return w[u];
	} else if(!OutofRange(L, R, l, r)) {
		int M = (L + R) / 2;
		return max(query1(u * 2, L, M, l, r), query1(u * 2 + 1, M + 1, R, l, r));
	} else return 0;
}
ll query2(int u, int L, int R, int l, int r) {
	if(InRange(L, R, l, r)) {
		return w[u];
	} else if(!OutofRange(L, R, l, r)) {
		int M = (L + R) / 2;
		if(query2(u * 2, L, M, l, r) == max1 && query2(u * 2 + 1, M + 1, R, l, r) != max1) return query2(u * 2 + 1, M + 1, R, l, r);
		else if(query2(u * 2 + 1, M + 1, R, l, r) == max1 && query2(u * 2, L, M, l, r) != max1) return query2(u * 2, L, M, l, r);
		else if(query2(u * 2, L, M, l, r) == max1 && query2(u * 2 + 1, M + 1, R, l, r) == max1) return 0;
		else return max(query2(u * 2, L, M, l, r), query2(u * 2 + 1, M + 1, R, l, r));
	} else return 0;
}
int main() {
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	for(int t = 1; t <= q; t++) {
		int op;
		cin >> op;
		if(op == 1) {
			int p; ll x;
			cin >> p >> x;
			update1(1, 1, n, p, x);
		} else {
			int l, r;
			cin >> l >> r;
			max1 = query1(1, 1, n, l, r);
			max2 = query2(1, 1, n, l, r);
			cout << max2 << endl;
		}
	}
	return 0;
}