14309: 【原4309】询问区间max

题目

题目描述

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

Description

助教不仅有树，还有一串长为n的数组（下标是1-base），他灵机一动，又想了一个考你的办法。

共有m次询问，每次询问都给出l,r，你需要回答助教原数组里区间[l,r]中的最大值。

数据范围是：$n\leq 1e5$, $m \leq 1e5$, $a[i]\leq 1e6$

Input Format

第一行一个数字n，表示数组长度。

接下来n行，每行一个数字a[i]，即为数组i位置上的数字。

然后是一个数字m，表示询问次数。

接下来m行，每行一对l,r（保证l不大于r），代表助教的询问。

Output Format

对于每个询问输出一行，表示区间最大值

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;
}