Day 2

请选择关卡：◀ Day 2 ▶
请选择难度：◀ Nightmare ▶
这就是强者的世界吗QwQ
废话不多说看题

T1 十字形

好的吧上来T1就是不会做QwQ 直觉告诉咱应该是用线段树乱搞毕竟是找“线段”的交点，包括线段覆盖平面直角坐标系上的点也和区间或多或少有些关系
结果结束了之后一起的dalao说用二分乱搞才意识到这是求最小值最大！这么明显的二分看不出来我大概废了
考场上写的暴力O(n^{2})算法挂的很惨。。手一抖把i敲成1了于是送了20pts。。
题解说数据随机可以乱搞？考虑对O(N^{2})算法进行优化。将水平和垂直的线段按照长度从大到小排序，若找到的线段长度小于目前最大的十字半径的二倍，那么这条线段及比它更小的线段必定无法对答案产生贡献，此时break即可。由于数据随机，这种算法能够直接AC。
然而并不是所有数据都这么良心==事实上，另一种做法能达到稳定O(n \log^{2} n)的做法。我们二分答案，判断能否取到即可。对于二分的每个答案r,将每条线段长度减去2*r,判断是否有交点。我们将水平的线段拆分成左端点加入与右端点删除，使用线段树维护水平线段。再枚举竖直线段逐个查询判断即可。

T2 集合

数 学 杀 我
其实考场上咱看到异或和总觉得在哪见过，后来看到题解才意识到正是不久前瞟过一眼的线性基==

经过一整个下午的没有gdb的调试后，咱终于A了P3369 普通平衡树Qw 这大概是咱写了最久的一道题了吧 从去年暑假一直到现在超过半年的调试算是有了结果。之后的任务大概就要稍微轻一点了叭 毕竟写完Splay可是咱定下的重要任务之一Qw