1777

题意： 思路： 由于需要维护极差，因此将 $ a $ 排序；由于相同的数对因子的种类和极差的贡献重复，因此将 $ a $ 去重。 设满足条件且极差最小的方案为： $ a_1 $ ， $ a_3 $ ， $ a_4 $ ， $ a_7 $ ， $ a_9 $ ，该方案等价于区间 $ [1，9] $ 。 ......

分析 看到求最大值最小，不难想到二分。 很容易想到二分最大可取边长度。 思考如何check。 首先如果存在一点 \(u\) 符合条件，那么我们很难判断那条边该翻哪条边不该翻，很难去check。 那么大胆假设对于每个点 \(u\)，每条边的方向只会确定为一个状态。 尝试证明。 假设存在边 \(a, b ......

分析 看到题面里面的子序列觉得很恶心，如果是子段感觉就会比较好做。 如果直接填上子序列中间的空隙就可能会取一些比必须要取的数更大或者更小的数，影响我们的答案。 那么就可以直接排序，使得子序列中间的空隙的数必然 \(\geq\) 左端且 \(\leq\) 右端，不会影响我们的答案（因为极差只看最大最小 ......

分析 首先计算单个排列中的逆序对数量。 我们发现这东西可以分为两类，一类是两个数在原排列和倒着的排列（这里称为“反排列”），另一类是两个数一个在原排列，一个在反排列的。 对于第一类，我们发现，原排列中的顺序对是反排列中的逆序对，所以原排列的所有数对要么在原排列中是逆序对，要么在反排列中是逆序对，所以 ......

分析 发现操作2不会改变数的奇偶性，故无视。 那么操作就是单纯删一个数。 对于一个连续出现 \(x\) 个奇偶性相同的数的序列，需要删 \(x - 1\) 个数（因为只剩下一个数就不会和相邻的数奇偶性相同了）。 觉得找序列太麻烦，观察到连续出现 \(x\) 个奇偶性相同的数的序列有 \(x - 1\ ......

problem & blog 反转的边最大权值最小，想到二分。 于是二分代价即可。 反转代价小于二分的代价的边可以反转，所以再建一条反向边即可。 在 DAG 中，存在一个点可以到达所有的点的条件是入度为 \(0\) 的点有且只有一个。 所以二分判断的时候将可以反转的边转化为无向边，然后缩点，形成 D ......

[Everybody Likes Good Arrays!](https://www.luogu.com.cn/problem/CF1777A) 简单题。 因为偶乘偶为偶，奇乘奇为奇，所以直接找有多少个奇偶性相同的块即可。 最后修改次数就是 $n-cnt$。 复杂度 $O(n)$。 ```cpp # ......