結果
問題 | No.2942 Sigma Music Game Level Problem |
ユーザー |
|
提出日時 | 2024-10-18 22:32:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 839 ms / 6,000 ms |
コード長 | 7,621 bytes |
コンパイル時間 | 14,625 ms |
コンパイル使用メモリ | 378,332 KB |
実行使用メモリ | 29,568 KB |
最終ジャッジ日時 | 2024-11-15 19:34:05 |
合計ジャッジ時間 | 26,849 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
use fenwick_tree::FenwickTree; use proconio::input; const MAX: usize = 200000; fn main() { input! { (n, q, _l0): (usize, usize, usize), aa: [usize; n], } let mut count_ft = FenwickTree::<usize>::new(MAX + 1); let mut sum_ft = FenwickTree::<usize>::new(MAX + 1); for &a in &aa { count_ft.add(a, 1); sum_ft.add(a, a); } let mut ans = vec![]; for _ in 0..q { input! { qt: usize, } match qt { 1 => { input! { l: usize, } count_ft.add(l, 1); sum_ft.add(l, l); } 2 => { input! { (l, r): (usize, usize), } let count = count_ft.sum(l..=r); let sum = sum_ft.sum(l..=r); ans.push((count, sum)); } 3 => { input! { _m: usize, } } _ => panic!(), } } if ans.is_empty() { println!("Not Found!"); } else { for &(count, sum) in &ans { println!("{} {}", count, sum); } } } 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) } } }