結果

問題 No.924 紲星
ユーザー sakikuroesakikuroe
提出日時 2024-03-05 12:41:08
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 3,132 ms / 4,000 ms
コード長 14,086 bytes
コンパイル時間 11,696 ms
コンパイル使用メモリ 391,452 KB
実行使用メモリ 132,344 KB
最終ジャッジ日時 2024-09-29 17:54:18
合計ジャッジ時間 37,585 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
10,368 KB
testcase_01 AC 10 ms
10,368 KB
testcase_02 AC 10 ms
10,496 KB
testcase_03 AC 16 ms
10,752 KB
testcase_04 AC 11 ms
10,496 KB
testcase_05 AC 16 ms
10,752 KB
testcase_06 AC 17 ms
10,624 KB
testcase_07 AC 12 ms
10,624 KB
testcase_08 AC 3,114 ms
132,344 KB
testcase_09 AC 3,132 ms
132,260 KB
testcase_10 AC 3,058 ms
132,168 KB
testcase_11 AC 3,119 ms
132,200 KB
testcase_12 AC 3,118 ms
132,272 KB
testcase_13 AC 1,597 ms
58,064 KB
testcase_14 AC 1,659 ms
43,880 KB
testcase_15 AC 1,489 ms
49,988 KB
testcase_16 AC 926 ms
108,736 KB
testcase_17 AC 2,510 ms
62,788 KB
testcase_18 AC 11 ms
10,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#[derive(Clone)]
pub struct SuccinctBitVector {
    len: usize,
    bit: Vec<u16>,
    chunk: Vec<u32>,
    block: Vec<Vec<u16>>,
    table: Vec<u16>,
}

impl SuccinctBitVector {
    const LOG_LEN: usize = 32;
    const CW: usize = SuccinctBitVector::LOG_LEN * SuccinctBitVector::LOG_LEN;
    const BW: usize = SuccinctBitVector::LOG_LEN / 2;
    pub fn new(v: Vec<usize>) -> Self {
        let len = v.len();
        let table = (0_usize..1 << (SuccinctBitVector::LOG_LEN / 2))
            .map(|x| x.count_ones() as u16)
            .collect::<Vec<_>>();

        let cnum = (len + SuccinctBitVector::CW - 1) / SuccinctBitVector::CW;
        let bnum = SuccinctBitVector::CW / SuccinctBitVector::BW;

        let mut bit = vec![0; cnum * bnum];

        let set = |bit: &mut Vec<u16>, i: usize, b: u8| {
            assert!(b <= 1);
            let bpos = i / SuccinctBitVector::BW;
            let offset = i % SuccinctBitVector::BW;

            if b == 0 {
                bit[bpos] &= !(1 << offset);
            } else {
                bit[bpos] |= 1 << offset;
            }
        };

        for i in 0..v.len() {
            set(&mut bit, i, v[i] as u8);
        }

        let mut chunk = vec![0_u32; cnum + 1];
        let mut block = vec![vec![0_u16; bnum]; cnum];

        for i in 0..cnum {
            block[i][0] = 0;
            for j in 0..bnum - 1 {
                block[i][j + 1] = block[i][j] + table[bit[i * bnum + j] as usize];
            }
            chunk[i + 1] = chunk[i]
                + block[i][bnum - 1] as u32
                + table[bit[(i + 1) * bnum - 1] as usize] as u32;
        }

        SuccinctBitVector {
            len,
            bit,
            chunk,
            block,
            table,
        }
    }

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

    pub fn access(&self, i: usize) -> usize {
        let bw = SuccinctBitVector::LOG_LEN / 2;
        let bpos = i / bw;
        let offset = i % bw;
        (self.bit[bpos] >> offset & 1) as usize
    }

    pub fn rank(&self, i: usize) -> usize {
        let bnum = SuccinctBitVector::CW / SuccinctBitVector::BW;

        let cpos = i / SuccinctBitVector::CW;
        let bpos = i % SuccinctBitVector::CW / SuccinctBitVector::BW;
        let offset = i % SuccinctBitVector::BW;

        let masked = (self.bit[cpos * bnum + bpos]) & ((1 << offset) - 1);
        (self.chunk[cpos] + self.block[cpos][bpos] as u32 + self.table[masked as usize] as u32)
            as usize
    }
}

/// 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<SuccinctBitVector>,
    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(SuccinctBitVector::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_less_than(&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).count()
    pub fn count_more_than(&self, l: usize, r: usize, lower: usize) -> usize {
        r - l - self.count_less_than(l, r, lower)
    }

    /// 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 {
        self.count_less_than(l, r, upper) - self.count_less_than(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_less_than(l, r, x);
        let d = self.count_more_than(l, r, x);
        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