• 【POJ No. 1195】 矩形区域查询 Mobile phones


    【POJ No. 1195】 矩形区域查询 Mobile phones

    北大 OJ 题目地址

    在这里插入图片描述

    【题意】

    移动电话的基站区域分为多个正方形单元,形成S ×S 矩阵,行和列的编号为0~S -1,每个单元都包含一个基站。一个单元内活动手机的数量可能发生变化,因为手机从一个单元移动到另一个单元,或手机开机、关机。

    编写程序,改变某个单元的活动手机数量,并查询给定矩形区域中当前活动手机的总数量。

    【输入输出】

    输入:

    输入和输出均为整数。每个输入都占一行,包含一个指令和多个参数。所有值始终在以下数据范围内。

    若A 为负,则可以假设它不会将值减小到零以下。

    • 表大小:1×1≤S ×S ≤1024×1024。
    • 单元值:0≤V ≤32767。
    • 更新量:-32768≤A ≤32767。
    • 输入中的指令数:3≤U ≤60002。
    • 整个表中的最大电话数:M =2^30 。

    在这里插入图片描述

    输出:

    对指令2,单行输出矩形区域中当前活动手机的总数量。

    【样例】

    在这里插入图片描述

    【思路分析】

    这道题包括单点更新与矩形区间和查询,是非常简单的二维树状数组问题。

    算法设计

    直接采用二维树状数组进行点更新和矩阵区间和查询即可。

    注意:本题坐标从0开始,树状数组下标必须从1开始,所以对输入下标做加1处理。

    【算法实现】

    #include
    #include
    #define maxn 1050
    #define lowbit(x) (x)&(-x)
    
    int c[maxn][maxn],n;
    
    void add(int x,int y,int z)//单点更新 
    {
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=n;j+=lowbit(j))
                c[i][j]+=z;
    }
    
    int sum(int x,int y)//区间和:左上角(1,1)到右下角(x,y)矩阵区间和 
    {
        int s=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j))
                s+=c[i][j];
        return s;
    }
    
    int sum(int x1,int y1,int x2,int y2)//求左上角(x1,y1)到右下角(x2,y2)子矩阵区间和 
    {
    	return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
    }
    
    int main()
    {
        int opt,x,y,a,l,b,r,t;
    	while(scanf("%d",&opt)!=EOF)
    	{
    		if(opt==3) break;
    		if(opt==0)
    		{
    			scanf("%d",&n);
        		memset(c,0,sizeof(c));
    		}
    		else if(opt==1)
    		{
                scanf("%d%d%d",&x,&y,&a);
                ++x;++y;
                add(x,y,a);
            }
            else
    		{
                scanf("%d%d%d%d",&l,&b,&r,&t);
                ++l,++b,++r,++t;
                printf("%d\n",sum(l,b,r,t));
            }
    	}
        return 0;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    在这里插入图片描述

  • 相关阅读:
    力扣:300.最长递增子序列
    mysql的代理工具实现读写分离实战
    J9数字论:热存储与冷存储:哪个最安全?
    如何使用NumPy处理数组翻转与变形
    RabbitMQ 消息应答
    微服务中的服务发现是什么?
    k8s编程operator——client-go中的informer
    百度地图API-初步使用(2)
    利用EasyDL制作一个简单的图片识别小项目
    父子项目打包发布至私仓库
  • 原文地址:https://blog.csdn.net/weixin_44226181/article/details/128091502