http://acm.hdu.edu.cn/showproblem.php?pid=5283
池塘里有一些鱼和一个渔网，池塘可以看成一个二维的平面，而渔网可以看成一个与坐标轴平行的矩形。每条鱼都被给予了一个标号，分别从 1 到n标号， n 表示池塘里鱼的总数。鱼的游动可以概括为两个动作： 1 l r d : 表示标号在[l， r ]这个区间内的鱼向x轴正方向游动了 d 个单位长度。 2 l r d ：表示标号在[l， r ]这个区间内的鱼向y轴正方向游动了 d 个单位长度。 还有询问操作：3 l r 表示询问现在标号在[ l ，r]这个区间内的鱼有多少在渔网内。
第一行包含一个整数 T ，表示测试数据组数。 对于每组测试数据： 第一行包含一个整数n表示鱼的总数。 第二行包含四个整数 x1 , y1 , x2 , y2 ，表示渔网的左下角坐标和右上角坐标。 接下来 n 行每行两个整数xi, yi ，表示标号为i的鱼初始时刻的坐标。 接下来一行包含一个整数 m ，表示后面的事件数目。 接下来的m行每行为以下三种类型的一种： 1 l r d : 表示标号在[ l ，r]这个区间内的鱼向 x 轴正方向游动了d个单位长度。 2 l r d：表示标号在[ l ，r]这个区间内的鱼向 y 轴正方向游动了d个单位长度。 3 l r : 表示询问现在标号在[l， r ]这个区间内的鱼有多少在渔网内。
对于每组数据的每个询问，输出一个整数表示对应的答案。
对于30%的数据1≤n, m ≤1000 对于100%的数据1≤T≤10,1≤ n ,m≤30000,1≤ l ≤r≤ n . 1≤d≤10^9 , x1 ≤ x2 , y1 ≤ y2 。保证任意时刻所有涉及的坐标值在[−10^9,10^9]范围内。
事先说明：这一题代码普遍很长。
首先我们看到数据范围中1≤ d ≤109 ，说明鱼的坐标是单调不下降的，鱼只会不停地往上游和往右游，这样问题就简单了许多，至少不会左右上下都游。
用三棵线段树维护 x ，y坐标以及答案。 区间[ l ,r]维护小于 x1 的最大的 xi 、大于等于 x1 小于等于 x2 的 xi 的最大值、小于 y1 的最大的 yi ，大于等于 y1 小于等于 y2 的 yi 的最大值，以及该区间内有多少条鱼游进了渔网（即该区间的答案）。
询问时直接递归询问线段树累计答案即可。
主要的问题是修改，怎么修改呢？
如果某段区间加 k ，那么这段区间维护的那两个最大值也要加k。 这是我们看一下存不存在小于 x1 ( y1 )的最大值大于 x1 ( y1 )，如果有，就说明至少存在一条原本横坐标(纵坐标)本来不属于合法范围内，后来又进入了合法范围的鱼，我们遍历一遍线段树，找到这条鱼，这条鱼的横坐标(纵坐标)刚刚进入了合法范围内，再看一下它的纵坐标(横坐标)是否已在合法范围内，是，就给对应区间答案加 1 ，否则不加。
为了能够保证在找到这条鱼的时候这条鱼的横纵坐标已更新到最新，所以我们在遍历线段树的时候横纵坐标的标记都要下传。
然后再看一下有没有鱼因为这次修改游出了渔网，判断方法以及维护方法和上述方法差不多，最后把找到的鱼删除，具体实现为可以把它的横纵坐标赋值为超级小的值。
再看看时间复杂度，一条鱼至多游进合法范围2次，游出渔网 1 次，共3次，一共有 n 条鱼，每次询问log n 次，总时间复杂度为O( n log n <script type="math/tex" id="MathJax-Element-135">n</script>)，当然不会超时。
