题目名称 577. 蝗灾
输入输出 locust.in/out
难度等级 ★★★☆
时间限制 2000 ms (2 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2011-07-28加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:135, 提交:329, 通过率:41.03%
Gravatarhytzongxuan 100 1.175 s 35.79 MiB C++
Gravatarliaoy 100 1.224 s 22.03 MiB C++
GravatarAAAAAAAAAA 100 1.330 s 96.44 MiB C++
Gravatarinfi 100 1.379 s 12.90 MiB C++
Gravatarzzuzxy 100 1.706 s 19.01 MiB C++
GravatarLadyLex 100 1.731 s 36.16 MiB C++
GravatarHzoi_moyi 100 1.744 s 12.14 MiB C++
GravatarFisher. 100 1.748 s 49.53 MiB C++
GravatarGo灬Fire 100 1.750 s 25.87 MiB C++
Gravatarkito 100 1.791 s 23.94 MiB C++
本题关联比赛
20110728
关于 蝗灾 的近10条评论(全部评论)
我来考古啦,终于调出来了!
Gravatarzxsoul
2021-08-20 07:34 16楼
CDQ大法好!
GravatarHZOI_蒟蒻一只
2017-07-12 10:22 15楼
CDQ大法好啊
Gravatarsxysxy
2016-12-10 10:20 14楼
树套树卡空间 通过率完蛋了TAT
GravatarDrench
2016-11-17 22:41 13楼
懒得重写了......抄的mokia的代码......
树套树卡不过去了.....CDQ大法好,退树套树保平安......
GravatarAntiLeaf
2016-10-15 14:50 12楼
1.没有绅士来出一个强制在线的盗版题么...要不然对于明明理论效率一样却被卡常数的树套树实在不公平啊
2.两个优化细节:sort改成与cdq同步的归并排序。拆成4个的查询可以拆成2个。
Gravatar喵喵喵
2016-10-13 14:25 11楼
归并排序大法好!
Gravatarliu_runda
2016-10-08 12:09 10楼
分治第一发
Gravatar哒哒哒哒哒!
2016-10-06 08:12 9楼
数组又开小了。。一定要记住要开2(n+m)的!!
以及树状数组一开始向下查询向上修改写反了(不过样例),让我调了一会儿。。
Gravatar_Itachi
2016-10-05 20:40 8楼
VIP CDQ分治,终于搞掉了这道题,lowbit(i)写成lowbit(x) 查了1个多小时TAT...
Gravatar沉迷学习的假的Keller
2016-07-03 21:33 7楼

577. 蝗灾

★★★☆   输入文件:locust.in   输出文件:locust.out   简单对比
时间限制:2 s   内存限制:128 MiB

【题目描述】

C国国土辽阔,地大物博......但是最近却在闹蝗灾.....
我们可以把C国国土当成一个W×W的矩阵,你会收到一些诸如(X,Y,Z)的信息,代表(X,Y)这个点增多了Z只蝗虫,而由于C国政府机关比较臃肿,为了批复消灭蝗虫的请求需要询问一大堆的问题......每个询问形如(X1,Y1,X2,Y2),询问在(X1,Y1,X2,Y2)范围内有多少蝗虫(请注意询问不会改变区域内的蝗虫数),你作为一个C国的程序员,需要编一个程序快速的回答所有的询问。
NOTICE
C国一开始没有蝗虫。

【输入格式】

输入文件的第一行包括一个整数W,代表C国国土的大小。

第二行有一个整数N,表示事件数。

接下来有N行表示N个事件,以(1 X Y Z)的形式或(2,X1,Y1,X2,Y2)的形式给出,分别代表蝗虫的增加和询问。

【输出格式】

对于每个询问输出一个整数表示需要的结果。

【样例输入】

5
8
2 4 1 4 2
1 3 1 8
1 4 4 4
2 1 3 4 4
1 1 5 1
1 4 4 5
2 2 2 5 4
2 3 2 4 4

【样例输出】

0
4
9
9

【数据范围】

10%的数据满足W<=100,N<=100;

30%的数据满足W<=2000,N<=5000;

50%的数据满足W<=100000,N<=50000;

100%的数据满足W<=500000,N<=200000,每次蝗虫增加数不超过1000;