結果
問題 |
No.3197 Frequency Counter
|
ユーザー |
![]() |
提出日時 | 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);
ソースコード
#![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) } } }