HDU 5443 – The Water Problem [RMQ水题]

点击打开HDU题目链接

题意

给定一个数列,求区间[l, r]的最大值

分析

这题后台数据实在是很水,各种姿势暴都没问题。今天写线段树的RMQ发现最近数据结构的题一直依赖队友,竟然不会写了……

C++代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int v[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i]);
        int q; scanf("%d", &q);
        while(q--) {
            int l, r; scanf("%d%d", &l, &r);
            printf("%d\n", *max_element(v+l, v+r+1));
        }
    }
    return 0;
}

C++线段树代码

#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 1024;
int Max[maxn<<2];

void pushUp(int rt) {
    Max[rt] = max(Max[rt<<1], Max[rt<<1|1]);
}

void build(int l, int r, int rt) {
    if(l == r) {
        scanf("%d", &Max[rt]);
        return;;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushUp(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if(l >= L && r <= R)
        return Max[rt];
    int m = (l + r) >> 1;
    int ret = INT_MIN;
    if(L <= m) ret = max(ret, query(L, R, lson));
    if(R > m) ret = max(ret, query(L, R, rson));
    return ret;
}


int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        build(1, n, 1);
        int q; scanf("%d", &q);
        while(q--) {
            int l, r; scanf("%d%d", &l, &r);
            printf("%d\n", query(l, r, 1, n, 1));
        }
    }
    return 0;
}

欢迎留言