# 14309: 【原4309】询问区间max

### 题目描述

author: DS-TA Group2020 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4309

## Sample Input

10
1
5
2
6
8
9
11
20
4
5
6
1 2
1 5
1 6
1 7
1 8
8 9


## Sample Output

5
8
9
11
20
20


## q4x3's solution

/**
* 区间最大问题
* 拿线段树混的
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

const int MAXN = 1e5 + 233;
int dt[MAXN], tree[MAXN << 2];
int m, n, l, r;

int maxx(int x, int y) {
return x > y ? x : y;
}

void build(int l, int r, int rt) {
if(l == r) {
tree[rt] = dt[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = maxx(tree[rt << 1], tree[rt << 1 | 1]);
}

int query(int rt, int l, int r, int s, int t) {
if(s <= l && t >= r) return tree[rt];
int mid = (l + r) >> 1;
if(t <= mid) return query(rt << 1, l, mid, s, t);
else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
else return maxx(query(rt << 1, l, mid, s, t),
query(rt << 1 | 1, mid + 1, r, s, t));
}

int main() {
scanf("%d", &n);
for(int i = 1;i <= n;++ i)
scanf("%d", &dt[i]);
build(1, n, 1);
scanf("%d", &m);
for(int i = 1;i <= m;++ i) {
scanf("%d%d", &l, &r);
printf("%d\n", query(1, 1, n, l, r));
}
}


## victrid's solution

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
//I'm fool
//1e5 <=> 10000->0<-
int nums[100005];
int st[100005][20];
inline int lg(int n) { return n ? lg(n / 2) + 1 : -1; }
int main() {
int n, k, lgn;
scanf("%d", &n);
lgn = lg(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &nums[i]);
st[i][0] = i;
}
for (int j = 1; j <= lgn; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = nums[st[i][j - 1]] > nums[st[i + (1 << (j - 1))][j - 1]] ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
}
//...... the rr - ll + 1 problem
int ll, rr;
scanf("%d", &k);
while (k--) {
scanf("%d%d", &ll, &rr);
printf("%d\n", max(nums[st[ll][lg(rr - ll + 1)]], nums[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]]));
}
return 0;
}