ABC380 G 题解

纪念一个因打游戏而错过的水题。

题意 ABC380G

给定长为 N 的排列 P 和常数 K，等概率选取一个长为 K 的区间随机打乱，求最终序列逆序对数的期望。

思路

回忆使用 \mathtt{BIT} 求逆序对的过程，他的主要思想是对每个元素算贡献，也就是对于每个 P_i，求满足 j<i 且 P_j>P_i 的个数，加和就得到逆序对数。

题目中只选取了一个长度为 K 的区间随机打乱，容易发现除了区间内的元素，其他元素对逆序对的贡献均不会发生变化。于是我们就把问题划分成了两个子问题：

1. 求原序列的逆序对数，记为 x。

2. 求某个长为 K 的区间随机打乱后逆序对数变化 \Delta x。

两个子问题的解决方案如下：

1. 归并排序或 \mathtt{BIT}。

2. 已知原序列是一个排列，因此不需要担心元素相等的情况，于是这个区间的元素可以等价为一个排列。你可以通过如下方式得知长为 K 的随机排列逆序对数的期望值为 \dfrac{K(K-1)}{4}：

   • OEIS，打表找规律。

   • 直接推，每一个数对 (a,b)（1\le a < b \le K）可以对期望产生 \dfrac{1}{2} 的贡献。

   变化量 \Delta x 就直接是这个期望值减去原逆序对数。

solution

• 使用任意方式求出排列的逆序对数，加入答案。

• 使用 \mathtt{BIT} 或线段树等支持单修区查的数据结构动态维护每个长为 K 的区间的逆序对数 x；这一步先去掉超出区间的元素贡献，再加上新加入元素的贡献，类似于滑动窗口。

  答案加上 \left(\dfrac{K(K-1)}{4}-x\right)\times \dfrac{1}{N-K+1}，也就是期望变化量。求有理数取模的过程一般使用快速幂，详见乘法逆元。

• 输出答案。时间复杂度 \mathcal O(N \log N)，空间复杂度 \mathcal O(N)。

code

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define cnt1(x) __builtin_popcount(x)
#define int long long
using namespace std;
const int N = 2e5+5, M = 2e6+5, mod = 998244353;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int n, K, a[N], ans, now, c[N];
// now 表示滑动到某个区间的逆序对数
inline void add(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
}
inline int ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}
inline int qpow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = a * res % mod;
        a = a * a % mod;
    }
    return res;
}
signed main() {
    FASTIO;
    cin >> n >> K;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) {
        ans += i-1-ask(a[i]);
        add(a[i], 1);
    }// 求最初逆序对，使用的是 BIT
    memset(c, 0, sizeof c);
    int inv = qpow(4, mod-2), inv2 = qpow(n-K+1, mod-2);
    rep(i, 1, n) {
        if (i > K) now -= ask(a[i-K]-1), add(a[i-K],-1);// 删去超出区间的元素及其贡献
        now += ask(n)-ask(a[i]);// 加入新元素的贡献
        if (i >= K) ans = (ans+(K*(K-1)%mod*inv%mod-now%mod+mod)%mod*inv2)%mod;
        add(a[i], 1);// 加入新元素
    }
    cout << ans;
    return 0;
}