q089.rs

use std::collections::BTreeMap;
use proconio::input;

const MOD: i64 = 1_000_000_007;

fn main() {
    // #1 入力
    input!{
        n: usize,
        k: usize,
        a: [usize; n],
    }
    // #2「座標圧縮」
    let mut map = BTreeMap::new();
    for &ai in &a { map.insert(ai, 0); }
    for (i, (_key, value)) in map.iter_mut().enumerate() { *value = i+1 }
    let b: Vec<_> = a.iter().map(|ai|map[ai]).collect();

    // #3 転倒数がK以下となる最大の[l, r]を求める
    // 尺取り法だと全体がO(NlogN)で求まる
    let mut ub = vec![0; n+1];
    let (mut l, mut r) = (0, 0);
    let mut bit = BITree::new(n+1);
    bit.add(b[0], 1);
    let mut inv_num = 0i64;
    loop {
        ub[l] = r;
        // eprintln!("{}", inv_num);
        if l == n-1 && r == n-1 { break; }

        if r < n-1 {
            // r += 1 してみる
            let diff = bit.sum(b[r+1]+1..);
            if inv_num + diff <= k as i64 {
                r += 1;
                inv_num += diff;
                bit.add(b[r], 1);
                continue;
            }
        }
        // r += 1 しないなら l = +1 する
        {
            let diff = bit.sum(..b[l]);
            inv_num -= diff;
            bit.add(b[l], -1);
            l += 1;
            continue;
        }
    }

    // #4 dp 前の部分列がiで終わっている場合、次の部分列は[i,i],...,[i,ub[i]]がありうるので
    // dp[i-1]をdp[i]..dp[ub[i]]に加算する。このままだと区間への加算のためO(N^2)となるので、BITを利用する
    // diff_dp[i] = dp[i] - dp[i-1]
    let mut diff_dp = BITree::new(n+2);
    // dp[0] = 1;
    diff_dp.set(0, 1); diff_dp.set(1, -1);
    for i in 0..n {
        let x = diff_dp.sum(..=i) % MOD;
        // dp[i+1]..dp[ub[i]+1]にdp[i]を足す
        diff_dp.add(i+1, x);
        diff_dp.add(ub[i]+2, -x);
    }

    let ans = diff_dp.sum(..=n) % MOD;
    println!("{}", ans);
}

/// BITree
#[derive(Debug)]
#[allow(non_snake_case)]
struct BITree<N> {
    n: usize,
    data: Vec<N>,
}
impl<N: num::Num + Copy + std::ops::AddAssign> BITree<N> {
    fn new (n: usize) -> Self {
        Self { n, data: vec![N::zero(); n+1]}
    }
    #[allow(dead_code)]
    fn add(&mut self, i: usize, x: N) {
        assert!(i < self.n);
        let mut ip1 = i + 1;
        while ip1 <= self.n {
            self.data[ip1] = self.data[ip1] + x;
            ip1 += 1 << ip1.trailing_zeros();
        }
    }
    fn sumrt(&self, range_to_inclusive_end: usize) -> N {
        let mut ip1 = range_to_inclusive_end;
        assert!(ip1 <= self.n);
        let mut res = N::zero();
        while ip1 != 0 {
            res = res + self.data[ip1];
            ip1 -= 1 << ip1.trailing_zeros();
        }
        res
    }
    fn sum(&self, range: impl std::ops::RangeBounds<usize>) -> N {
        let (l, r) = (range.start_bound(), range.end_bound());
        // assert!(l <= r && r < self.n);
        let end = match r {
            std::ops::Bound::Excluded(&end) => self.sumrt(end),
            std::ops::Bound::Included(&end) => self.sumrt(end+1),
            std::ops::Bound::Unbounded => self.sumrt(self.n),
        };
        let start = match l {
            // Excluded(&start) => self.sumrt(start-1),
            std::ops::Bound::Excluded(_) => unreachable!(),
            std::ops::Bound::Included(&start) => self.sumrt(start),
            std::ops::Bound::Unbounded => N::zero(),
        };
        end - start
    }
    #[allow(dead_code)]
    fn get(&self, i: usize) -> N {
        assert!(i < self.n);
        let res = self.sum(i..=i);
        res
    }
    #[allow(dead_code)]
    fn set(&mut self, i: usize, x: N) {
        assert!(i < self.n);
        let diff = x - self.get(i);
        self.add(i, diff);
    }
}