結果

問題 No.3101 Range Eratosthenes Query
ユーザー urectanc
提出日時 2025-04-11 22:17:00
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 173 ms / 3,000 ms
コード長 2,671 bytes
コンパイル時間 25,022 ms
コンパイル使用メモリ 393,868 KB
実行使用メモリ 18,240 KB
最終ジャッジ日時 2025-04-11 22:17:31
合計ジャッジ時間 18,391 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::fmt::Write;

use bit::BinaryIndexedTree;
use proconio::input;

fn main() {
    input! {
        q: usize,
        queries: [(usize, usize); q],
    }

    const M: usize = 1_000_000;

    let mut queries = queries
        .into_iter()
        .enumerate()
        .map(|(i, (l, r))| (l, r, i))
        .collect::<Vec<_>>();
    queries.sort_unstable();

    let mut n_divisors = vec![0; M + 1];
    let mut bit = BinaryIndexedTree::new(M + 1, 0);
    for i in 2..=M {
        if n_divisors[i] == 0 {
            bit.add(i, 1);
        }
        for j in (i..=M).step_by(i) {
            n_divisors[j] += 1;
        }
    }

    let mut ans = vec![!0; q];
    let mut prev_l = 2;
    for (l, r, i) in queries {
        if l == 1 {
            ans[i] = 1;
            continue;
        }

        for i in prev_l..l {
            for j in (i..=M).step_by(i) {
                n_divisors[j] -= 1;
                if n_divisors[j] == 1 {
                    bit.add(j, 1);
                }
            }
        }

        ans[i] = bit.sum(l, r + 1);
        prev_l = l;
    }

    let mut output = String::new();
    for ans in ans {
        writeln!(&mut output, "{ans}").unwrap();
    }

    println!("{}", output.trim_end());
}

#[allow(dead_code)]
mod bit {
    pub struct BinaryIndexedTree<T> {
        n: usize,
        array: Vec<T>,
        e: T,
    }

    impl<T> BinaryIndexedTree<T>
    where
        T: Clone + std::ops::AddAssign + std::ops::Sub<Output = T> + std::cmp::PartialOrd,
    {
        pub fn new(n: usize, e: T) -> Self {
            Self {
                n,
                array: vec![e.clone(); n + 1],
                e,
            }
        }

        pub fn add(&mut self, i: usize, x: T) {
            let mut i = i + 1;
            while i <= self.n {
                self.array[i] += x.clone();
                i += i & i.wrapping_neg();
            }
        }

        pub fn cum(&self, mut i: usize) -> T {
            let mut cum = self.e.clone();
            while i > 0 {
                cum += self.array[i].clone();
                i -= i & i.wrapping_neg();
            }
            cum
        }

        pub fn sum(&self, l: usize, r: usize) -> T {
            self.cum(r) - self.cum(l)
        }

        pub fn lower_bound(&self, mut x: T) -> usize {
            let mut i = 0;
            let mut k = 1 << (self.n.next_power_of_two().trailing_zeros());
            while k > 0 {
                if i + k <= self.n && self.array[i + k] < x {
                    x = x - self.array[i + k].clone();
                    i += k;
                }
                k >>= 1;
            }
            i
        }
    }
}
0