結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-18 23:56:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 666 ms / 2,000 ms |
コード長 | 7,129 bytes |
コンパイル時間 | 12,020 ms |
コンパイル使用メモリ | 396,824 KB |
実行使用メモリ | 53,144 KB |
最終ジャッジ日時 | 2025-07-18 23:57:08 |
合計ジャッジ時間 | 20,451 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
use proconio::{fastout, input, marker::Usize1}; use crate::fenwick_tree::FenwickTree; const MAX_NUM_DIGITS: usize = 26; #[fastout] fn main() { input! { (n, q): (usize, usize), aa: [usize; n], lr: [(Usize1, usize); q], } let fenwick_trees = (0..MAX_NUM_DIGITS) .map(|exp| FenwickTree::from(aa.iter().map(|a| a >> exp & 1).collect::<Vec<_>>())) .collect::<Vec<_>>(); let solve = |l: usize, r: usize| { (0..MAX_NUM_DIGITS) .map(|exp| { let num_ones = fenwick_trees[exp].sum(l..r); (num_ones * (r - l - num_ones)) << exp }) .sum::<usize>() }; for &(l, r) in &lr { println!("{}", solve(l, r)); } } 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) } } }