Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
98 lines (79 sloc) 2.1 KB
/*************************************************************************************
Segment tree. Solves RMQ problem (maximum on a segment and value update)
O(N) on precalculation, O(logN) 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 = 105000;
const int INF = (int) 1e9;
int n, num, qn;
int a[MAXN];
int tree[4 * MAXN];
int l, r;
int getMax(int l, int r) {
l = num + l - 1; r = num + r - 1;
int res = -INF;
while (l <= r) {
if (l & 1) {
res = max(res, tree[l]);
l++;
}
if (r % 2 == 0) {
res = max(res, tree[r]);
r--;
}
l /= 2; r /= 2;
}
return res;
}
void update(int pos, int val) {
pos = num + pos - 1;
tree[pos] = val;
pos /= 2;
while (pos >= 1) {
tree[pos] = max(tree[pos * 2], tree[pos * 2 + 1]);
pos /= 2;
}
}
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]);
num = 1;
while (num < n)
num *= 2;
for (int i = num; i < 2 * num; i++) {
if (i - num + 1 <= n)
tree[i] = a[i - num + 1];
else
tree[i] = -INF;
}
for (int i = num - 1; i >= 1; i--) {
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
scanf("%d", &qn);
for (int i = 1; i <= qn; i++) {
scanf("%d %d", &l, &r);
printf("%d ", getMax(l, r));
}
return 0;
}