1174 区间中最大的数(线段树)

2017年07月14日 11点热度 0人点赞 0条评论
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

1174 区间中最大的数(线段树) 收藏

1174 区间中最大的数(线段树) 关注
给出一个有N个数的序列,编号0 - N - 1。进行Q次查询,查询编号i至j的所有数中,最大的数是多少。

例如: 1 7 6 3 1。i = 1, j = 3,对应的数为7 6 3,最大的数为7。(该问题也被称为RMQ问题)
Input
第1行:1个数N,表示序列的长度。(2 <= N <= 10000)
第2 - N + 1行:每行1个数,对应序列中的元素。(0 <= S[i] <= 10^9)
第N + 2行:1个数Q,表示查询的数量。(2 <= Q <= 10000)
第N + 3 - N + Q + 2行:每行2个数,对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1)
Output
共Q行,对应每一个查询区间的最大值。
Input示例
5
1
7
6
3
1
3
0 1
1 3
3 4
Output示例
7
7

3

#include
#include
using namespace std;
int n,q,a,b,mx[10002*4];
void buildtree(int l,int r,int rt)
{
    if(l==r)
    {
        cin>>mx[rt];
        return;
    }
    int mid=(l+r)/2;
    buildtree(l,mid,rt*2);
    buildtree(mid+1,r,rt*2+1);
    mx[rt]=max(mx[rt*2],mx[rt*2+1]);
}
int querymx(int l,int r,int rt,int ll,int rr)
{
    if(ll<=l&&rr>=r) return mx[rt];
    int mid=(l+r)/2,cnt=0;
    if(l<=rr&&ll<=mid) cnt=max(cnt,querymx(l,mid,rt*2,ll,rr));
    if(mid>n;
    buildtree(1,n,1);
    cin>>q;
    while(q--)
    {
        cin>>a>>b;
        cout<

未经允许不得转载!1174 区间中最大的数(线段树)

update

纸上得来终觉浅, 绝知此事须躬行。