NOIP2020 模拟赛 B 组 Day6

非常巧妙的一场模拟赛，比较偏向于 Atcoder 的风格，考场上做出了 A 、C 两题。

排完序后一个个礼物地枚举时间复杂度是\(\Theta(nm)\)的,不能接受。但是注意到，若当前商品买得起，那么它一定能够使答案缩小至少一半。因此我们用二分法找到下一个能买得起的商品，买完再二分下一个，时间复杂度是\(\Theta(n\log^2(n))\)的。

这道题的思路，来源于想到这是一个取模运算，或者是想到若前一个不能买了后一个能买了，那么商品的价格一定会相差一定的级数，而这个级数一共的肯定不大。

假设只有一个询问，那就前缀和一下，然后一个个位置枚举看一下当前子段 1 的数量相不相等就行。

然后询问多了就彻底不会了，而且似乎询问还很难一起处理。。。这里隆重介绍一中字符串问题的大杀器：

\(\Sigma|T|<=1e6\)意味着，串长的种类数小于等于\(\sqrt n\)!因此把相同长度的串放在一起处理就可以了。

类似的题目还有这题：P3366 -- [FOI 2018 四校联训 Round 1]卷积练习题，当一个条件是某些量的值的总和小于等于一个数的时候，就意味着这些量的值只有根号种，这是一个很大力的武器。

我们先求个连通分量，在每个连通分量内，我们随便找到它的一棵生成树，显然只要确定生成树的一个结点的值，就可以通过树边确定整棵树的唯一取值方案。我们随便选一个点作为关键点求出子树的值，倘若这时与其他边存在矛盾，就可以 NIE 了。

若没有矛盾，一个点合法的条件是\(val_i \in [0,p_i]\)，这是一个一次不等式；总的来看，关键点的取值范围受到许多一次函数的约束，我们可以用简单得树形 DP 求出关键点的取值范围，若右端点小于左端点则输出无解；若有解，那么子树和的最大最小值一定只会在两个端点取得——这是一次函数嘛。

看着挺像是从斜率下手解决问题的，连数据范围都非常的 KD-tree ，然而嘛。。。我们从每个点引两条切线，若两个点的切线相交，则它们可以互相看见。对切点建立极坐标系，每个点对应一个区间，求相交的线段对数。

用线段树轻松解决——线段树需要整数域，那就把角度映射到\([0,+\infty]\)的整数域中即可。相交的线段对数——相交有两种情况，一种是部分包含，那么两个线段各有一个端点被另一个线段包含；一种是完全包含，那么一个线段有两个端点在另一个线段中。因此求出每条线段上有多少个端点，除以二就是答案。

巴特西