結果
問題 | 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>whereT: 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) -> SelfwhereT: 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)whereT: 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)whereT: 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)whereT: 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) -> TwhereT: 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) -> TwhereT: 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) -> TwhereT: Default + Clone + AddAssign<T> + Sub<T, Output = T>,{assert!(p < self.0.len());self.sum(p..=p)}}}