#752163 (Rust) No.1891 Static Xor Range Composite Query

• 問題: No.1891 Static Xor Range Composite Query
• ユーザー: akakimidori
• 提出日時: 2022-04-07 12:00:31
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 2,315 ms / 5,000 ms
• コード長: 6,541 bytes
• コンパイル時間: 13,824 ms
• コンパイル使用メモリ: 395,216 KB
• 実行使用メモリ: 26,624 KB
• 最終ジャッジ日時: 2024-11-27 23:37:19
• 合計ジャッジ時間: 39,553 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,820 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	1 ms; 6,816 KB
testcase_03	AC	1 ms; 6,816 KB
testcase_04	AC	1 ms; 6,816 KB
testcase_05	AC	1 ms; 6,816 KB
testcase_06	AC	1 ms; 6,816 KB
testcase_07	AC	1 ms; 6,820 KB
testcase_08	AC	2 ms; 6,820 KB
testcase_09	AC	1 ms; 6,816 KB
testcase_10	AC	1 ms; 6,820 KB
testcase_11	AC	3 ms; 6,816 KB
testcase_12	AC	3 ms; 6,816 KB
testcase_13	AC	2 ms; 6,816 KB
testcase_14	AC	3 ms; 6,816 KB
testcase_15	AC	2 ms; 6,816 KB
testcase_16	AC	3 ms; 6,816 KB
testcase_17	AC	3 ms; 6,820 KB
testcase_18	AC	3 ms; 6,816 KB
testcase_19	AC	3 ms; 6,816 KB
testcase_20	AC	2 ms; 6,820 KB
testcase_21	AC	2,123 ms; 26,624 KB
testcase_22	AC	2,271 ms; 26,624 KB
testcase_23	AC	2,315 ms; 26,624 KB
testcase_24	AC	2,242 ms; 26,624 KB
testcase_25	AC	2,165 ms; 26,624 KB
testcase_26	AC	2,261 ms; 26,496 KB
testcase_27	AC	2,262 ms; 26,624 KB
testcase_28	AC	2,267 ms; 26,496 KB
testcase_29	AC	2,217 ms; 26,496 KB
testcase_30	AC	2,251 ms; 26,496 KB

ソースコード

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let n: usize = sc.next(b' ');
    let q: usize = sc.next(b'\n');
    let a = (0..n)
        .map(|_| {
            let a: u32 = sc.next(b' ');
            let b: u32 = sc.next(b'\n');
            Affine::new(a, b)
        })
        .collect::<Vec<_>>();
    let mut seg = XorSegmentTree::new(&vec![Affine::e(); n]);
    for (i, a) in a.iter().enumerate() {
        seg.update(i, a.clone());
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for _ in 0..q {
        let l: usize = sc.next(b' ');
        let r: usize = sc.next(b' ');
        let p: usize = sc.next(b' ');
        let x: u32 = sc.next(b'\n');
        let ans = seg.find(l, r, p).eval(x);
        writeln!(out, "{}", ans).ok();
    }
}

const MOD: u32 = 998_244_353;

#[derive(Clone)]
struct Affine(u32, u32);

impl Affine {
    fn new(a: u32, b: u32) -> Self {
        Affine(a, b)
    }
    fn eval(&self, x: u32) -> u32 {
        ((self.0 as u64 * x as u64 + self.1 as u64) % MOD as u64) as u32
    }
}

impl Monoid for Affine {
    fn merge(&self, rhs: &Self) -> Self {
        let a = self.0 as u64 * rhs.0 as u64 % MOD as u64;
        let b = (self.1 as u64 * rhs.0 as u64 + rhs.1 as u64) % MOD as u64;
        Affine::new(a as u32, b as u32)
    }
    fn e() -> Self {
        Affine::new(1, 0)
    }
}

pub trait Monoid: Clone {
    fn merge(&self, rhs: &Self) -> Self;
    fn e() -> Self;
}

pub struct StaticXorSegmentTree<T> {
    data: Vec<Vec<T>>,
    size: usize,
}

impl<T> StaticXorSegmentTree<T>
where
    T: Monoid,
{
    pub fn new(a: &[T]) -> Self {
        let size = a.len();
        assert!(size.next_power_of_two() == size);
        let k = size.trailing_zeros() as usize;
        let mut data = Vec::with_capacity(k + 1);
        data.push(Vec::from(a));
        for i in 1..=k {
            let mut a = Vec::with_capacity(size);
            for data in data.last().unwrap().chunks(1 << i) {
                let (l, r) = data.split_at(1 << (i - 1));
                a.extend(l.iter().zip(r.iter()).map(|(l, r)| l.merge(r)));
                a.extend(l.iter().zip(r.iter()).map(|(l, r)| r.merge(l)));
            }
            data.push(a);
        }
        Self { data, size }
    }
    pub fn find(&self, mut l: usize, mut r: usize, xor: usize) -> T {
        assert!(l <= r && r <= self.size && xor < self.size);
        if l == r {
            return T::e();
        }
        let mut x = T::e();
        let mut y = T::e();
        for (shift, data) in self.data.iter().enumerate() {
            if l >> shift & 1 == 1 {
                x = x.merge(&data[l ^ xor]);
                l += 1 << shift;
            }
            if r >> shift & 1 == 1 {
                r -= 1 << shift;
                y = data[r ^ xor].merge(&y);
            }
            if l == r {
                break;
            }
        }
        x.merge(&y)
    }
    pub fn find_all(&self, xor: usize) -> T {
        assert!(xor < self.size);
        self.data.last().unwrap()[xor].clone()
    }
    fn update(&mut self, pos: usize, v: T) {
        assert!(pos < self.size);
        self.data[0][pos] = v;
        for shift in 1..self.data.len() {
            let s = (pos >> shift) << shift;
            let mut p = std::mem::take(&mut self.data[shift]);
            let c = &self.data[shift - 1][s..(s + (1 << shift))];
            let (l, r) = c.split_at(1 << (shift - 1));
            let ab = l.iter().zip(r.iter()).chain(r.iter().zip(l.iter()));
            for (p, (a, b)) in p[s..].iter_mut().zip(ab) {
                *p = a.merge(b);
            }
            self.data[shift] = p;
        }
    }
}

pub struct XorSegmentTree<T> {
    data: Vec<StaticXorSegmentTree<T>>,
    size: usize,
    batch: usize,
}

impl<T> XorSegmentTree<T>
where
    T: Monoid,
{
    pub fn new(a: &[T]) -> Self {
        let size = a.len();
        assert!(size.next_power_of_two() == size);
        let batch = size.trailing_zeros() as usize / 2;
        let data = a
            .chunks(1 << batch)
            .map(|a| StaticXorSegmentTree::new(a))
            .collect();
        Self { data, size, batch }
    }
    fn partition(&self, x: usize) -> (usize, usize) {
        (x >> self.batch, x & ((1 << self.batch) - 1))
    }
    pub fn update(&mut self, x: usize, v: T) {
        assert!(x < self.size);
        let (a, b) = self.partition(x);
        self.data[a].update(b, v);
    }
    pub fn find(&self, l: usize, r: usize, xor: usize) -> T {
        assert!(l <= r && r <= self.size && xor < self.size);
        if l == r {
            return T::e();
        }
        let (u, d) = self.partition(xor);
        let mut ans = T::e();
        for i in 0..(self.size >> self.batch) {
            let geta = i << self.batch;
            let l = l.max(geta);
            let r = r.min(geta + (1 << self.batch));
            if l >= r {
                continue;
            }
            if r - l == 1 << self.batch {
                ans = ans.merge(&self.data[u ^ self.partition(l).0].find_all(d));
            } else {
                ans = ans.merge(&self.data[u ^ self.partition(l).0].find(l - geta, r - geta, d));
            }
        }
        ans
    }
}

// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

use std::io::Write;

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}