【HDU 1754】I Hate It（线段树/树状数组）

左手的ㄟ右手 2022-04-16 02:16 189阅读 0赞

## 题目：[点击打开题目链接][Link 1] ##

## Problem Description： ##

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。  
这让很多学生很反感。  
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

## Input： ##

本题目包含多组测试，请处理到文件结束。  
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。  
学生ID编号分别从1编到N。  
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。  
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。  
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。  
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

## Output： ##

对于每一次询问操作，在一行里面输出最高成绩。

## Sample Input： ##

5 6  
1 2 3 4 5  
Q 1 5  
U 3 6  
Q 3 4  
Q 4 5  
U 2 9  
Q 1 5

## Sample Output： ##

5  
6  
5  
9

思路：这道题可以用树状数组、线段树都可以，都是单点更新，区间求最大值的过程。

其中用树状数组方法时需要注意查询的过程，要活用查询操作。从R开始查询，然后通过R - lowbit \[ R \] 进行一个区间一个区间的查询来减少时间复杂度，但是如果要查询的区间的左界比L小，就只对此单点进行查询，再进行下一个区间的查询，直到查询到L的位置。

下面是2种方法的代码。

## My DaiMa（树状数组）： ##

#include<iostream>
    #include<stdio.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    int a[200005],build[200005],lowbit[200005],n;
    //lowbit[i]表示i所管辖的数有多少个，也是i的二进制中从右往左第一个1的位置
    void GetLowbit()
    {
        for(int i = 1; i <= n ; i++)
            lowbit[i] = i&(-i);//-x为x的补码
    }
    ///建树，先求出每一段的初始最大值存在build数组里
    void TreeBuild()
    {
        for(int i = 1; i <= n; i++)
        {
            build[i] = a[i];
            for(int j = i-1; j > i-lowbit[i]; j--)
                build[i] = max(build[i],a[j]);
        }
    }
    ///单点更新，更新所有管辖到x的build值
    void update(int x, int y)
    {
        a[x] = y;
        for(int i = x; i <= n; i += lowbit[i])
            build[i] = max(build[i],a[x]);
    }
    ///查询
    int Find_max(int x,int y)
    {
        int maxx = a[y];///从区间右边开始
        while(y != x)
        {
            for(y -= 1; y-lowbit[y] > x; y -= lowbit[y])///根据lowbit进行一个区间一个区间的查询
                maxx = max(maxx,build[y]);
            maxx = max(maxx,a[y]);///当查询的区间的左界小于x时，只对单点进行查询
        }
        return maxx;
    }
    int main()
    {
        int m;
        char ch;
        while(cin >> n >> m)
        {
            for(int i = 1; i <= n; i++)
                scanf("%d",&a[i]);
            GetLowbit();
            TreeBuild();
            int x,y;
            while(m--)
            {
                cin >> ch >> x >> y;
                if(ch == 'U') update(x,y);///单点更新
                else cout << Find_max(x,y) << endl;///查询区间最大值
            }
        }
    }

## My DaiMa（线段树）： ##

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    #include<time.h>
    #pragma GCC optimize(2)
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    typedef unsigned long long ull;
    const int N = 200000;
    struct Node
    {
        int left,right,data;
    }node[4*N];
    
    ///更新当前节点
    void push_up(int root)
    {
        node[root].data = max(node[root<<1].data , node[root<<1|1].data);
    }
    
    ///构建线段树
    void build(int root,int left,int right)
    {
        node[root].left = left;
        node[root].right = right;
        if(left == right)
        {
            scanf("%d",&node[root].data);
            return;
        }
        int mid = (left+right)/2;
        build(root<<1,left,mid);///构建左子树
        build(root<<1|1,mid+1,right);///构建右子树
        push_up(root);
    }
    
    ///单点更新
    void update(int root,int a,int b)
    {
        if(node[root].left == node[root].right && node[root].left == a)
        {
            node[root].data = b;
            return;
        }
        int mid = (node[root].left+node[root].right)/2;
        if(a <= mid) update(root<<1 , a , b);///更新的点在左子树中
        else update(root<<1|1 , a , b);///更新的点在右子树中
        push_up(root);
    }
    
    ///区间查询
    int query(int l,int r,int root)
    {
        if(node[root].left == l && r == node[root].right)
            return node[root].data;
        int mid = (node[root].left+node[root].right)/2;
        if(r <= mid)///说明区间在左子树中
            query(l , r , root<<1);
        else if(mid+1 <= l)///说明区间在右子树中
            query(l, r, root<<1|1);
        else ///说明区间一部分在左子树中，一部分在右子树中，因此劈两半，两边都得查询，取最大值
        {
            int x = query(l, mid, root<<1);///注意这里是mid，而不是r，因为区间被劈了两半
            int y = query(mid+1, r, root<<1|1);
            return max(x,y);
        }
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            build(1, 1, n);
            char ch;
            int a,b;
            while(m--)
            {
                cin >> ch >> a >>b;
                if(ch == 'U')
                    update(1, a, b);
                else
                {
                    int ans = query(a, b, 1);
                    printf("%d\n",ans);
                }
            }
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1754