結果

問題 No.924 紲星
ユーザー sakikuroesakikuroe
提出日時 2024-03-05 12:24:06
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 3,040 ms / 4,000 ms
コード長 11,958 bytes
コンパイル時間 12,093 ms
コンパイル使用メモリ 401,308 KB
実行使用メモリ 226,000 KB
最終ジャッジ日時 2024-09-29 17:52:58
合計ジャッジ時間 35,711 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 4 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 5 ms
6,820 KB
testcase_06 AC 4 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2,982 ms
225,020 KB
testcase_09 AC 2,970 ms
224,916 KB
testcase_10 AC 3,040 ms
226,000 KB
testcase_11 AC 2,939 ms
225,000 KB
testcase_12 AC 2,982 ms
224,956 KB
testcase_13 AC 1,212 ms
87,868 KB
testcase_14 AC 1,088 ms
59,272 KB
testcase_15 AC 1,055 ms
71,548 KB
testcase_16 AC 878 ms
188,192 KB
testcase_17 AC 2,017 ms
94,212 KB
testcase_18 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// use proconio::{input, marker::Usize1};

/// verified by
/// - AtCoder | [AtCoder Beginner Contest 281 E - Least Elements](https://atcoder.jp/contests/abc281/tasks/abc281_e), ([submittion](https://atcoder.jp/contests/abc281/submissions/37286128))
/// - AtCoder | [Chokudai SpeedRun 001 J - 転倒数](https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j), ([submittion](https://atcoder.jp/contests/chokudai_S001/submissions/37286099))
/// - AtCoder | [AtCoder Beginner Contest 174 F - Range Set Query](https://atcoder.jp/contests/abc174/tasks/abc174_f), ([submittion](https://atcoder.jp/contests/abc174/submissions/37286021))
/// - AtCoder | [AtCoder Beginner Contest 241（Sponsored by Panasonic） D - Sequence Query](https://atcoder.jp/contests/abc241/tasks/abc241_d), ([submittion](https://atcoder.jp/contests/abc241/submissions/37308280))
/// - AtCoder | [AtCoder Beginner Contest 234 D - Prefix K-th Max](https://atcoder.jp/contests/abc234/tasks/abc234_d), ([submittion](https://atcoder.jp/contests/abc234/submissions/37313950))
/// - Library Checker | [Range Kth Smallest](https://judge.yosupo.jp/problem/range_kth_smallest), ([submittion](https://judge.yosupo.jp/submission/116350))
/// - Aizu Online Judge | [Hard Beans](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1549), ([submittion](https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7183138#1))

// ceil(log2(cardinality(X)))
// ex) when v : &[u32] -> 32,
//     when v : &[u64] -> 64
const WAVELET_MATRIX_HEIGHT: usize = 64;

#[derive(Clone)]
pub struct WaveletMatrixRow {
    accum_table: Vec<usize>,
}

impl WaveletMatrixRow {
    pub fn new(bit: Vec<usize>) -> Self {
        let mut accum_table = vec![0; bit.len() + 1];
        for i in 0..bit.len() {
            accum_table[i + 1] = accum_table[i] + bit[i];
        }
        WaveletMatrixRow { accum_table }
    }

    pub fn len(&self) -> usize {
        self.accum_table.len() - 1
    }

    pub fn access(&self, i: usize) -> usize {
        self.accum_table[i + 1] - self.accum_table[i]
    }

    pub fn rank(&self, i: usize) -> usize {
        self.accum_table[i]
    }
}

#[derive(Clone)]
pub struct WaveletMatrix {
    accum: Vec<usize>,
    bit_table: Vec<WaveletMatrixRow>,
    accum_table: Vec<WaveletMatrixRow>,
}

impl WaveletMatrix {
    pub fn new(v: &[usize]) -> Self {
        let mut v = v.to_vec();
        let mut accum = vec![0];
        for i in 0..v.len() {
            accum.push(accum[i] + v[i]);
        }
        let mut bit_table = vec![];
        let mut accum_table = vec![];
        for i in (0..WAVELET_MATRIX_HEIGHT).rev() {
            bit_table.push(WaveletMatrixRow::new(
                v.iter().map(|&x| (x >> i) & 1).collect(),
            ));
            accum_table.push(WaveletMatrixRow::new(
                v.iter()
                    .map(|&x| if (x >> i) & 1 == 0 { x } else { 0 })
                    .collect::<Vec<_>>(),
            ));

            // slow code
            // ```
            // v.sort_by_key(|&x| (x >> i) & 1);
            // ```
            v = v
                .iter()
                .filter(|&x| (x >> i) & 1 == 0)
                .chain(v.iter().filter(|&x| (x >> i) & 1 == 1))
                .cloned()
                .collect::<Vec<_>>();
        }

        WaveletMatrix {
            accum,
            bit_table,
            accum_table,
        }
    }

    /// Returns:
    ///     v[i]
    pub fn access(&self, mut i: usize) -> Option<usize> {
        if i >= self.bit_table[0].len() {
            return None;
        }

        let mut res = 0;

        for row in &self.bit_table {
            res <<= 1;
            res |= row.access(i);
            i = match row.access(i) {
                0 => i - row.rank(i),
                1 => row.len() - row.rank(row.len()) + row.rank(i),
                _ => {
                    unreachable!()
                }
            };
        }

        Some(res)
    }

    /// Returns:
    ///     v[l..r].into_iter().filter(|y| **y == x).count()
    pub fn rank(&self, mut l: usize, mut r: usize, x: usize) -> usize {
        for (i, row) in self.bit_table.iter().rev().enumerate().rev() {
            if (x >> i) & 1 == 0 {
                l = l - row.rank(l);
                r = r - row.rank(r);
            } else {
                l = row.rank(l) + (row.len() - row.rank(row.len()));
                r = row.rank(r) + (row.len() - row.rank(row.len()));
            }
        }

        r - l
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().sorted().nth(k)
    ///     }
    pub fn get_kth_smallest(&self, mut l: usize, mut r: usize, mut k: usize) -> Option<usize> {
        if l >= r || r - l <= k {
            return None;
        }

        let mut res = 0;

        for (i, row) in self.bit_table.iter().rev().enumerate().rev() {
            let j = (r - l) - (row.rank(r) - row.rank(l));
            if j > k {
                l = l - row.rank(l);
                r = r - row.rank(r);
            } else {
                l = row.rank(l) + (row.len() - row.rank(row.len()));
                r = row.rank(r) + (row.len() - row.rank(row.len()));
                res |= 1 << i;
                k -= j;
            }
        }

        Some(res)
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().sorted().rev().nth(k)
    ///     }
    pub fn get_kth_largest(&self, l: usize, r: usize, k: usize) -> Option<usize> {
        if !(r >= l + 1 + k) {
            None
        } else {
            self.get_kth_smallest(l, r, r - l - 1 - k)
        }
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().sorted().take(k).sum::<usize>()
    ///     }
    pub fn get_sum_lower_k(&self, mut l: usize, mut r: usize, mut k: usize) -> usize {
        let mut res = 0;
        let mut kth = 0;

        for (i, (row, sum)) in (self.bit_table.iter().zip(self.accum_table.iter()))
            .rev()
            .enumerate()
            .rev()
        {
            let j = (r - l) - (row.rank(r) - row.rank(l));
            if j > k {
                l = l - row.rank(l);
                r = r - row.rank(r);
            } else {
                res += sum.rank(r);
                res -= sum.rank(l);
                l = row.rank(l) + (row.len() - row.rank(row.len()));
                r = row.rank(r) + (row.len() - row.rank(row.len()));
                kth |= 1 << i;
                k -= j;
            }
        }

        res += k * kth;

        res
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().sorted().rev().take(k).sum::<usize>()
    ///     }
    pub fn get_sum_upper_k(&self, l: usize, r: usize, k: usize) -> usize {
        self.accum[r] - self.accum[l] - self.get_sum_lower_k(l, r, r - l - k)
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().filter(|x| lower <= *x && *x < upper).sum::<usize>()
    ///     }
    pub fn get_sum(&self, l: usize, r: usize, lower: usize, upper: usize) -> usize {
        self.get_sum_lower_k(l, r, self.count(l, r, 0, upper))
            - self.get_sum_lower_k(l, r, self.count(l, r, 0, lower))
    }

    /// Returns:
    ///     v[l..r].into_iter().filter(|y| **y < upper).count()
    pub fn count_lower(&self, mut l: usize, mut r: usize, upper: usize) -> usize {
        let mut res = 0;

        for (i, row) in self.bit_table.iter().rev().enumerate().rev() {
            if (upper >> i) & 1 == 0 {
                l = l - row.rank(l);
                r = r - row.rank(r);
            } else {
                res += (r - l) - (row.rank(r) - row.rank(l));
                l = row.rank(l) + (row.len() - row.rank(row.len()));
                r = row.rank(r) + (row.len() - row.rank(row.len()));
            }
        }

        res
    }

    /// Returns:
    ///     v[l..r].into_iter().filter(|y| lower <= **y && **y < upper).count()
    pub fn count(&self, l: usize, r: usize, lower: usize, upper: usize) -> usize {
        let range_freq_sub = |mut l: usize, mut r: usize, upper: usize| -> usize {
            let mut res = 0;

            for (i, row) in self.bit_table.iter().rev().enumerate().rev() {
                if (upper >> i) & 1 == 0 {
                    l = l - row.rank(l);
                    r = r - row.rank(r);
                } else {
                    res += (r - l) - (row.rank(r) - row.rank(l));
                    l = row.rank(l) + (row.len() - row.rank(row.len()));
                    r = row.rank(r) + (row.len() - row.rank(row.len()));
                }
            }

            res
        };

        range_freq_sub(l, r, upper) - range_freq_sub(l, r, lower)
    }

    /// Returns:
    ///     {
    ///         use itertools::Itertools;
    ///         v[l..r].into_iter().filter(|y| lower <= **y).sorted().nth(k)
    ///     }
    pub fn get_above_kth_smallest(
        &self,
        l: usize,
        r: usize,
        lower: usize,
        k: usize,
    ) -> Option<usize> {
        let cnt = self.count(l, r, 0, lower);
        if cnt + k >= r - l {
            None
        } else {
            Some(self.get_kth_smallest(l, r, cnt + k).unwrap())
        }
    }

    /// Returns:
    ///     v[l..r].into_iter().filter(|y| **y < upper).sorted().rev().nth(k)
    pub fn get_below_kth_largest(
        &self,
        l: usize,
        r: usize,
        upper: usize,
        k: usize,
    ) -> Option<usize> {
        let cnt = self.count(l, r, 0, upper);
        if cnt <= k {
            None
        } else {
            Some(self.get_kth_smallest(l, r, cnt - 1 - k).unwrap())
        }
    }

    /// Returns:
    ///     v[l..r].map(|y| y.abs_diff(x)).sum::<usize>()
    pub fn get_sum_abs_diff(&self, l: usize, r: usize, x: usize) -> usize {
        let c = self.count(l, r, 0, x);
        let d = self.count(l, r, x, std::usize::MAX);
        x * c - self.get_sum_lower_k(l, r, c) + self.get_sum_upper_k(l, r, d) - x * d
    }
}

fn main() {
    // input! {
    //     n: usize, q: usize,
    //     a: [isize; n],
    // }
    let n;
    let q;
    {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let mut ws = s.split_whitespace();
        n = ws.next().unwrap().parse::<usize>().unwrap();
        q = ws.next().unwrap().parse::<usize>().unwrap();
    }

    let a;
    {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let mut ws = s.split_whitespace();
        a = (0..n)
            .map(|_| ws.next().unwrap().parse::<isize>().unwrap())
            .collect::<Vec<_>>();
    }

    let wm = WaveletMatrix::new(
        &a.iter()
            .cloned()
            .map(|x| 2 * (x + 1000000000) as usize)
            .collect::<Vec<_>>(),
    );

    let mut ans = vec![];

    for _ in 0..q {
        // input! {
        //     l: Usize1, r: usize,
        // }
        let l;
        let r;
        {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut ws = s.split_whitespace();
            l = ws.next().unwrap().parse::<usize>().unwrap() - 1;
            r = ws.next().unwrap().parse::<usize>().unwrap();
        }

        if (r - l) % 2 == 1 {
            let mid = wm.get_kth_largest(l, r, (r - l) / 2).unwrap();
            ans.push(wm.get_sum_abs_diff(l, r, mid) / 2);
        } else {
            let mid0 = wm.get_kth_largest(l, r, (r - l) / 2 - 1).unwrap();
            let mid1 = wm.get_kth_largest(l, r, (r - l) / 2).unwrap();
            ans.push(wm.get_sum_abs_diff(l, r, (mid0 + mid1) / 2) / 2);
        }
    }

    println!(
        "{}",
        ans.into_iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join("\n")
    );
}
0