关于小鱼之美的近10条评论(全部评论)
回复 @Mike is Fool : 呃。。。。。。造数据的时候没有严格控制这个。。。总之在空间允许时间还够的时候全体long long就好了。。 Sky_miner 2016-11-10 15:01 8楼
回复 @Sky_miner : 这个题可以整体二分。每条鱼在网内的时间连续，我们可以二分求取每条鱼在网内的最早时刻和最晚时刻，然后改成时间轴差分序列，空间轴用bit求和，复杂度为O(nlog^2n) 学长，第9个点，中间似乎有点问题，计算偏移量的时候int爆了。 FoolMike 2016-11-10 13:12 7楼
回复 @Mike is Fool : 其实这道题用线段树直接维护就可过。。整体二分什么的好像不需要 Sky_miner 2016-11-10 06:01 6楼
整体二分+线段树+树状数组。估计是哪里写WA了 FoolMike 2016-11-09 22:23 5楼
题解:http://www.cnblogs.com/Skyminer/p/6047555.html Sky_miner 2016-11-09 16:41 4楼
小鱼之美函数的美　树之美强迫症福利QAQ Tiny 2016-11-09 08:21 3楼
生快！ AntiLeaf 2016-11-09 08:17 2楼
SM生快 YGOI_真神名曰驴蛋蛋 2016-11-09 08:00 1楼

2533. [HZOI 2016] 小鱼之美

★★★☆ 输入文件：skyfishs.in 输出文件：skyfishs.out 简单对比
时间限制：5 s 内存限制：1024 MiB

Sky_miner的生日到了！

为了庆祝Sky_miner的生日，Sky_miner去抓鱼啦！

Sky_miner来到了平静的大海上，一个大海可以理解为一个二维平面。

Sky_miner在大海上撒下了一张渔网，一张渔网可以理解为一个于坐标轴平行的矩形

Sky_miner通过在海边架起的心灵监控器得知了小鱼的运动方式及时间，可是Sky_miner不知道到底什么时候收网才能获得最多的鱼。所以就有你来帮忙了！

Sky_miner从海边的心灵监控仪处获得了一系列小鱼移动的信息，每一条信息如下：

move in x-area l r d

move in y-area l r d

表示全球 $id$ 在 $l,r$ 之间的鱼向x(y)轴正方向移动了 $d$ 个单位长度。由于心灵控制器的存在，$d$ 恒大于零。

但是sky_miner蒙了，他不知道什么时候收网能获得多少鱼，所以这就交给你了。

Sky_miner的询问如下:

$query\ l\ r$ 表示询问全球 $id$ 在 $l,r$ 之间的鱼有多少鱼在网中（包括渔网边界）

多组测试数据：

第一行一个整数 $T$，表示测试数据的组数。

对于每组测试数据，第一行一个正整数 $n$，表示鱼的数量。

接下来一共有 $n$ 行，每一行包括两个整数 $x_i,y_i$，第 $i+1$ 行表示全球 $id$ 为 $i$ 的鱼的初始坐标。

下面一行四个正整数 $x_1,y_1,x_2,y_2$ 分别表示渔网左下角的坐标和右上角的坐标

然后一行一个正整数 $m$，表示操作的总次数。

每个操作将会被如下形式给出:

$1\ l\ r\ d$ 表示 $id$ 在 $[l,r]$ 这个区间内的鱼向x轴正方向游动了d个单位长度。

$2\ l\ r\ d$ 表示 $id$ 在 $[l,r]$ 这个区间内的鱼向y轴正方向游动了d个单位长度。

$3\ l\ r$ 表示询问现在 $id$ 在 $[l,r]$ 这个区间内的鱼有多少在渔网内

对于每一个询问，输出询问的答案

5
4

数据范围：

$1\le n,m\le 100000$

$1\le l\le r\le n$

$1\le d\le 10^9$

$x_1\le x_2,y_1\le y_2$

保证任意时刻的坐标绝对值不超过 $10^9$。

HZOI 2016