定点の轰炸：ST表、线段树

题意简述

题目描述了一个城市，城市中有 $N$ 座房子，每座房子有一个高度 $h_i$。JW 的父亲需要执行 $Q$ 次轰炸任务，每次任务给定一个区间 $[l, r]$，要求在这个区间内选择高度最高的房子进行轰炸。如果有多个房子高度相同，选择编号最小的那个。

解题思路

这个问题可以转化为一个经典的区间最大值查询问题。我们需要在给定的区间 $[l, r]$ 内找到高度最大的房子，并返回其编号。由于 $N$ 和 $Q$ 都可能非常大 （$N \leq 3 \times 10^5$，$Q \leq 10^6$），我们需要一个高效的算法来处理这些查询。

方法选择

1. 暴力法：对于每个查询，遍历区间 $[l, r]$，找到最大值。这种方法的时间复杂度是 $O(Q \times N)$，显然无法通过。
2. 线段树：线段树可以处理区间查询和更新操作，时间复杂度为 $O(\log N)$ 每次查询。对于 $Q = 10^6$ 来说，总时间复杂度为 $O(Q \log N)$，可以通过。
3. ST表：ST表是一种用于解决静态区间最值查询的数据结构，预处理时间复杂度为 $O(N \log N)$，查询时间复杂度为 $O(1)$。对于 $Q = 10^6$ 来说，总时间复杂度为 $O(N \log N + Q)$，也可以通过。

由于题目中房子高度是静态的（不会改变），ST表是一个非常适合的选择。

预处理

1. 定义：$st[i][j]$ 表示从位置 $i$ 开始，长度为 $2^j$ 的区间内的最大值的位置。
2. 初始化：对于每个 $i$，$st[i][0] = i$，因为长度为 $1$ 的区间最大值就是它自己。
3. 递推：对于每个 $j$，从 $i = 1$ 到 $i = n - 2^j + 1$，比较 $st[i][j-1]$ 和 $st[i + 2^{j-1}][j-1]$ 所对应的值，取较大的那个。

查询

对于查询区间 $[l, r]$，我们可以找到一个 $k$，使得 $2^k \leq r - l + 1 < 2^{k+1}$。然后比较 $st[l][k]$ 和 $st[r - 2^k + 1][k]$ 所对应的值，取较大的那个。

正解

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=3e5+35;
int n,q,l,r,len;
int h[MAXN],logs[MAXN],st[MAXN][25];
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",h+i);
		st[i][0]=i;
		if(i>=2) logs[i]=logs[i>>1]+1;
	}
	for(int j=1;1<<j<=n;j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<j)-1>n) break;
			if(h[st[i][j-1]]>=h[st[i+(1<<j-1)][j-1]]) st[i][j]=st[i][j-1];
			else st[i][j]=st[i+(1<<j-1)][j-1];
		}
	}
	while(q--){
		scanf("%d %d",&l,&r);
		len=logs[r-l+1];
		if(h[st[l][len]]>=h[st[r-(1<<len)+1][len]]) printf("%d\n",st[l][len]);
		else printf("%d\n",st[r-(1<<len)+1][len]);
	}
	return 0;
}

时间复杂度：$O(N\log N)$
预计得分：$160pts$