一些废话

题目传送门

• 很好，为什么最难的题会放在最前面？（划掉，因为我小题大作了）
• 好吧，看了st表的做法，突然发现没有update（区间修改）的线段树简直就是在浪费手和脑子（其实就是我想练练没学多久的线段树啦）
• 至于为什么题简单还写这篇题解，因为我是蒟蒻原因见2947题的前两个字（也划掉）
• 嗯，题意就是找区间最大和次大值，说实话，看了好几次才明白为什么两个边能构成三角形（这个也划掉，因为我是蒟蒻）

代码

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, q, a[N], max1[N << 2], max2[N << 2]; //树要开4倍

struct node { //答案结构体
	int max1, max2;
	node(int a = 0, int b = 0) {
		max1 = a;
		max2 = b;
	}
};

inline void read(int &x) { //快读
	x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + ch - 48;
		ch = getchar();
	}
	return ;
}

void pushup(int root) { //回溯操作（因为不用update，这里甚至没有pushdown和懒标记）
	int lnode = root << 1, rnode = lnode + 1;
	max1[root] = max(max1[lnode], max1[rnode]); //找最大和次大
	if (max1[lnode] > max1[rnode]) {
		max2[root] = max(max1[rnode], max2[lnode]);
	} else {
		max2[root] = max(max1[lnode], max2[rnode]);
	}
	return ;
}

void build(int root, int bdl, int bdr) { //建树
	if (bdl == bdr) {
		max1[root] = a[bdl];
		return ;
	}
	int mid = (bdl + bdr) >> 1;
	int lnode = root << 1, rnode = lnode + 1;
	build(lnode, bdl, mid);
	build(rnode, mid + 1, bdr);
	pushup(root);
	return ;
}

node query(int root, int bdl, int bdr, int L, int R) { //标准的线段树查询函数，跟板子一样
	if (bdl >= L && bdr <= R) {
		return {max1[root], max2[root]};
	}
	int mid = (bdl + bdr) >> 1;
	int lnode = root << 1, rnode = lnode + 1;
	node lnd, rnd, ans;
	if (L <= mid) {
		ans = lnd = query(lnode, bdl, mid, L, R);
	}
	if (R > mid) {
		rnd = query(rnode, mid + 1, bdr, L, R);
		ans.max1 = max(lnd.max1, rnd.max1); //还是找最大和次大
		if (lnd.max1 > rnd.max1) {
			ans.max2 = max(rnd.max1, lnd.max2);
		} else {
			ans.max2 = max(lnd.max1, rnd.max2);
		}
	}
	return ans;
}

int main() {
	read(n), read(q);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	build(1, 1, n);
	int l, r;
	node now;
	while (q--) {
		read(l), read(r);
		now = query(1, 1, n, l, r);
		printf("%.2lf\n", 0.5 * now.max1 * now.max2); //求直角三角形面积
	}
	return 0;
}