题解：AT_abc380_g [ABC380G] Another Shuffle Window

下文下标统一从 0 开始。

每个 i 对答案造成的贡献由两部分构成：

2. 除此之外的逆序对。即，设逆序两数下标为 x,y，不同时满足 x\in [i, i+k) 和 y\in [i, i+k) 的逆序对。

定理：均匀随机地生成一个含 k 个数的排列，它的逆序对期望个数为 \frac{k(k-1)}{4}。

证明：对于 k=1，结论显然。

对于 k>1，考虑一个排列 a，将他反转后的序列 \operatorname{reverse}(a) 也是合法的排列。这两个排列正序对和逆序对恰好相反，故他们的逆序对和为 \frac{k(k-1)}{2}。

这样的排列共有 \frac{k!}{2} 组，故期望对数为 \frac{k(k-1)}{4}。

根据以上定理能够 O(1) 算出第一部分的贡献。

第二部分的贡献为 [0, n) 内的逆序对数减去 [i, i+k) 内的（原序列上的）逆序对数。使用树状数组动态维护即可。这部分的代码：

for (int i = 0; i < n; ++i) {
  int current = tr.sum(n) - tr.sum(a[i]);
  res1 += current;
  res1 %= Mod;
  if (i < k) {
    res2 += current;
    res2 %= Mod;
  }
  tr.add(a[i], 1);
}
for (int i = k; i < n; ++i) {
  tr.add(a[i], -1);
}
for (int i = k; i < n; ++i) {
  ans += ((res1 - res2) % Mod + Mod) % Mod;
  ans %= Mod;
  tr.add(a[i - k], -1);
  res2 -= tr.sum(a[i - k]);
  res2 += tr.sum(n) - tr.sum(a[i]);
  res2 %= Mod;
  tr.add(a[i], 1);
}
ans += ((res1 - res2) % Mod + Mod) % Mod;
ans %= Mod;

总时间复杂度 O(n\log n)。