题解：CF2056D Unique Median

Eason_cyx · 2025-02-04 19:34:05 · 题解

妙妙题，参考了官方题解。

考虑一个子段 [l,r] 什么时候是坏的。首先必要条件显然就是 r-l+1 是偶数。那么假设 [l,r] 的中位数是 x，如果这个子段是坏的，那么一定有 \frac{r-l+1}{2} 个数 \le x，\frac{r-l+1}{2} 个数 >x，这样就满足条件了。

接下来考虑怎么计数。因为 1 \le a_i \le \color{red}\bf{10}，所以我们从这里入手。考虑枚举中位数是 x 时的答案。我们可以建立 b 数组，如果 a_i \le x，那么 b_i=-1；否则 b_i=1。那么只要有一个子段的和是 0，就说明这个子段是坏的了。那么数一下即可。时间复杂度 O(nV)，V 是值域，这里 V=10。