結果

問題 No.3581 分数対称差更新区間計数取得
コンテスト
ユーザー titia
提出日時 2026-07-05 04:15:57
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 4,462 ms / 10,000 ms
コード長 1,610 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,971 ms
コンパイル使用メモリ 192,776 KB
実行使用メモリ 12,648 KB
最終ジャッジ日時 2026-07-05 04:16:49
合計ジャッジ時間 47,295 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// ChatGPTにより変換

use std::io::{self, Read};

const LEN: usize = 1 << 20;

fn update(bit: &mut Vec<i32>, mut v: usize, w: i32) {
    while v <= LEN {
        bit[v] += w;
        v += v & (!v + 1); // lowbit
    }
}

fn getvalue(bit: &Vec<i32>, mut v: usize) -> i32 {
    let mut ans = 0;
    while v != 0 {
        ans += bit[v];
        v -= v & (!v + 1); // lowbit
    }
    ans
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let q: usize = it.next().unwrap().parse().unwrap();

    let mut a = vec![0i32; LEN + 1];
    let mut bit = vec![0i32; LEN + 1];

    let mut out = String::new();

    for _ in 0..q {
        let i: usize = it.next().unwrap().parse().unwrap();
        let l: usize = it.next().unwrap().parse().unwrap();
        let r: usize = it.next().unwrap().parse().unwrap();

        let mut j = 1usize;
        while j * j <= i {
            let k = i / j;
            if a[k] == 0 {
                a[k] = 1;
                update(&mut bit, k, 1);
            } else {
                a[k] = 0;
                update(&mut bit, k, -1);
            }
            j += 1;
        }

        let lim = i / j;
        for k in 1..=lim {
            if a[k] == 0 {
                a[k] = 1;
                update(&mut bit, k, 1);
            } else {
                a[k] = 0;
                update(&mut bit, k, -1);
            }
        }

        let ans = getvalue(&bit, r) - getvalue(&bit, l - 1);
        out.push_str(&format!("{}\n", ans));
    }

    print!("{}", out);
}
0