传送门
描述
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.
输入
Line 1: Two space-separated integers, N and Q.
Lines 2.. N+1: Line i+1 contains a single integer that is the height of cow iLines N+2.. N+ Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
输出
Lines 1.. Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
样例
- 输入6 31734251 54 62 2
- 输出630
思路
- 题意:给n个数和m次询问,每次询问给l和r,求区间[l,r]中最大值和最小值的差值。
- st[i][j]表示区间[i,i+2^j-1]内的最值。
- 以最大值为例,
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1])
。- 询问区间[l,r]时,取区间
[l,l+(1<<k)]
和[r-(1<<k)+1][r]
,其中k=log(r-l+1.0)/log(2.0)
,这样两个区间必有交集,则两个区间的最大值的最大值就一定是[l,r]的最大值。- st表构造O(nlgn),查找O(1)。当需要多次查找区间最值,不需要进行修改操作时,st表比线段树、树状数组更好用。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include |