题目：Balanced lineup

题目说的很清楚了，没有修改，直接RMQ，模板题。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

const int N = 5e4 + 5;

using namespace std;

int n, m, a[N], f1[N][20], f2[N][20];

int main()

{

	scanf("%d %d", &n, &m);

	for(int i = 1; i <= n; i++)

	    scanf("%d", &a[i]), f1[i][0] = f2[i][0] = a[i];

	for(int j = 1; (1<<j) <= n; j++)

	    for(int i = 1; i + (1<<j) - 1 <= n; i++)

	    {

	        f1[i][j] = max(f1[i][j-1], f1[i + (1<< (j-1))][j-1]);

	        f2[i][j] = min(f2[i][j-1], f2[i + (1<< (j-1))][j-1]);

	    }

	while(m--)

	{

		int l, r;

		scanf("%d %d", &l, &r);

		int j=log2(r - l + 1);

		printf("%d\n", max(f1[l][j], f1[r - (1<<j) + 1][j]) - min(f2[l][j], f2[r - (1<<j) + 1][j]));

	}

	return 0;

}

巴特西

2022春每日一题：Day 15

题目：Balanced lineup

最新文章

热门文章