結果
| 問題 |
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);
ソースコード
#![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)
}
}
}