84 lines
1.9 KiB
C++
84 lines
1.9 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
int main(){
|
|
int n, q;
|
|
cin >> n >> q;
|
|
vector<int> lg(n+1);
|
|
vector<int> height(n);
|
|
lg[1] = 0;
|
|
for(int i = 2; i <= n; ++i){
|
|
lg[i] = lg[i >> 1] + 1;
|
|
}
|
|
for(int i = 0; i < n; ++i){
|
|
cin >> height[i];
|
|
}
|
|
vector<vector<int>> st_max(n, vector<int>(20));
|
|
vector<vector<int>> st_min(n, vector<int>(20));
|
|
|
|
// 初始化第 0 层（长度为 1 的区间）
|
|
for(int i = 0; i < n; ++i) {
|
|
st_max[i][0] = st_min[i][0] = height[i];
|
|
}
|
|
|
|
// 核心倍增预处理
|
|
for(int j = 1; j <= lg[n]; ++j) { // 先枚举幂次
|
|
for(int i = 0; i + (1 << j) <= n; ++i) { // 枚举起点，确保不越界
|
|
// 长度为 2^j 的区间 = 两个长度为 2^(j-1) 的区间合并
|
|
st_max[i][j] = max(st_max[i][j-1], st_max[i + (1 << (j-1))][j-1]);
|
|
st_min[i][j] = min(st_min[i][j-1], st_min[i + (1 << (j-1))][j-1]);
|
|
}
|
|
}
|
|
|
|
for(int i = 0; i < q; ++i){
|
|
int a, b;
|
|
cin >> a >> b;
|
|
int len = b - a + 1;
|
|
int k = lg[len];
|
|
int res_max = max(st_max[a-1][k], st_max[b - (1 << k)][k]);
|
|
int res_min = min(st_min[a-1][k], st_min[b - (1 << k)][k]);
|
|
cout << res_max - res_min << endl;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
//dp困难方法
|
|
/*
|
|
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
const int INF = 1e9;
|
|
int main(){
|
|
int n, q;
|
|
cin >> n >> q;
|
|
vector<int> height(n);
|
|
vector<vector<int>> dp(n, vector<int>(n, INF));
|
|
for(int i = 0; i < n; ++i){
|
|
cin >> height[i];
|
|
dp[i][i] = height[i];
|
|
}
|
|
//dp function: dp[i][j] = min(dp[i][k], dp[k][j])
|
|
for(int i = 0; i < n; ++i){
|
|
for(int j = 1; j < n; ++j){
|
|
dp[i][j] = min(dp[i][j - 1], height[j]);
|
|
}
|
|
}
|
|
for(int i = 0; i < q; ++i){
|
|
int a, b;
|
|
cin >> a >> b;
|
|
cout << dp[a - 1][b - 1] << endl;
|
|
}
|
|
return 0;
|
|
}*/ |