分析

此题最重要的性质是在于 $k$ 的范围：保证是奇数。$k$ 是奇数，那么所有长度为 $k$ 的区间当中的所 有元素，轴对称的位置与其本身的位置 奇偶性保持一致。因为假设对称轴坐标是整数 $m$，那么对称轴左侧位置为 $m-i$ 的元素，对称之后就到了 $m+i$ 的位置，而 $(m+i) - (m-i) = 2i$ 是偶数。

对于此类计数问题，可以从左到右，依次扫描每个元素，计算有多少元素可以与之配对。为了避免重复，对于第 $p$ 个元素，我们只从 $[1, p-1]$ 范围内（即 它的左侧）进行计数。

长度为 $n$ 的序列最多有 $n-k+1$ 个长度为 $k$ 的子区间，每个子区间最多贡献 $\frac{k+1}{2}$ 的答案（要记得 $k$ 是奇数），因此答案的最大值是 $(n-k+1) \times \frac{k+1}{2}$。

假设对于第 $p$ 个元素，它左侧可能存在与之配对（对称并相等）的元素的范围是 $[l, r]$，那么只要提前分奇偶把所有数字出现的位置存下来，使用 std::upper_bound 和 std::lower_bound 就可以快速计算出这个范围内有多少个。答案的最大值减去所有的配对个数，就是最终答案。

那么接下来的主要问题，就是计算 $[l, r]$。

对于 $l$

• 首先要保证 $l$ 到 $p$ 的距离在 $k$ 以内，即 $p-l+1 \leq k$，化简得到 $l \geq p-k+1$。
• $l$ 与 $p$ 之间对称轴的位置是 $m=\frac{l+p}{2}$，要保证对称轴左边还有足够的位置来容纳这个长度为 $k$ 的区间，得到 $\frac{l+p}{2} - \frac{k+1}{2} \geq 1$，化简得到 $l \geq k+2-p-1$。

对于 $r$

• 为了避免重复计算，我们只考虑在 $p$ 左边的可能的位置。$r$ 的最大值在对称轴位于 $m=p-1$ 的时候取到，此时 $r=p-2$。因此：$r \leq p - 2$。
• $r$ 与 $p$ 之间对称轴的位置是 $m = \frac{r+p}{2}$，与刚才类似，现在要保证对称轴右边（到数组尽头）还有足够的位置来容纳这个长度为 $k$ 的区间，即 $\frac{r+p}{2} + \frac{k+1}{2} <= n$，化简得到 $r \leq 2n - p - k + 1$。

整理式子

根据上述计算，有 $$\begin{aligned} l &= \max(p-k+1, k-p+1) \\ r &= \min(p-2, 2n-p-k+1) \end{aligned}$$ 要注意有可能计算得到 $l > r$，这种情况应当予以忽略。

代码

void solution() {
  int n, k;
  std::cin >> n >> k;
  assert(k & 1);
  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::vector<std::vector<int>> odd(200001), even(200001);
  for (int i = 1; i <= n; ++i)
    i & 1 ? odd[a[i]].push_back(i) : even[a[i]].push_back(i);
  ll ans = 1ll * (k / 2) * (n - k + 1);
  auto solve = [&](auto& pos) {
    for (int x = 1; x <= 200000; ++x) {
      for (auto p : pos[x]) {
        int l = std::max(p - k + 1, k - p + 1);
        int r = std::min(p - 2, 2 * n - p - k + 1);
        auto it1 = std::lower_bound(pos[x].begin(), pos[x].end(), l);
        auto it2 = std::upper_bound(pos[x].begin(), pos[x].end(), r);
        auto sub = std::distance(it1, it2);
        ans -= sub <= 0 ? 0 : sub;
      }
    }
  };
  solve(odd);
  solve(even);
  std::cout << ans << "\n";
}