#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int m_ax, m_in;
int a[50010];
struct node
{
	int l, r, m_ax, m_in;
}tree[200000];
void build(int n, int l, int r)
{
	tree[n].l = l;
	tree[n].r = r;
	if (l == r)
	{
		tree[n].m_ax = a[l];
		tree[n].m_in = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(n * 2, l, mid);
	build(n * 2 + 1, mid + 1, r);
	tree[n].m_ax = max(tree[n * 2].m_ax, tree[n * 2 + 1].m_ax);
	tree[n].m_in = min(tree[n * 2].m_in, tree[n * 2 + 1].m_in);
}

void query(int n, int l, int r)
{
	if (tree[n].l == l&&tree[n].r == r)
	{
		m_ax = max(m_ax, tree[n].m_ax);
		m_in = min(m_in, tree[n].m_in);
		return;
	}
	int mid = (tree[n].l + tree[n].r) / 2;
	if (r <= mid)
	{
		query(n * 2, l, r);
	}
	else if (l > mid)
	{
		query(n * 2 + 1, l, r);
	}
	else
	{
		query(n * 2, l, mid);
		query(n * 2 + 1, mid + 1, r);
	}
}

int main()
{
	int n, q, s, b;
	while (~scanf("%d%d", &n, &q))
	{
		memset(a, 0, sizeof(a));
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		build(1, 1, n);
	/*	for (int i = 1; i <= 20; i++)
		{
			m_ax = 0;
			m_in = 1000000;
			printf_s("%d %d %d %d\n", tree[i].l, tree[i].r, tree[i].m_ax, tree[i].m_in);
		}*/


		for (int i = 1; i <= q; i++)
		{
			m_ax = 0;
			m_in = 1000000;
			scanf("%d%d", &s, &b);
			query(1,s,b);
			printf("%d\n",m_ax-m_in);
		}
	}
	return 0;
}

• Re:水题，1A，附代码 (1619) chenzhensen 2015-10-24 15:21:18
• Re:水题，1A，附代码 (1619) 522413 2020-08-13 11:04:29