NYOJ 119 士兵殺敵（三）

士兵殺敵（三） 時(shí)間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：5 描述

南將軍統(tǒng)率著N個(gè)士兵，士兵分別編號(hào)為1~N,南將軍經(jīng)常愛拿某一段編號(hào)內(nèi)殺敵數(shù)最高的人與殺敵數(shù)最低的人進(jìn)行比較，計(jì)算出兩個(gè)人的殺敵數(shù)差值，用這種方法一方面能鼓舞殺敵數(shù)高的人，另一方面也算是批評(píng)殺敵數(shù)低的人，起到了很好的效果。

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

現(xiàn)在，請(qǐng)你寫一個(gè)程序，幫小工回答南將軍每次的詢問吧。

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

輸入 只有一組測(cè)試數(shù)據(jù)
第一行是兩個(gè)整數(shù)N,Q，其中N表示士兵的總數(shù)。Q表示南將軍詢問的次數(shù)。(1<N<=100000,1<Q<=1000000)
隨后的一行有N個(gè)整數(shù)Vi(0<=Vi<100000000)，分別表示每個(gè)人的殺敵數(shù)。
再之后的Q行，每行有兩個(gè)正正數(shù)m,n，表示南將軍詢問的是第m號(hào)士兵到第n號(hào)士兵。 輸出 對(duì)于每次詢問，輸出第m號(hào)士兵到第n號(hào)士兵之間所有士兵殺敵數(shù)的最大值與最小值的差。 樣例輸入

5?2
1?2?6?9?3
1?2
2?4

樣例輸出

1
7

來源 經(jīng)典改編 上傳者

張?jiān)坡?/p>

#include#include#includeusing?namespace?std;

const?int?N?=?100010;
int?maxsum[N][20],?minsum[N][20];

void?RMQ(int?num)?//預(yù)處理->O(nlogn)
{
	for(int?j?=?1;?j?<?20;?++j)
		for(int?i?=?1;?i?<=?num;?++i)
			if(i?+?(1?<<?j)?-?1?<=?num)
			{
				maxsum[i][j]?=?max(maxsum[i][j?-?1],?maxsum[i?+?(1?<<?(j?-?1))][j?-?1]);
				minsum[i][j]?=?min(minsum[i][j?-?1],?minsum[i?+?(1?<<?(j?-?1))][j?-?1]);
			}
}

int?main()
{
	int?num,?query;
	int?src,?des;
	scanf("%d?%d",?&num,?&query);
		for(int?i?=?1;?i?<=?num;?++i)?//輸入信息處理
		{
			scanf("%d",?&maxsum[i][0]);
			minsum[i][0]?=?maxsum[i][0];
		}
		RMQ(num);
		while(query--)?//O(1)查詢
		{
			scanf("%d?%d",?&src,?&des);
			int?k?=?(int)(log(des?-?src?+?1.0)?/?log(2.0));
			int?maxres?=?max(maxsum[src][k],?maxsum[des?-?(1?<<?k)?+?1][k]);
			int?minres?=?min(minsum[src][k],?minsum[des?-?(1?<<?k)?+?1][k]);
			printf("%dn",?maxres?-?minres);
		}
	return?0;
}

對(duì)數(shù)函數(shù)log（）默認(rèn)以e為底 ?將 x 的自然對(duì)數(shù)值除以 n 的自然對(duì)數(shù)值，就可以對(duì)任意底 n 來計(jì)算數(shù)值 x 的對(duì)數(shù)值：
Logn(x) = Log(x) / Log(n) ?換底公式

題目詳解

RMQ算法