这道题的意思是：给你n个点，每个数出现的位置对应着改点数的大小。然后给出m个区间输出每个区间上的最大值与最小值的差。
典型的线段树啊，自己写的那个代码很搓，然后啸爷教了我，他怎么写的，就学习了一下。以后尽量写的好一点啊。
主要是线段树的建立与查找。
| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 31222 | Accepted: 14709 | |
| Case Time Limit: 2000MS | ||
Description
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range
of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest
cow in the group.
Input
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.
Output
Sample Input
6 3 1 7 3 4 2 5 1 5 4 6 2 2
Sample Output
6 3 0
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-7
#define M 10001000
//#define LL __int64
#define LL long long
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
const int maxn = 50100;
using namespace std;
struct node
{
int a, b;
int Max, Min;
} f[4*maxn];
int cnum[maxn];
void Bulid(int l, int r, int site)
{
if(l == r)
{
f[site].a = l;
f[site].b = r;
f[site].Max = cnum[l];
f[site].Min = cnum[l];
return ;
}
int mid = (l+r)/2;
Bulid(l, mid, site*2);
Bulid(mid+1, r, site*2+1);
f[site].Max = max(f[site*2].Max, f[site*2+1].Max);
f[site].Min = min(f[site*2].Min, f[site*2+1].Min);
f[site].a = l;
f[site].b = r;
}
node Search(int l, int r, int site)
{
if(l == f[site].a && r == f[site].b)
return f[site];
int mid = (f[site].a+f[site].b)/2;
if(r <= mid)
{
return Search(l, r, 2*site);
}
else if(l > mid)
{
return Search(l, r, site*2+1);
}
else
{
node p1 = Search(l, mid, site*2);
node p2 = Search(mid+1, r, site*2+1);
node p;
p.Max = max(p1.Max, p2.Max);
p.Min = min(p1.Min, p2.Min);
return p;
}
}
void Updata(int m, int d, int site)
{
if(f[site].a == f[site].b)
{
f[site].Max = f[site].Min = d;
return;
}
int mid = (f[site].a+f[site].b)/2;
if(m <= mid)
{
Updata(m, d, 2*site);
}
else
{
Updata(m, d, 2*site+1);
}
f[site].Max = max(f[site*2].Max, f[site*2+1].Max);
f[site].Min = min(f[site*2].Min, f[site*2+1].Min);
}
int main()
{
int n, m;
while(scanf("%d %d",&n, &m) != EOF)
{
for(int i = 1; i <= n; i++)
scanf("%d",&cnum[i]);
Bulid(1, n, 1);
int a, b;
while(m--)
{
scanf("%d %d",&a, &b);
node p;
p = Search(a, b, 1);
printf("%d\n",p.Max-p.Min);
}
}
return 0;
}