NC25040. [USACO 2007 Jan G]Balanced Lineup
描述
输入描述
Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
输出描述
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
示例1
输入:
6 3 1 7 3 4 2 5 1 5 4 6 2 2
输出:
6 3 0
C++(clang++ 11.0.1) 解法, 执行用时: 75ms, 内存消耗: 9644K, 提交时间: 2022-10-25 19:06:43
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int Fmax[N][20], Fmin[N][20], a[N];
int n, m;
int query_max(int l, int r)
{
int len = log2(r - l + 1);
return max(Fmax[l][len], Fmax[r - (1 << len) + 1][len]);
}
int query_min(int l, int r)
{
int len = log2(r - l + 1);
return min(Fmin[l][len], Fmin[r - (1 << len) + 1][len]);
}
signed main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int len1 = log2(n);
for (int j = 0; j <= len1; j ++ )
{
for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
{
if (!j) Fmax[i][j] = a[i];
else Fmax[i][j] = max(Fmax[i][j - 1], Fmax[i + (1 << (j - 1))][j - 1]);
}
}
for (int j = 0; j <= len1; j ++ )
{
for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
{
if (!j) Fmin[i][j] = a[i];
else Fmin[i][j] = min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);
}
}
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query_max(l, r) - query_min(l, r));
}
return 0;
}