训练记录
9 月没做题。
不能摆了，再摆就完蛋了。
CF1784F Minimums or Medians
很厉害的题。
我们考虑找充要条件：
-
注意到所有被删除的连续段长度都是偶数。并且不同的连续段之间，都是被分开删除的。
注意到只有从 \(1\) 开始的连续段才可能用操作 1 删除，于是其它被删的数都是通过操作 2 删除的。
-
注意到第 \(i\) 次若为操作 2，则删除的较大数为 \(i+n\)，所以，被删除的数都必须 \(\le n+k\)。
-
注意到若删除了数 \(t\le n\) 不在第一段，则 \([t,2n-t+1]\) 的数都必须被删除。
上述 3 个必要条件是充分的，因为考虑我可以通过构造，每次能用操作 2 就用操作 2，否则就用操作 1，不难发现一定是合法的。
设函数 \(f(n, m)\) 表示长度为 \(n\) 的段中，选出 \(2m\) 个数，并要求选出的数形成长度为偶数的连续段。考虑捆绑法，我们没选出一个数就要求必须选它后面的那个数，于是这样就只有 \(n-m\) 个物品，从中选出 \(m\) 个，所以是 \(\binom{n-m}{m}\)。
考虑如何计数。首先，我们枚举从 1 开始的连续段需要操作的次数 \(t\)，因为涉及到条件 3，所以我们需要根据是否覆盖超过一半来分类讨论：
- \(2t < n\)，于是再枚举在 \(n\) 之前被删掉的连续段长度 \(c\)，于是得到：
\[\sum_{t=1}^{\min\{k, \lfloor \frac{n-1}{2} \rfloor\}} \sum_{c=0}^{\min\{k - len, n - 2k - 1\}}f(k-c,k-t-c)
\]
注意到 \(len\) 增加时，组合数的变化可以 \(O(1)\) 维护，类似莫队移动指针，加入或删除组合数。
- \(2t \ge n\)，那么剩下的就可以随便操作，于是对答案的贡献为：
\[\sum_{len = \lceil\frac{n}{2}\rceil}^{k} f(n + k-2t-1, k - t)
\]
记录。