程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> nyoj 119士兵殺敵（三）(線段樹區間最值查詢，RMQ算法)

nyoj 119士兵殺敵（三）(線段樹區間最值查詢，RMQ算法)

編輯：C++入門知識

nyoj 119士兵殺敵（三）(線段樹區間最值查詢，RMQ算法)

士兵殺敵（三）

描述

南將軍統率著N個士兵，士兵分別編號為1~N,南將軍經常愛拿某一段編號內殺敵數最高的人與殺敵數最低的人進行比較，計算出兩個人的殺敵數差值，用這種方法一方面能鼓舞殺敵數高的人，另一方面也算是批評殺敵數低的人，起到了很好的效果。

所以，南將軍經常問軍師小工第i號士兵到第j號士兵中，殺敵數最高的人與殺敵數最低的人之間軍功差值是多少。

現在，請你寫一個程序，幫小工回答南將軍每次的詢問吧。

注意，南將軍可能詢問很多次。

輸入

只有一組測試數據
第一行是兩個整數N,Q，其中N表示士兵的總數。Q表示南將軍詢問的次數。(1 隨後的一行有N個整數Vi(0<=Vi<100000000)，分別表示每個人的殺敵數。
再之後的Q行，每行有兩個正正數m,n，表示南將軍詢問的是第m號士兵到第n號士兵。

輸出

對於每次詢問，輸出第m號士兵到第n號士兵之間所有士兵殺敵數的最大值與最小值的差。

樣例輸入

樣例輸出

1
7

看到這樣的題就想到線段樹唉還是知道的算法太少了

第一次線段樹還超時了（粗心忘記寫return 了）

還可以用RMQ算法（比線段樹快多了。。）。百度的。。。。

線段樹 1836ms 險過。。。

#include 
#include 
using namespace std;
struct node
{
int left,right;
int max_num,min_num;
}tree[100000*4];
void build(int left,int right,int root)
{
tree[root].left=left;
tree[root].right=right;
if(left==right)
{
scanf("%d",&tree[root].max_num);
tree[root].min_num=tree[root].max_num;
return ;
}
else
{
int mid=(left+right)/2;
build(left,mid,root*2);
build(mid+1,right,root*2+1);
tree[root].max_num=max(tree[root*2].max_num,tree[root*2+1].max_num);
tree[root].min_num=min(tree[root*2].min_num,tree[root*2+1].min_num);
}
}
void search(int l,int r,int root,int &c,int &d)
{
if(tree[root].left==l&&tree[root].right==r)
{
c=tree[root].max_num;
d=tree[root].min_num;
return ;
}
int mid=(tree[root].left+tree[root].right)/2;
if(mid>=r)
search(l,r,root*2,c,d);
else if(mid

RMQ算法 976ms 節省了近一倍的事件。如果不懂RMQ (Range Minimum/Maximum Query)算法，看下文：

#include 
#include 
#include 
using namespace std;
int min_num[100005][20];
int max_num[100005][20];
int n,k;
void RMQ()
{
	for(int i=1;i<20;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j+(1<