0228测试
0228测试
T1
毒瘤计算几何。
考虑一步的过程，是从一个点的一个方向开始旋转，于是对所有目标点极角排序，极角相同的长度较长的放前面，查询就是要找到接下来的第一个长度小于当前长度的。
一个很暴力的想法是直接开始跳，如果遇到了相同的点说明有环，然后模环长再跳，这样每个点期望经过 \(O(\log)\) 次，总共要处理 \(O(nm\log n)\) 次，感觉很可做。
接下来的问题变成了如何快速查询。考场上觉得排序后确实是查第一个比它大的，但是要带上删除，于是考虑长度倒序做。然后想 set 暴力操作肯定要超时，然后考虑用并查集做删除操作，用优先队列维护长度的处理顺序。
很麻烦，写不出来。
实际上可以不带删，考虑找到第一个极角超过查询极角的位置，在上面二分第一个长度满足限制的，用 ST 表做长度查询，复杂度 \(O(\log n)\)。
找环的时候需要注意不是点重复而是边重复才出现环，判断需要再检查一下来向，需要记录当前点上一次访问时有几个点，走了多远，从哪个来的。
总复杂度 \(O(Tnm\log^2n)\)。因为卡不满所以能过。
带删的查询问题都很麻烦，考察之前先想想能不能不删。
T2
首先考察 \(1\) 是不是重心，如果 \(1\) 不是重心那么一定会向重心移动？不对，可以先往重心走一步，让重心的点相互消耗，然后往回去。
考虑目标点和 \(1\) 之间的毛毛虫。毛毛虫任意两个端点都是可以相互抵消大小的。因此如果毛毛虫所有端点大小和为偶数且没有任何一个端点大小超过 \(\frac{totalsize}{2}\)，那么一定可以移动到目标点。
如果有一个大小超了，考虑能不能在它的内部抵消，是可以的，考虑计算一下某棵子树最少要将中心往自己的方向拉几步，同时也不难证明最少步数到 \(sz\) 之间每一个奇偶性相同的步数都能取到。
最小步数是可以动态规划的，转移看是否有一个儿子的 DP 值超过其它儿子的大小总和，还要看当前子树大小奇偶性。可以拿个类记录一下 DP 值最大的儿子和对应的子树大小以及总的子树大小。因为如果有儿子 DP 值超过其它儿子总大小，那么这个儿子的 DP 值一定是最大的，所以这样没问题。
然后考虑计算答案，直接再 DFS 一遍，判断合法性的信息就是转移的那个信息，很容易合并的，额外算一个后缀和就行。
T3
最开始想能不能把限制弄成不包含或者不交，然后发现不行，由于 \(x_i\) 可能相等，所以不交也是不现实的。然后想能不能从位置入手做，比如区间 DP 或者扫描 DP，还是不好处理。
就算是容斥，同样不好考虑位置。
考虑从值本身入手做，每段位置有一个限制，然后考虑一个限制，可能让它满足条件的段是一段区间，而且使值不同的限制满足的位置集合不交。说人话就是不同值的限制独立，一段上界相同的位置只会满足值是其上界的限制。因此可以上界不同的段分开做然后乘起来。
将区间弄成左闭右开方便处理，然后离散化暴力算每一段的上界，上界记在左端点。枚举每个值，暴力将每一段放进去，然后将对应的限制挂在新标号的位置上去。
然后设 \(dp[i][j]\) 表示考虑到前 \(i\) 个，上一个抵到上界的位置是 \(j\) 的方案数，在右端点还需要将不满足挂上的限制的状态清掉。
复杂度 \(O(q^2T)\)。
其实有 \(O(Tq\log q)\)
的做法，暴力算上界可以用单点改后缀查的树状数组优化，暴力放段的过程可以用
vector 记一下每一个值具体有哪些段和哪些限制。
动态规划中，先对限制的左端点取前缀 \(\max\)，然后可以考虑枚举最后一个 \(1\) 的位置转移，然后转移可以双指针加标记搞定。