I Hate it-HDU1754 点修改+区间最大值

题意：

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，

现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

链接： http://acm.hdu.edu.cn/showproblem.php?pid=1754

思路：

基本的线段树点修改+查询区间最大值

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e5+;

int tree[MAXN<<];int a[MAXN];

void push_up(int node)

{

    tree[node]=max(tree[node<<],tree[node<<|]);

}

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

{

    if(l==r)

    {

        tree[node]=a[l];return;

    }

    int mid=(l+r)>>;

    build(node<<,l,mid);

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

    push_up(node);

}

void update(int node,int l,int r,int i,int k)

{

    int mid=(l+r)>>;

    if(l==r)

    {

        a[l]=k;tree[node]=k;

        return;

    }

    if(i<=mid)

        update(node<<,l,mid,i,k);

    else

        update(node<<|,mid+,r,i,k);

    push_up(node);

}

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

{

    if(x<=l&&y>=r)

    {

        return tree[node];

    }

    int res=;

    int mid=(l+r)>>;

    if(x<=mid)

        res=max(res,query(node<<,l,mid,x,y));

    if(y>mid)

        res=max(res,query(node<<|,mid+,r,x,y));

    return res;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

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

        build(,,n);

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

        {

            char str[];

            scanf("%s",str);

            int x,y;

            if(str[]=='Q')

            {

                scanf("%d%d",&x,&y);

                printf("%d\n",query(,,n,x,y));

            }

            else

            {

                scanf("%d%d",&x,&y);

                update(,,n,x,y);

            }

        }

    }

    return ;

}

巴特西

I Hate it-HDU1754 点修改+区间最大值

最新文章

热门文章