P2423 [HEOI2012] 朋友圈
考虑 \(a \oplus b \bmod 2 = 1\) 的限制实际上转化为不同左侧点最多选择两个，因为奇偶性需要不同。
暴力枚举左侧的点集，考虑 B 侧的点，首先需要跟左侧点集任意有边，之后内部还需要是完全图。
B 侧选定点的最大团这个东西是不好做的，但是我们可以借助边的性质。
我们如果按照 B 的奇偶性来分成两类，因为 \(a \oplus b \bmod 2 = 0\)，所以集合内部点两两有边，而第二类又在两个集合中做出了连边。
不难发现如果除去团内的边，实际上这是一张二分图，我们将二分图取补图，这仍然是一张二分图。我们发现，如果在这张图上求 最大独立集，那么在原图上即为最大团。
团要求两两有边，而独立集要求两两没边，将补图还原后两两间必然有边，即为团。
- 引理：最大独立集 = $n \ - $ 最小点覆盖。
最大独立集事实上想要从全集中去掉一些点（尽量少），使得两两间没边，也就是想找最少的点破坏掉所有边（如果有边存在必然有点相连）。正好对应了最小点覆盖。
而最小点覆盖又等于最大匹配。所以我们对补图求最大匹配然后计算即可。
时间复杂度 \(O(|A|^2|B|^2)\)。
BZOJ #4664
考虑方案数从前到后并不好表示，因为如果想保证混乱度 \(\le L\)，那么需要记录前一项是什么，还需要记录选了什么，这样的话状态数也许是 \(O(2^nn)\) 的，显然无法接受。
考虑一个插块 dp，设 \(f_{i, j}\) 表示从小到大插入到第 \(i\) 个数，分成了 \(j\) 段的方案数。
转移经典，但是我们发现无法保证混乱度，考虑再设 \(f_{i, j, k}\) 表示从小到大插入到第 \(i\) 个数，分成了 \(j\) 段，总混乱度为 \(k\) 的方案数。
看起来到这就结束了，不过我们发现我们很难考虑一次插值的贡献。事实上，贡献是与邻项强相关的，然而我们的状态并没有记录邻项的值。
考虑一边插值一边计算全局的贡献。具体来说，从小到大给了我们很好的性质，考虑这样一个式子：
事实上这就是差分的前缀和。因为我们从小到大插值，那么未插的地方数字一定比当前值大，为了构造出它，我们给所有连通块的边界位置插上 \(a_i - a_{i - 1}\) 的贡献，一边插值一边算出了整体的贡献。
实现细节上，因为边界只有一边可以产生贡献所以需要再开一维表示边界。
accnoi5709 k 大值
事实上也许跟基数排序没什么关系。
考虑值域大概是 \(10^{18}\)，空间正好容得下 \(10^6\)，按照 \(10^{12}\) 确定答案在哪个块里，再按照 \(10^6\) 分块，确定在哪个 \(10^6\) 块里，下一次内部开桶即可。
ps: 事实上值域不是 \(10^{18}\)，而是稍大一些，实现上可以适当调大块长。