結果

問題 No.3197 Frequency Counter
ユーザー Moss_Local
提出日時 2025-07-11 21:46:05
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 570 ms / 2,000 ms
コード長 11,323 bytes
コンパイル時間 12,728 ms
コンパイル使用メモリ 400,068 KB
実行使用メモリ 9,996 KB
最終ジャッジ日時 2025-08-01 18:22:57
合計ジャッジ時間 20,239 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
   --> src/main.rs:112:9
    |
112 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:118:9
    |
118 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:123:9
    |
123 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:129:9
    |
129 |     let mut vec: Vec<f64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:134:9
    |
134 |     let mut vec: Vec<char> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:139:9
    |
139 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:144:9
    |
144 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:150:9
    |
150 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:156:9
    |
156 |     let mut a: Vec<u64> = read_vec();
    |         ----^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:157:9
    |
157 |     let mut wm = wavelet_matrix::WaveletMatrix::new(&a);
   

ソースコード

diff #

#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]

use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::io::BufRead;
use std::io::Read;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;

const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;

use cmp::Ordering::*;
use std::collections::*;

use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        println!("{}", $x);
    };
}

macro_rules! vp {
    ($x:expr) => {
        println!(
            "{}",
            $x.iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    };
}

macro_rules! d {
    ($x:expr) => {
        eprintln!("{:?}", $x);
    };
}
macro_rules! yn {
    ($val:expr) => {
        if $val {
            println!("Yes");
        } else {
            println!("No");
        }
    };
}

macro_rules! map{

    ($($key:expr => $val:expr),*) => {
        {
            let mut map = ::std::collections::BTreeMap::new();
            $(
                map.insert($key, $val);
            )*
            map
        }
    };
}

macro_rules! set{

    ($($key:expr),*) => {
        {
            let mut set = ::std::collections::BTreeSet::new();
            $(
                set.insert($key);
            )*
            set
        }
    };
}

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

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

#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut vec: Vec<f64> = read_vec();
    (vec[0], vec[1])
}

fn readcc() -> (char, char) {
    let mut vec: Vec<char> = read_vec();
    (vec[0], vec[1])
}

fn readuuu() -> (usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

fn main() {
    let n: usize = read();
    let mut a: Vec<u64> = read_vec();
    let mut wm = wavelet_matrix::WaveletMatrix::new(&a);
    let q: usize = read();
    for _ in 0..q {
        let (x, k): (usize, usize) = readuu();
        let x = x as u64;
        let cnt = wm.freq(0, n, x);
        // d!(cnt);
        if cnt >= k {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}
/* ========== ここからライブラリ ========== */
mod bitvec {
    /// **Succinct BitVector**
    /// - `access`, `rank1` を O(1) で提供
    pub struct BitVector {
        bits: Vec<u64>,
        prefix: Vec<usize>, // block ごとの 1 の累積
        len: usize,
    }
    impl BitVector {
        pub fn new(raw: Vec<u8>) -> Self {
            let len = raw.len();
            let blocks = (len + 63) / 64;
            let mut bits = vec![0u64; blocks];
            for (i, &b) in raw.iter().enumerate() {
                if b != 0 {
                    bits[i >> 6] |= 1 << (i & 63);
                }
            }
            // 64bit ごとの累積 1 数
            let mut prefix = Vec::with_capacity(blocks + 1);
            prefix.push(0);
            let mut sum = 0usize;
            for &blk in &bits {
                sum += blk.count_ones() as usize;
                prefix.push(sum);
            }
            Self { bits, prefix, len }
        }
        #[inline]
        pub fn access(&self, idx: usize) -> bool {
            ((self.bits[idx >> 6] >> (idx & 63)) & 1) != 0
        }
        #[inline]
        pub fn rank1(&self, idx: usize) -> usize {
            // 区間 [0, idx) に含まれる 1 の個数
            let blk = idx >> 6;
            let off = idx & 63;
            let mut cnt = self.prefix[blk];
            if off != 0 {
                cnt += (self.bits[blk] & ((1u64 << off) - 1)).count_ones() as usize;
            }
            cnt
        }
    }
}

mod wavelet_matrix {
    //! Wavelet Matrix 実装
    //!
    //! - 値域:`u64`(必要なら `u32` でも OK)
    //! - 高さ = ⌈log₂(max+1)⌉
    //! - 主要操作をすべて **O(log σ)** で提供

    use super::bitvec::BitVector;

    pub struct WaveletMatrix {
        levels: Vec<BitVector>, // MSB → LSB
        zeros: Vec<usize>,      // 各レベルで 0 側に移動した要素数
        height: usize,
        size: usize,
    }

    impl WaveletMatrix {
        /// O(N log σ) で構築
        pub fn new(arr: &[u64]) -> Self {
            let size = arr.len();
            let max = *arr.iter().max().unwrap_or(&0);
            let height = if max == 0 {
                1
            } else {
                64 - max.leading_zeros() as usize
            };

            let mut levels = Vec::with_capacity(height);
            let mut zeros = Vec::with_capacity(height);

            // 現在の並びを更新しつつ上位ビットから構築
            let mut cur: Vec<u64> = arr.to_vec();
            for bit in (0..height).rev() {
                // MSB → LSB
                let mut raw = vec![0u8; size];
                let mut zs = Vec::with_capacity(size);
                let mut os = Vec::with_capacity(size);

                for (i, &v) in cur.iter().enumerate() {
                    if (v >> bit) & 1 == 1 {
                        raw[i] = 1;
                        os.push(v);
                    } else {
                        zs.push(v);
                    }
                }
                zeros.push(zs.len());
                zs.extend_from_slice(&os);
                cur = zs;
                levels.push(BitVector::new(raw));
            }
            // levels と zeros は MSB → LSB の順序なので reverse は不要

            Self {
                levels,
                zeros,
                height,
                size,
            }
        }

        #[inline]
        fn rank1(&self, lvl: usize, idx: usize) -> usize {
            self.levels[lvl].rank1(idx)
        }

        // ----------------------------------------------------------
        // ★ クエリ実装
        // ----------------------------------------------------------

        /// access(i): 元配列 A[i] を取得
        pub fn access(&self, mut idx: usize) -> u64 {
            let mut val = 0u64;
            for lvl in 0..self.height {
                val <<= 1;
                let bit = self.levels[lvl].access(idx);
                if bit {
                    val |= 1;
                    idx = self.zeros[lvl] + self.rank1(lvl, idx);
                } else {
                    idx = idx - self.rank1(lvl, idx);
                }
            }
            val
        }

        /// freq(l, r, x): 区間 [l, r) における値 x の出現数
        pub fn freq(&self, mut l: usize, mut r: usize, x: u64) -> usize {
            if l >= r {
                return 0;
            }
            for lvl in 0..self.height {
                let bit = ((x >> (self.height - lvl - 1)) & 1) as usize;
                let rl = self.rank1(lvl, l);
                let rr = self.rank1(lvl, r);
                if bit == 0 {
                    // 0 側へ
                    l = l - rl;
                    r = r - rr;
                } else {
                    // 1 側へ
                    l = self.zeros[lvl] + rl;
                    r = self.zeros[lvl] + rr;
                }
            }
            r - l
        }

        /// kth_smallest(l, r, k): [l,r) で k 番目 (0-based) に小さい値
        pub fn kth_smallest(&self, mut l: usize, mut r: usize, mut k: usize) -> Option<u64> {
            if l >= r || k >= r - l {
                return None;
            }
            let mut val = 0u64;
            for lvl in 0..self.height {
                let zeros_l = l - self.rank1(lvl, l);
                let zeros_r = r - self.rank1(lvl, r);
                let zc = zeros_r - zeros_l; // 0 側の個数
                val <<= 1;
                if k < zc {
                    // 0 側
                    l = zeros_l;
                    r = zeros_r;
                } else {
                    // 1 側
                    val |= 1;
                    k -= zc;
                    l = self.zeros[lvl] + self.rank1(lvl, l);
                    r = self.zeros[lvl] + self.rank1(lvl, r);
                }
            }
            Some(val)
        }

        /// kth_largest(l, r, k): [l,r) で k 番目 (0-based) に大きい値
        pub fn kth_largest(&self, l: usize, r: usize, k: usize) -> Option<u64> {
            if l >= r {
                return None;
            }
            let len = r - l;
            if k >= len {
                return None;
            }
            // 大きい順 k → 小さい順 (len-k-1)
            self.kth_smallest(l, r, len - k - 1)
        }

        /// less_than(l, r, x): [l,r) で x 未満の要素数
        pub fn less_than(&self, mut l: usize, mut r: usize, x: u64) -> usize {
            let mut cnt = 0usize;
            for lvl in 0..self.height {
                let bit = ((x >> (self.height - lvl - 1)) & 1) as usize;
                let rl = self.rank1(lvl, l);
                let rr = self.rank1(lvl, r);
                let zeros_l = l - rl;
                let zeros_r = r - rr;
                if bit == 1 {
                    // 0 側はすべて x 未満
                    cnt += zeros_r - zeros_l;
                    l = self.zeros[lvl] + rl;
                    r = self.zeros[lvl] + rr;
                } else {
                    l = zeros_l;
                    r = zeros_r;
                }
            }
            cnt
        }

        /// range_freq(l, r, low, high): [l,r) において値が [low, high) に含まれる要素数
        pub fn range_freq(&self, l: usize, r: usize, low: u64, high: u64) -> usize {
            if low >= high || l >= r {
                return 0;
            }
            self.less_than(l, r, high) - self.less_than(l, r, low)
        }

        /// quantile(l, r, k): kth_smallest の別名(統計でいう分位点)
        pub fn quantile(&self, l: usize, r: usize, k: usize) -> Option<u64> {
            self.kth_smallest(l, r, k)
        }
    }
}
0