线段树单点更新区间最大值 hdoj1754I Hate It

待我称王封你为后i 2022-09-20 15:21 334阅读 0赞

题目：hdoj1754 I Hate It

分析：更新的话，建树的时候保存叶子编号的的节点信息，然后从下往上更新就ok。

求和的话，从根节点开始，然后找在根的左边还是右边，然后递归找一个所有中的最大值即可、

代码：

#include <cstdio>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    const int N = 205000;
    struct Node
    {
        int l,r;
        int sum;
    };
    Node tree[4*N];
    int a[N];
    int fa[N];
    void build(int l,int r,int v)
    {
        tree[v].l=l;
        tree[v].r=r;
        if(l==r)
        {
            fa[l]=v;
            tree[v].sum=a[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,v*2);
        build(mid+1,r,v*2+1);
        tree[v].sum=max(tree[v+v].sum,tree[v+v+1].sum);
    }
    
    void update(int t,int p,int x)
    {
        if(tree[t].sum<p)
            tree[t].sum=p;
        if(t==1)
            return ;
        update(t/2,p,x);
    }
    int queue(int a,int b,int v)
    {
        if(tree[v].l==a&&tree[v].r==b)
        {
            return tree[v].sum;
        }
        int mid=(tree[v].l+tree[v].r)>>1;
        if(b<=mid) return queue(a,b,v+v);
        else if(a>mid) return queue(a,b,v+v+1);
        else return max(queue(a,mid,v*2),queue(mid+1,b,v*2+1));
    }
    int main()
    {
        //freopen("a.txt","r",stdin);
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            build(1,n,1);
            while(m--)
            {
                char c;
                int x,y;
                scanf("%*c%c",&c);
                scanf("%d%d",&x,&y);
                if(c=='Q')
                    printf("%d\n",queue(x,y,1));
                else if(c=='U')
                    update(fa[x],y,x);
            }
        }
        return 0;
    }