st表维护区间最值下标

#include<bits/stdc++.h>
using namespace std;
const int Max=1000005;
//
int n,m,arr[Max],st[Max][25];
//区间 st[i(下标)][j(2^j 区间长度)] 
// st[i][j]: (i, i+2^j -1)区间 最值的下标 
inline int get_ans(int l,int r){
	int tmp=log2(r-l+1);
	return max(st[l][tmp],st[r-(1<<tmp)+1][tmp]);
}
inline int get_id(int l,int r){
	if(l>r) return 0;
	int tmp=log2(r-l+1);
	int x=st[l][tmp];
	int y=st[r-(1<<tmp)+1][tmp];
	if(arr[x]<arr[y])return y;
	else return x; 
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&arr[i]);
		st[i][0]=i;
	} 
	for(int j=1;(1<<j)<=n;++j){
		for(int i=1;i<=n-(1<<j)+1;++i){
			//st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			//下标 
			int x=st[i][j-1];
			int y=st[i+(1<<j-1)][j-1];
			
			if(arr[x]>arr[y]) st[i][j]=x;
			else st[i][j]=y; 
		}
	}
	
	while(m--){
		int l,r; 
		scanf("%d%d",&l,&r);
		int id=get_id(l,r);
	//	cout<<id<<endl;
		int first_number=arr[id]; 
		int second_number=max(arr[get_id(l,id-1)],arr[get_id(id+1,r)]);
		printf("%.2lf\n",first_number*1.0*second_number/2.0);
	}
	return 0;
}

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;
}

一些废话

题目传送门

• 很好，为什么最难的题会放在最前面？（划掉，因为我小题大作了）
• 好吧，看了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;
}