A
有一家公司，现在有 \(n(n\le 5e5)\) 人来应聘，每个人有两个属性 \(a,b\)。
表示他最多可以连续工作 \(a\) 小时，表示它两次工作之间的间隔必须大于等于 \(b\) 小时。 现在要雇佣最少的人，满足能够按某种排列无限工作。
若当前雇佣了若干人，能无限工作的条件是 \(\sum a_i \ge \max(a_i+b_i)\).
那么把 \(a_i+b_i\) 排序，然后从小到大枚举，查询之前的至少要多少个人满足 \(\sum a \ge a_i+b_i\)，线段树上二分即可。
B
\(n(n\le 1e5)\) 个数构成的环，有多少种方案，把这个环分成连续的若干段，使得每一段的 \(\gcd>1\)。取模 \(1e9+7\).
把环压成序列，只要确定左边开头一部分和右边结尾的一部分组成一个段，剩下的就是链了。链的话 dp 就可以了。
我们枚举右边结尾的一段是多少，求出右边的 \(\gcd\)，令 \(a_1\) 与这个数求 \(\gcd\)。
从左边开始从左到右做 dp 即可，使用 ST 表快速查询。
然而这样是 \(n^2\) 的，但是我们发现右边 \(\gcd\) 连续段个数是 \(\log\) 级别的，所以若右边的 \(gcd\) 没变的话，直接调用之前的数组即可。
复杂度 \(O(n\log^2 n)\)，
C
一棵树，叶子节点有 \(n\) 个，非叶子有 \(n-1\) 个，每个非叶子节点都有两个儿子，两个儿子分别连的是公路和铁路。
你现在要翻新 \(n-1\) 条路，每的叶子节点有 \(a,b,c\) 三个权值，若这个节点到根有 \(x\) 条未翻新的公路，\(y\) 条未翻新的铁路，其代价是 \(a(b+x)(c+y)\).
首先有一个性质就是一条公路或铁路被翻新，那么它上面的公路或铁路都被翻新。
我们就可以预处理出 \(g[u][A][B]\) 表示 \(u\) 上方还有 \(A\) 条未翻新的公路，\(B\) 条未翻新的铁路，的代价。
然后我们可以 dp，再 wqs 二分优化一下即可。
D
数轴上有 \(n\) 个黑点，坐标为 \(a[]\)；\(n\) 个白点，坐标为 \(b[]\)
同时你有两个参数 \(la\) 和 \(lb\)，满足 \(1\le lb<la\) 。
你需要找到一个 \(1\sim n\) 的排列 \(p\)，满足对于所有 \(i\)，有 \(a[i]\le b[p[i]]\le a[i]+la\).
你需要最大化满足 \(b[p[i]]+lb\le a_i+la\) 的下标 \(i\) 的个数。数据保证存在一个合法的排列。
本来是跑费用流，实则模拟费用流。