P4390 [BOI2007]Mokia 摩基亚

    • 616通过
    • 1.4K提交
  • 题目提供者 strangers
  • 评测方式 云端评测
  • 标签 分治 归并排序 树状数组 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    摩尔瓦多的移动电话公司摩基亚(Mokia)设计出了一种新的用户定位系统。和其他的定位系统一样,它能够迅速回答任何形如“用户C的位置在哪?”的问题,精确到毫米。但其真正高科技之处在于,它能够回答形如“给定区域内有多少名用户?”的问题。

    在定位系统中,世界被认为是一个W×W的正方形区域,由1×1的方格组成。每个方格都有一个坐标(x,y),1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形,就有1<=x<=4,1<=y<=4(如图):

    请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

    输入输出格式

    输入格式:

    有三种命令,意义如下:

    命令 参数 意义

    • 0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
    • 1 x y A 向方格(x,y)中添加A个用户。A是正整数。
    • 2 X1 Y1 X2 Y2 查询X1<=x<=X2,Y1<=y<=Y2所规定的矩形中的用户数量
    • 3 无参数 结束程序。本命令仅结束时出现一次。

    输出格式:

    对所有命令2,输出一个一行整数,即当前询问矩形内的用户数量。

    输入输出样例

    输入样例#1: 复制
    0 4
    1 2 3 3
    2 1 1 3 3
    1 2 2 2
    2 2 2 3 4
    3
    输出样例#1: 复制
    3
    5
    

    说明

    对于所有数据:

    1<=W<=2000000
    1<=X1<=X2<=W
    1<=Y1<=Y2<=W
    1<=x,y<=W
    0<A<=10000
    命令1不超过160000个。
    命令2不超过10000个。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。