結果

問題 No.1891 Static Xor Range Composite Query
ユーザー akakimidori
提出日時 2022-04-07 11:08:57
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 445 ms / 5,000 ms
コード長 6,535 bytes
コンパイル時間 13,904 ms
コンパイル使用メモリ 393,156 KB
実行使用メモリ 65,576 KB
最終ジャッジ日時 2024-11-27 23:27:48
合計ジャッジ時間 21,174 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 mut data = vec![vec![]; 2 * size];
        for (data, a) in data[size..].iter_mut().zip(a.iter()) {
            *data = vec![a.clone()];
        }
        for i in (1..size).rev() {
            let a = &data[2 * i];
            let b = &data[2 * i + 1];
            let mut c = Vec::with_capacity(2 * a.len());
            c.extend(a.iter().zip(b.iter()).map(|(a, b)| a.merge(b)));
            c.extend(a.iter().zip(b.iter()).map(|(a, b)| b.merge(a)));
            data[i] = c;
        }
        Self { data, size }
    }
    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 mut l = l + self.size;
        let mut r = r + self.size;
        let mut shift = 0;
        let mut x = T::e();
        let mut y = T::e();
        while l < r {
            if l & 1 == 1 {
                let a = l ^ (xor >> shift);
                let b = xor & ((1 << shift) - 1);
                x = x.merge(&self.data[a][b]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                let a = r ^ (xor >> shift);
                let b = xor & ((1 << shift) - 1);
                y = self.data[a][b].merge(&y);
            }
            l >>= 1;
            r >>= 1;
            shift += 1;
        }
        x.merge(&y)
    }
    pub fn find_all(&self, xor: usize) -> T {
        assert!(xor < self.size);
        self.data[1][xor].clone()
    }
    fn update(&mut self, x: usize, v: T) {
        let mut x = x + self.size;
        self.data[x][0] = v;
        x >>= 1;
        while x >= 1 {
            let mut c = std::mem::take(&mut self.data[x]);
            let a = &self.data[2 * x];
            let b = &self.data[2 * x + 1];
            let ab = a.iter().zip(b.iter()).chain(b.iter().zip(a.iter()));
            for (c, (a, b)) in c.iter_mut().zip(ab) {
                *c = a.merge(b);
            }
            self.data[x] = c;
            x >>= 1;
        }
    }
}

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