如果按 $y$ 从小到大扫，上边界本来就要加一。
$y+w$ 不用减一是因为 $y+w-1+1=y+w$。
by jr_linys @ 2023-08-16 10:30:55
若减的线段不变（$y+w-1$），那么要先加后减。
若减的线段加一（$y+w$），那么要先减后加。
只是对边界处理的区别。
by jr_linys @ 2023-08-16 10:41:11
@[jr_linys](/user/667763) 你说的第一种我过不了，之前就这么写的，第二种可过，请问为什么
by Chinshyo @ 2023-08-28 20:47:36
@[qxhAwA](/user/312820) 我能过。
如果第一种写法的话每次修改后都要更新答案。
by jr_linys @ 2023-08-30 00:43:51
经检验，正确的
by Acerakoi @ 2024-01-16 20:51:53
@[FFFFFAN](/user/240724) 我的做法是离散 $y$ 按照 $x$ 轴排序，但是我不太理解为什么会被 $hack$，您的推测原因看不太懂。。。
by Acerakoi @ 2024-01-16 20:57:21
我懂了，先减去的话对 $x$ 一个区间的左端点无法造成影响，但是会先让右端点的亮度减去无法记入，所以 $x$ 不能减去 1。
is it?
by Acerakoi @ 2024-01-16 21:16:37
您说："高不该减一，只需要宽减一"，对应我的写法是，只需要高减一，但是为什么我的高减去 1 之后还是 WA #9，要两个都不减 1 才能 AC。
by Acerakoi @ 2024-01-16 21:19:07
@[Acerakoi](/user/514850) 先删后加时长宽都无需减一、先加后删时只需宽减一。
我的做法为，对 $y$ 使用离散线段树，将线按 $x$ 排序，每处理完一根线时统计答案（**如果有多个线的 $x$ 坐标相同，则每处理一个都会统计一次答案**）。
高无需减一是因为离散线段树的区间操作不包括右端点，因而相当于自动减去了一。
宽是否需要减一，重点在于删和加的顺序。对于星星扩展成的一个框，我们默认**只能看到左边界而不能看到右边界**。
- 假如宽不减一，那么对于同一个 $x$ 坐标，即对于这一条扫描线，以这一条扫描线为右边界的所有星星不应被看见，而以这一条扫描线为左边界的所有星星应该被看见，因此**在加入新的星星前应该先删除**。
- 若宽度减一，则在减一过后的右边界就可以看到该星星，因而**在删除星星前应该先加入**。
因此，对宽度的处理，有以下几种方案：
1. 不减一，并先删后加
2. 减一，并先加后删
3. （推荐做法）在扫描过程中，连续处理完所有 $x$ 坐标相同的线后再统计答案。这样即无需考虑删和加的顺序，也无需对宽度处理，同时也减少了统计次数，轻微地提高了运行效率。
第三个方案是最优秀也最方便的，推荐学习。我想，当初学习扫描线时也是受到了题解和课程的影响而忽略了算法可能的改进，直到现在才忽而发现，但这何尝不是我们学习算法的乐趣之一。
by FFFFFAN @ 2024-01-17 13:29:17