假装是计几的线段树题
问题描述
在二维平面上，摄像机在 $(0,0)$ 的位置，初始时平面上没有障碍物。现在执行 $Q$ 次操作，操作有两种（假设这是第 $i$ 次操作， $1 \leq i \leq Q$ ）：
- 给定 $x_0, y_0, x_1, y_1(x_0 < x_1, y_0 < y_1>)$ ，创建一个每条边与坐标轴平行的长方形障碍物，包含所有满足 $x_0 \leq x \leq x_1$ 且 $y_0 \leq y_1$ 的点（如果这个区域的某一部分已经存在障碍，则直接覆盖掉它，具体请看样例）。这个障碍物的编号为 $i$ 。
- 给定向量 $(x,y)$ ，会有一个动点从摄像机所在的 $(0,0)$ 位置出发，以 $(x,y)$ 所指的方向前进，直到碰到第一个障碍物为止。
对于第2种操作，输出最先碰到的障碍物的编号。若不会碰到任何障碍物，输出0。
输入格式
第一行一个正整数 $Q$ ，表示操作总数。
接下来的 $Q$ 行，每行第一个正整数 $opi$ 为操作种类（保证为 $1$ 或 $2$ ）。如果为 $1$ ，则加下来的四个整数 $x_0, y_0, x_1, y_1(x_0 < x_1, y_0 < y_1>)$ 表示障碍物的位置；如果为 $2$ ，则接下来两个正整数 $x,y$ 表示前进的方向。
输出格式
共 $R$ 行（ $R$ 为第 $2$ 种操作的总数），每行一个正整数，表示第一个碰到的障碍物编号。
样例输入
10
1 3 3 10 4
1 4 2 5 6
2 6 2
1 2 8 4 10
1 0 6 3 9
2 5 2
2 8 6
2 2 9
2 4 7
1 5 7 10 10
样例输出
1
2
2
5
0
数据规模与约定
对于所有数据，保证 $x0$ 与 $y0$ 不全为0， $x$ 和 $y$ 不全为 $0$
| 测试点编号 | $Q\leq$ | $x_0,y_0,x_1,y_1,x,y\leq$ | 特殊性质 |
|---|---|---|---|
| 1,2 | 1000 | $10^9$ | 无 |
| 3,4 | 100000 | $200$ | 无 |
| 5,6 | 100000 | $10^9$ | $x_0=x_1-1$ |
| 7,8,9,10 | 100000 | $10^9$ | 无 |
Solution
考虑新加入的一个矩形对答案的影响，只有与 $(x_0,y_0)$ 相邻的两条边。所以对答案有影响的点，只有 $(x_0, y_1), (x_0, y_0), (x_1, y_0)$ 三个点。因此将操作离线，将所有矩形的这三个点与询问的 $(x,y)$ 一起按极角排序离散化，于是每个询问就对应离散化后序列上的一个点，而修改则对应序列上的一段区间。
边分两种，横边和竖边，我们分开考虑，开两棵线段树。
对于新加入的一个矩形，我们在横边线段树上查找横边所在区间，如果当前距离原点的距离比树上记录的大就更新，并把标记赋值为 $i$ ，竖边同理。
对于询问，就是在横线段树和竖线段树上查询一个点的值（即光线最先碰道的横边与最先碰到的竖边），然后判断哪个更优即可。
我考场上代码中写的标记永久化线段树，因为感觉这样可能会方便一点。