Interval Inversion Count の解説

典型手法として、Kと等しい個数をもとめる時に、 K以下の個数としてありえる個数からk - 1以下の個数としてあり得る個数を引くことがあります。

したがって転倒数がk以下の(l, r)の個数を求められればこの問題は解けます。

転倒数は範囲を伸ばせば伸ばすだけ増加する一方で、減少はしません。 よって、尺取法でlを固定した時の最大のrを調べていけば良いです。

ある数numを配列一番右にpushしたときに迷惑をかける = 転倒数が増加する個数はそれより左にある、num より大きい値の個数です。

また、ある数numを配列一番左からremoveした時にその数が迷惑をかけていた = 転倒数が減少する個数はそれより右にある、numより小さい値の個数です。

これが高速に求められれば良いので、seg木で上記を更新しながら計算することで答えを高速に求められます。

fn main() {
    input! {
        n: usize,
        k: usize,
        p: [Usize1; n]
    }
    let f = |k: usize| {
        let mut right = 0;
        let mut count = 0;
        let mut seg = Segtree::<M>::new(n + 10);

        let mut ans = 0;
        for left in 0..n {
            loop {
                if right == n {
                    break;
                }
                let num = p[right];
                let cc = seg.prod(num + 1..);
                if count + cc > k {
                    break;
                }
                right += 1usize;
                count += cc;
                let pre = seg.get(num);
                seg.set(num, pre + 1);
            }
            ans += right - left;

            if left == right {
                right += 1usize;
            } else {
                let cc = seg.prod(..p[left]);
                count -= cc;
                let pre = seg.get(p[left]);
                seg.set(p[left], pre - 1);
            }
        }
        ans
    };
    let ans = f(k) - if k == 0 { 0 } else { f(k - 1) };
    println!("{}", ans);
}