結果

問題 No.1891 Static Xor Range Composite Query
ユーザー akakimidori
提出日時 2022-04-07 11:41:43
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 263 ms / 5,000 ms
コード長 4,148 bytes
コンパイル時間 14,889 ms
コンパイル使用メモリ 378,572 KB
実行使用メモリ 43,016 KB
最終ジャッジ日時 2025-02-19 03:39:56
合計ジャッジ時間 23,933 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 seg = StaticXorSegmentTree::new(&a);
    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)
    }
}

// ---------- 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);
}
0