Code/RMQ.cpp at master · BaoLearns/Code · GitHub

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
/*************************************************************************
    > File Name: RMQ.cpp
    > Author: Royecode
    > Mail: [email protected]
    > Created Time: 2015年09月24日 星期四 19时41分31秒
 ************************************************************************/

#include <iostream>
#include <cmath>

using namespace std;

int d[15][10001];
int n, arr[10001];
void make_RMQ(int n)
{
	int k = log(n) / log(2) + 1;
	for(int i = 1; i <= n; ++i) d[1][i] = arr[i];
	for(int i = 2; i <= k; ++i)
	{
		for(int j = 1; j + (1 << i) - 1 <= n; ++j)
			d[i][j] = min(d[i - 1][j], d[i - 1][j + (1 << (i - 1))]);
	}
	for(int i = 1; i <= k; ++i)
	{
		for(int j = 1; j <= n; ++j)
			cout << d[i][j] << " ";
		cout << endl;
	}
}
int main(int argv, char **argc)
{
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> arr[i];
	make_RMQ(n);
    return 0;
}