結果

問題 No.2758 RDQ
ユーザー naut3
提出日時 2024-05-17 22:18:46
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,669 ms / 2,000 ms
コード長 3,078 bytes
コンパイル時間 19,052 ms
コンパイル使用メモリ 386,864 KB
実行使用メモリ 115,692 KB
最終ジャッジ日時 2024-12-20 15:47:11
合計ジャッジ時間 35,641 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        N: usize, Q: usize,
        A: [usize; N],
    }

    let mut bits = vec![DynamicBinaryIndexedTree::new(N); 100_010];

    for i in 0..N {
        let a = A[i];
        let divs = calc_divisors(a);

        for d in divs {
            bits[d].add(i, 1);
        }
    }

    for _ in 0..Q {
        input! {
            L: Usize1, R: Usize1, K: usize,
        }

        let ans = bits[K].sum(L..=R);
        println!("{}", ans);
    }
}

pub fn calc_divisors(n: usize) -> Vec<usize> {
    let mut ret = vec![];

    for i in 1..=n {
        if i * i > n {
            break;
        }

        if n % i != 0 {
            continue;
        }

        ret.push(i);

        if n / i != i {
            ret.push(n / i);
        }
    }

    ret.sort();
    return ret;
}

#[derive(Clone)]
pub struct DynamicBinaryIndexedTree<T> {
    size: usize,
    tree: std::collections::HashMap<usize, T>,
}

impl<
        T: Default
            + Clone
            + Copy
            + std::ops::Add<Output = T>
            + std::ops::AddAssign
            + std::ops::Sub<Output = T>,
    > DynamicBinaryIndexedTree<T>
{
    /// self = [0; size]
    pub fn new(size: usize) -> Self {
        return Self {
            size: size,
            tree: std::collections::HashMap::new(),
        };
    }

    fn _inner_add(&mut self, mut i: usize, w: T) {
        assert!(i <= self.size && i > 0);

        while i <= self.size {
            let prev = self.tree.get(&i);
            match prev {
                Some(&v) => {
                    self.tree.insert(i, v + w);
                }
                None => {
                    self.tree.insert(i, w);
                }
            }
            i += i & i.wrapping_neg();
        }
    }

    fn _inner_sum(&self, mut i: usize) -> T {
        let mut ret = T::default();
        while i > 0 {
            if let Some(&v) = self.tree.get(&i) {
                ret += v;
            }

            i -= i & i.wrapping_neg();
        }
        return ret;
    }

    /// self[i] += w
    pub fn add(&mut self, i: usize, w: T) {
        self._inner_add(i + 1, w);
    }

    /// return Σ_{j ∈ [0, i]} self[j]
    pub fn prefix_sum(&self, i: usize) -> T {
        self._inner_sum(i + 1)
    }

    /// return Σ_{j ∈ range} self[j]
    pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> T {
        let left = match range.start_bound() {
            std::ops::Bound::Included(&l) => l,
            std::ops::Bound::Excluded(&l) => l + 1,
            std::ops::Bound::Unbounded => 0,
        };

        let right = match range.end_bound() {
            std::ops::Bound::Included(&r) => r,
            std::ops::Bound::Excluded(&r) => r - 1,
            std::ops::Bound::Unbounded => self.tree.len() - 1,
        };

        if left == 0 {
            return self.prefix_sum(right);
        } else {
            return self.prefix_sum(right) - self.prefix_sum(left - 1);
        }
    }
}
0