A. 养花

利用根号的一些性质，可以得到很多在最坏情况下$n\sqrt n logn$的算法，

然而出题人似乎根本没有给这个算法分的意思。

正解是分块。

预处理出每个块内对于每个k的答案。

对于询问，大块直接统计，小块暴力就可以了。

设值域为s，块的大小为q，那么总共有$\frac{n}{q}$个块。

总复杂度为$O(\frac{n*s*ln(s)+n^2}{q}+m*(q+\frac{n}{q}))$。

不妨设$n=m=q$，利用均值不等式可得当$q=\sqrt{n*ln(n)}$时有最小值。

B. 折射

按$y$排序，即自动满足条件1。

设$dp(i,j)$表示最后一个的横坐标为i，倒数第二个的横坐标为j。

那么可以写出简单的dp转移，前缀和优化一下就可以$O(n^2)$。

然而会被卡空间，发现dp数组只用了一半，所以用等差数列把它拍到一维上就可以了。

正解是将点按$x$排序，

利用当前枚举点最靠右，那么一定是第一或第二个点的性质，设为向右/左拐，可以进行dp。

C. 画作

结论：存在一种最优方案，使得操作区域不断为前一次操作区域的子集，并且相邻两次涂的颜色不同。

因为看不懂证明，所以不写证明，所以复制题解的证明：

考虑归纳证明, 记 S 为当前所有操作区域的并, T 为接下来一步的操作区域, 我们有:

1. T 与 S 有交的情况一定可以转化成 T 被 S 包含的情况。

2. T 与 S 交集为空时, 可以找一个连接 S 和 T 的集合 M 并操作 S ∪T ∪ M，

并将之前的所有操作连接到更外的层以及外层的连接部分同时操作，

特殊处理最外层和第二层的情况。

3. T 被 S 包含时，T 落在某个完整区域内时等价于情况二，否则一定连接若干个同色块，

这些块可以同时处理，步数一定不会更劣。

证明了以上结论，枚举起始点不断进行bfs，复杂度可以$O(n^5)$。

将同色的联通块视作0边，异色联通块视作1边，进行双端队列bfs，可以$O(n^4)$。

更容易理解的是继承上一层的bfs状态，直接进行拓展。