-
Notifications
You must be signed in to change notification settings - Fork 248
/
SparseTable.cpp
80 lines (63 loc) · 1.84 KB
/
SparseTable.cpp
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*************************************************************************************
Sparse table. Solves static RMQ problem (without element changes).
O(NlogN) on precalculation, O(1) on query.
Based on problem 3309 from informatics.mccme.ru:
http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3309
*************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 2 * 105000;
const int MAXLOG = 20;
int n, m;
int a[MAXN];
int table[MAXLOG][MAXN];
int numlog[MAXN];
void buildTable() {
numlog[1] = 0;
for (int i = 2; i <= n; i++)
numlog[i] = numlog[i / 2] + 1;
for (int i = 0; i <= numlog[n]; i++) {
int curlen = 1 << i;
for (int j = 1; j <= n; j++) {
if (i == 0) {
table[i][j] = a[j];
continue;
}
table[i][j] = max(table[i - 1][j], table[i - 1][j + curlen / 2]);
}
}
}
int getMax(int l, int r) {
int curlog = numlog[r - l + 1];
return max(table[curlog][l], table[curlog][r - (1 << curlog) + 1]);
}
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
buildTable();
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d ", getMax(l, r));
}
return 0;
}