The Water Problem

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1308 Accepted Submission(s): 1038

Problem Description

In
Land waterless, water is a very limited resource. People always fight
for the biggest source of water. Given a sequence of water sources with a1,a2,a3,...,an representing the size of the water source. Given a set of queries each containing 2 integers l and r, please find out the biggest water source between al and ar.

Input

First you are given an integer T(T≤10) indicating the number of test cases. For each test case, there is a number n(0≤n≤1000) on a line representing the number of water sources. n integers follow, respectively a1,a2,a3,...,an, and each integer is in {1,...,106}. On the next line, there is a number q(0≤q≤1000) representing the number of queries. After that, there will be q lines with two integers l and r(1≤l≤r≤n) indicating the range of which you should find out the biggest water source.

Output

For each query, output an integer representing the size of the biggest water source.

Sample Input

3
1
100
1
1 1
5
1 2 3 4 5
5
1 2
1 3
2 4
3 4
3 5
3
1 999999 1
4
1 1
1 2
2 3
3 3

Sample Output

100
2
3
4
4
5
1
999999
999999
1

区域赛水题，区间最值。。

//单点更新+区间查找

#include<iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

const int Max = ;

int MAXNUM;

int a[Max];

struct Tree{

    int Max;

    int r,l;

}t[*Max];

int MAX(int k,int j){

    if(k>=j) return k;

    return j;

}

void build(int idx,int l,int r){

    t[idx].l = l;

    t[idx].r=r;

    if(l==r){

        t[idx].Max = a[l];

        return;

    }

    int mid = (l+r)>>;

    build(idx<<,l,mid);

    build(idx<<|,mid+,r);

    t[idx].Max = MAX(t[idx<<].Max,t[idx<<|].Max); //父亲节点

}

void query(int idx,int l,int r,int L,int R){

    if(l>=L&&r<=R) {

        MAXNUM = MAX(MAXNUM,t[idx].Max);

        return;

    }

    int mid = (l+r)>>;

    if(mid>=L)

    query(idx<<,l,mid,L,R);

    if(mid<R)

    query(idx<<|,mid+,r,L,R);

}

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        int n;

        scanf("%d",&n);

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

        }

        build(,,n);

        int m;

        scanf("%d",&m);

        for(int i=;i<=m;i++){

            int l,r;

            scanf("%d%d",&l,&r);

            MAXNUM = -;

            query(,,n,l,r);

            printf("%d\n",MAXNUM);

        }

    }

}

巴特西

hdu 5443(线段树水)

The Water Problem

最新文章

热门文章