cf1608E/F
cf-round1608的E/F
G看起来好神仙，不是很想补了。
是个有一定难度的数据结构。
做这种题的时候，注意到我们只需要满足每个矩形内的所选颜色个数大于等于答案即可。
所以为了思考方便，这样我们可以主动去掉一些边界线。（其实也可以考虑如果有边界限制住恰好，这个感觉其实很生硬，就有点像凸性什么的，其实就是自己给自己加难度，所以不应该限制边界。）
上面这句话就是这道题的全部的 key point。
剩下的就是主观感受了，我们只可能有如下两种情况：
三块平行的矩形
一个半平面，剩下的另一个半平面被分成了两个1/4平面。
这样问题变得容易多了。
考虑这个大于等于答案这个条件就非常像 binary search...
所以二分答案，接下来 case 1可以3次lower_bound 非常简单的解决。
case2可以lower_bound 出来一个半平面，然后剩下的 \(O(n)\) 枚举点应不应该在半平面里。
注意颜色有序，可以旋转，综上复杂度为 \(O(36n\log n)\)
感觉好神仙。
朴素的情感，对原数列计数没有出路（因为你考虑这个对Mex记录状态的难度和对排列记录状态的难度差不多），所以直接对\(\text{Mex}_{i\leq k}\{a_i\}\)计数。
考虑当 Mex 变化时如何转移。
若 Mex 从 \(a\),变为 \(b\) ,那么对于当前这一位 \(i\)，必然有 \(a_i=a\)。（这个\(a_i\) 是原数列）。
而且 \([a+1,b-1]\) 这些数必须在前面都出现过。
这样又是一个类似可重集合计数，还是比较难，所以观察 Mex 性质，只需要管第一次出现的位置即可，又发现小于 \(a\) 的位置早就没有价值了。
所以设出状态 \(f_{i,j,k}\) 表示添到第 \(i\) 位使得 \(\text{Mex }=j\) 并且有 \(k\) 个数大于 \(j\)。（这么设 \(k\) 就相当于看有几个第一次出现）
我们现在并不关系这 \(k\) 个到底是什么，但是我们关心除了这 \(k\) 个数，都是什么/和这 \(k\) 个数中的哪一个相等。
所以 Mex 从 \(a\) 到 \(b\) 的转移 (\(a<b\)) 也非常简单： \[ f(i,a,k)\to f(i+1,b,k-(b-a-1))\times k^\underline{b-a-1} \] 含义是我们必须选出 \(b-a-1\) 个大于 \(a\) 的数让他们组成 \([a+1,b-1]\) 这些数，注意是排列（后面的下降幂）。
转移数量级是 \(O(k)\) 的，要想办法把他变成 \(O(1)\) 的。
把转移写成求和，可以发现有一维独立出来了，直接记录即可，注意一下 \(a<b\) 的限制即可，这里不是本题的重点。
剩下只需要考虑 Mex 不变的情况，这里比较simple，我们只有两种选择：
- 添一个不是第一次出现的。
- 添一个第一次出现的。
对应的转移大概就是： \[ \begin{aligned} 1. f(i,a,k)&\to f(i+1,a,k)\times(a+k)\\ 2. f(i,a,k)&\to f(i+1,a,k+1) \end{aligned} \] 注意第二个转移没有系数的原因就是我们现在并不关心这 \(k\) 个数具体是什么。
综上：总状态数 \(O(n^2k)\) ，转移量 \(O(1)\)，总复杂度 \(O(n^2k)\)