AtCoder Beginner Contest 453 E

https://atcoder.jp/contests/abc453/tasks/abc453_e

入力例1だと選手1は単独でチーム、選手2は2人のチームだから、と考えたくなりますが、これだとうまくいきそうにありません。
見る角度を変えて、チームAの人数を決めればよいです。それをAとすると、Aが範囲に入る人数とBが範囲に入る人数とどちらにも入る人数を数えれば、組合せで直ちに求められます。
Aが範囲に入る人数を求めるにはBinary Indexed Treeに全ての範囲を加えればよいです。そして、両方に入るには、AとBを足せば常にNなので、真ん中で折り返して重なる部分を範囲にしてBITに加えればよいです。すなわち、入力例2だと3が真ん中だから、それぞれ、1 3、1 3、2 3、3 3、3 3、2 3となります。

// Team Division
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


//////////////////// Binary Indexed Tree ////////////////////

struct BIT {
    n: usize,
    data: Vec<i64>,
}

impl BIT {
    fn new(n: usize) -> Self {
        BIT { n, data: vec![0; n + 1] }
    }
    
    // i に x を足す（0-indexedで受け取る）
    fn add(&mut self, mut i: usize, x: i64) {
        i += 1;
        while i <= self.n {
            self.data[i] += x;
            i += i & (!i + 1)
        }
    }
    
    // [0, i] の和（0-indexed）
    fn sum(&self, mut i: usize) -> i64 {
        i += 1;
        let mut s = 0;
        while i > 0 {
            s += self.data[i];
            i -= i & (!i + 1);
        }
        s
    }
}


//////////////////// process ////////////////////

const D: i64 = 998244353;

type Range = (usize, usize);

fn read_range() -> Range {
    let v: Vec<usize> = read_vec();
    (v[0], v[1] + 1)
}

fn read_input() -> Vec<Range> {
    let N: usize = read();
    let ranges: Vec<Range> = (0..N).map(|_| read_range()).collect();
    ranges
}

fn factorials(N: usize) -> Vec<i64> {
    let mut facs: Vec<i64> = vec![1; N+1];
    for i in 1..N+1 {
        facs[i] = facs[i-1] * (i as i64) % D
    }
    facs
}

fn C(n: i64, m: i64, f: &Vec<i64>) -> i64 {
    if n < m || m < 0 {
        0
    }
    else {
        f[n as usize] * inverse(f[m as usize], D) % D
                        * inverse(f[(n-m) as usize], D) % D
    }
}

fn convert(rngs: &Vec<Range>) -> Vec<Range> {
    let N = rngs.len();
    let mut rngs2: Vec<Range> = vec![];
    for &(L, R) in rngs.iter() {
        if L * 2 > N || (R - 1) * 2 < N {
            rngs2.push((L, L))
        }
        else {
            rngs2.push((L.max(N-R+1), N / 2 + 1))
        }
    }
    rngs2
}

fn create_tree(rngs: Vec<Range>) -> BIT {
    let N = rngs.len();
    let mut bit = BIT::new(N.next_power_of_two());
    for (l, r) in rngs {
        bit.add(l, 1);
        if r < bit.n {
            bit.add(r, -1)
        }
    }
    bit
}

fn F(rngs: Vec<Range>) -> i64 {
    let N = rngs.len();
    let rngs2 = convert(&rngs);
    let facs = factorials(N);
    let bit = create_tree(rngs);
    let bit2 = create_tree(rngs2);
    let mut counter: i64 = 0;
    for A in 1..N/2+1 {
        let NA = bit.sum(A);
        let NB = bit.sum(N-A);
        let NAB = bit2.sum(A);  // AにもBにもなり得る人数
        // AにもBにもならない選手がいる
        if NA + NB - NAB < (N as i64) {
            continue
        }
        
        // NA - NABは固定
        // NB - NABも固定
        // NABが動く
        // A-(NA-NAB)はNABの中でA側
        let c = C(NAB, NA-(A as i64), &facs);
        if A * 2 == N {
            counter += c
        }
        else {
            counter += c * 2
        }
    }
    counter % D
}

fn main() {
    let rngs = read_input();
    println!("{}", F(rngs))
}