liaomingjie LV 7 @ 2 年前

2945. 神奇三角形

题意为在区间内找两条边，然后去求这两条边组成的三角形的面积的最大值。

由于是找两条边，不用管第三边有多长，所以只要找到这两条边，把它拼成一个直角三角形，就是面积的最大值了。

这样的话，要解决的题目便变成了找区间内的最大值和次大值，然后相乘，除以2就行了。

这段代码是使用线段树的，感觉比较好理解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#define LL long long
#define ull unsigned long long
using namespace std;
const int N=1e6+5;
const int INF=0x3f3f3f3f;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node{
	int maxx,maxd;
	int l,r;
	int num;
}tree[N];
struct par{
	int maxv,maxs;
};
int n,q;
int a[N];
par find_(int a,int b,int c,int d){//寻找四个数里的最大值和次大值。
	par xs;
	xs.maxv=a;
	xs.maxs=-INF;
	if(b>xs.maxv){
	    xs.maxs=xs.maxv;
	    xs.maxv=b;
	}else if(b>xs.maxs){
	    xs.maxs=b;
	}
	if(c>xs.maxv){
	    xs.maxs=xs.maxv;
	    xs.maxv=c;
	}else if(c>xs.maxs){
	    xs.maxs=c;
	}
	if(d>xs.maxv){
	    xs.maxs=xs.maxv;
	    xs.maxv=d;
	}else if(d>xs.maxs){
	    xs.maxs=d;
	}
	return xs;
}
void push_up(int id){
	par x=find_(tree[id<<1].maxx,tree[id<<1].maxd,tree[id<<1|1].maxd,tree[id<<1|1].maxx);//这个区间的最大值和次大值是从它的两个子区间的最大值和次大值来的。
	tree[id].maxx=x.maxv;
	tree[id].maxd=x.maxs;
}
void build(int l,int r,int id){// 构造线段树
	tree[id].l=l;
	tree[id].r=r;
	if(l==r){
		tree[id].maxx=a[l];
//		cout << l << " " << r << " " << tree[id].maxx << " " << tree[id].maxd << endl;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
	push_up(id);
//	cout << l << " " << r << " " << tree[id].maxx << " " << tree[id].maxd << endl;
}
par tree_find(int l,int r,int id){//在区间内查找
	if(tree[id].l>=l&&tree[id].r<=r){
		return (par){tree[id].maxx,tree[id].maxd};
	}
	if(tree[id].l>r||tree[id].r<l){
		return (par){-INF,-INF};
	}
	par a1=tree_find(l,r,id<<1);
	par a2=tree_find(l,r,id<<1|1);
	return find_(a1.maxs,a1.maxv,a2.maxs,a2.maxv);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		par ans=tree_find(l,r,1);
		printf("%.2lf\n",(double)(((double)ans.maxv*(double)ans.maxs)/2));
	}
	return 0;
}