The Water Problem

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5443

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

HINT

题意

查询区间最大值，不带修改

题解：

随便怎么写，反正数据范围只有1000

代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 10505

#define mod 10007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

struct node

{

    int l,r;

    int ma;

};

node a[maxn*];

int num[maxn];

void build(int x,int l,int r)

{

    a[x].l=l,a[x].r=r;

    if(l==r)

    {

        a[x].ma=num[l];

        return;

    }

    int mid=(l+r)>>;

    build(x<<,l,mid);

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

    a[x].ma=max(a[x<<].ma,a[x<<|].ma);

}

int query(int x,int l,int r)

{

    int L=a[x].l,R=a[x].r;

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

        return a[x].ma;

    int mid=(a[x].l+a[x].r)>>;

    if(r<=mid)

        return query(x<<,l,r);

    if(l>mid)

        return query(x<<|,l,r);

    return max(query(x<<,l,mid),query(x<<|,mid+,r));

}

int main()

{

    int t=read();

    while(t--)

    {

        memset(a,,sizeof(a));

        int n=read();

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

            num[i]=read();

        build(,,n);

        int q=read();

        for(int i=;i<q;i++)

        {

            int l=read(),r=read();

            printf("%d\n",query(,l,r));

        }

    }

}

秒客网

hdu 5443 The Water Problem 线段树