Codeforces Round #502
C. The Phone Number
题目描述：求一个\(n\)排列，满足\(LIS+LDS\)最小
solution
枚举\(LIS\)，可证明\(LDS\)的最小值为\(\left \lceil \frac{n}{LIS} \right \rceil\)。
证明：
假设\(LDS<\left \lceil \frac{n}{LIS} \right \rceil\)，令\((a_i, b_i)\)为\(i\)为结尾的\(LIS\)和\(LDS\)，可知\((a_i, b_i)\)二元组两两不同（假设\(a_i=a_j, b_i=b_j, i<j, \because a_i=a_j，\therefore p_i>p_j\), 则\(b_j=b_i+1\)矛盾）
则有\(1\leq a_i \leq LIS\),
\(1\leq b_i \leq LDS \leq \left \lceil \frac{n}{LIS} \right \rceil -1 < \frac{n}{LIS}+1-1=\frac{n}{LIS}\)
所以二元组的个数小于\(LIS \cdot \frac{n}{LIS}=n\)，根据鸽巢原理，必定有两个二元组相同，矛盾。
因此\(LDS\)的最小值为\(\left \lceil \frac{n}{LIS} \right \rceil\)。
根据这个可构造答案，从大到小排，然后每\(LIS\)个一组，剩余的一组，然后每组从小到大排。
时间复杂度：\(O(n)\)
E. The Supersonic Rocket
题目描述：题目看得很过瘾，竟然可以把判断两个凸包是否相同描述得如此得复杂。。。
solution
以边长和角度（可以用相邻边的点乘代替）的顺序作为凸包的特征值，把第一个凸包的特征值看成一个字符串，第二个凸包的特征值复制两遍，跑一次\(KMP\)即可。
时间复杂度：\(O(nlogn)\)
F. The Neutral Zone
题目描述：定义\(exlog_f(p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k})=a_1f(p_1)+a_2f(p_2)+\cdots+a_kf(p_k), p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}\)是一个数的质因数分解，\(f(x)=Ax^3+Bx^2+Cx+D\), 求\(\sum_{i=1}^{n} exlog_f(i)\)
solution
其实就是求
\[\sum_{i=1}^{n \text{以内质数个数}} f(p_i)\sum_{j=1}^{\infty} \left \lfloor \frac{n}{p_i} \right \rfloor\]
但是空间只有\(16M\)
方法一：
质数中除了\(2, 3\)其它质数模\(6\)为\(\pm 1\)，以此可以将线性筛的数组控制在十几\(M\)。
方法二：
将\(\sqrt{n}\)的质数求出来，然后将\(n\)分块，每一块分\(3\times 10^6\)，然后每一块用\(\sqrt{n}\)的质数筛，筛剩的就是质数。
时间复杂度：\(O(nln\sqrt{n})\)
G. The Tree
题目描述：有一棵以\(1\)为根的树，一开始所有点都是白色，现要支持三种操作：
- 选择一个节点，如果这个节点是白色，则将它变成黑色，否则对它的所有儿子进行同样操作。
- 选择一个节点，将这个节点的子树全部变成白色。
- 询问一个节点的颜色。
solution
题解给的方法是对操作分块\((\sqrt{n})\)，然后每一块的操作只涉及\(\sqrt{n}\)个点，然后不知道怎么搞。。。
下面一个小哥给了一个树剖的做法，感觉好理解一些。
首先将所有点标记为\(-1\)，
对于操作\(1\)，将那个点\(+1\)，
对于操作\(3\)，就是询问该点到根的后缀和最大值是否非负，如果非负，则这个点为白色，否则就是黑色。
对于操作\(2\)，先询问父亲到根的最大后缀和\((x)\)，然后将子树全部变成\(-1\)，最后如果\(x>0\), 则询问的那个点要加上\(-x\)，以消除前面操作对该子树的影响。
时间复杂度：\(O(nlogn)\)