結果
問題 |
No.3075 Mex Recurrence Formula
|
ユーザー |
|
提出日時 | 2025-03-28 22:21:58 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 7,793 bytes |
コンパイル時間 | 13,314 ms |
コンパイル使用メモリ | 401,604 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2025-03-28 22:22:18 |
合計ジャッジ時間 | 16,219 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
use fenwick_tree::FenwickTree; use proconio::{input, marker::Usize1}; fn main() { input! { (n, x): (usize, Usize1), aa: [usize; n], } println!("{}", solve(&aa, x)); } fn solve(aa: &[usize], x: usize) -> usize { let n = aa.len(); if x < n { return aa[x]; } let find_mex = |ft: &FenwickTree<usize>| { let mut ok = 0_usize; let mut ng = n + 1; while ok.abs_diff(ng) > 1 { let mid = (ok + ng) / 2; if ft.sum(..mid) == mid { ok = mid; } else { ng = mid; } } ok }; let mut counts = vec![0_usize; n + 1]; let mut ft = FenwickTree::<usize>::new(n + 1); for &a in aa { if a <= n { counts[a] += 1; if counts[a] == 1 { ft.add(a, 1); } } } let mut seq = aa.to_vec(); for i in 0..n + 1 { let mex = find_mex(&ft); seq.push(mex); assert_eq!(counts[mex], 0); counts[mex] = 1; assert_eq!(ft.get(mex), 0); ft.add(mex, 1); let remove = seq[i]; if remove <= n { counts[remove] -= 1; if counts[remove] == 0 { ft.sub(remove, 1); } } } // 最初のN項を除いたN+1項は繰り返される seq[n + (x - n) % (n + 1)] } pub mod fenwick_tree { //! Processes the following query in `O(log(n))` time //! for a sequence of numbers with `n` elements: //! * Update one element //! * Calculate the sum of the elements of a range //! * Gets the elements of a number sequence. use std::ops::{AddAssign, RangeBounds, Sub, SubAssign}; /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let ft = FenwickTree::from(vec![3, -1, 4, 1, -5, 9, 2]); /// assert_eq!(ft.sum(2..), 11); /// ``` #[derive(Debug, Clone)] pub struct FenwickTree<T>(Vec<T>); impl<T> From<Vec<T>> for FenwickTree<T> where T: Default + Clone + AddAssign<T>, { /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let ft = FenwickTree::from(vec![3, -1, 4, 1, -5, 9, 2]); /// assert_eq!(ft.sum(2..6), 9); /// ``` fn from(t: Vec<T>) -> Self { let mut ft = FenwickTree::new(t.len()); for (i, x) in t.into_iter().enumerate() { ft.add(i, x); } ft } } impl<T> FenwickTree<T> { /// Constructs a `FenwickTree<T>` with `n` elements. /// /// Each element is initialized with `T::default()`. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let ft = FenwickTree::<i32>::new(5); /// assert_eq!(ft.sum(..), 0); /// ``` pub fn new(n: usize) -> Self where T: Default + Clone, { FenwickTree(vec![T::default(); n]) } /// Add `x` to the `p`-th element. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let mut ft = FenwickTree::from(vec![3, -1, 4, 1, -5, 9, 2]); /// assert_eq!(ft.sum(2..6), 9); /// /// ft.add(3, 100); /// assert_eq!(ft.sum(2..6), 109); /// ``` pub fn add(&mut self, p: usize, x: T) where T: Clone + AddAssign<T>, { let FenwickTree(data) = self; let n = data.len(); assert!(p < n); let mut p = p + 1; while p <= n { data[p - 1] += x.clone(); p += p & p.overflowing_neg().0; } } /// Subtract `x` from the `p`-th element. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let mut ft = FenwickTree::<u32>::from(vec![3, 1, 4, 1, 5, 9, 2]); /// assert_eq!(ft.sum(2..6), 19); /// /// ft.sub(3, 1); /// assert_eq!(ft.sum(2..6), 18); /// ``` pub fn sub(&mut self, p: usize, x: T) where T: Clone + SubAssign<T>, { let FenwickTree(data) = self; let n = data.len(); assert!(p < n); let mut p = p + 1; while p <= n { data[p - 1] -= x.clone(); p += p & p.overflowing_neg().0; } } /// Sets `x` to the `p`-th element. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let mut ft = FenwickTree::from(vec![3, -1, 4, 1, -5, 9, 2]); /// assert_eq!(ft.sum(2..6), 9); /// /// ft.set(3, 100); /// assert_eq!(ft.sum(2..6), 108); /// ``` pub fn set(&mut self, p: usize, x: T) where T: Default + Clone + AddAssign<T> + Sub<T, Output = T> + SubAssign<T>, { let FenwickTree(data) = self; let n = data.len(); assert!(p < n); self.sub(p, self.get(p)); self.add(p, x); } /// Compute the sum of the range [0, r). fn inner_sum(&self, r: usize) -> T where T: Default + Clone + AddAssign<T>, { let mut s = T::default(); let mut r = r; while r > 0 { s += self.0[r - 1].clone(); r -= r & r.wrapping_neg(); } s } /// Calculate the total of the range. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let ft = FenwickTree::from(vec![3, -1, 4, 1, -5, 9, 2]); /// assert_eq!(ft.sum(..), 13); /// assert_eq!(ft.sum(2..), 11); /// assert_eq!(ft.sum(..6), 11); /// assert_eq!(ft.sum(2..6), 9); /// assert_eq!(ft.sum(6..2), 0); /// ``` pub fn sum<R>(&self, rng: R) -> T where T: Default + Clone + AddAssign<T> + Sub<T, Output = T>, R: RangeBounds<usize>, { let n = self.0.len(); let l = match rng.start_bound() { std::ops::Bound::Included(&start_bound) => start_bound, std::ops::Bound::Excluded(&start_bound) => start_bound + 1, std::ops::Bound::Unbounded => 0, }; let r = match rng.end_bound() { std::ops::Bound::Included(&end_bound) => end_bound + 1, std::ops::Bound::Excluded(&end_bound) => end_bound, std::ops::Bound::Unbounded => n, }; assert!(l <= n && r <= n); if l >= r { T::default() } else { self.inner_sum(r) - self.inner_sum(l) } } /// Returns the value of an element in a sequence of numbers. /// Calculate the total of the range. /// /// # Examples /// /// ``` /// use atcoder8_library::fenwick_tree::FenwickTree; /// /// let ft = FenwickTree::from(vec![3, -1, 4, -1, 5]); /// assert_eq!(ft.get(2), 4); /// ``` pub fn get(&self, p: usize) -> T where T: Default + Clone + AddAssign<T> + Sub<T, Output = T>, { assert!(p < self.0.len()); self.sum(p..=p) } } }