結果

問題 No.1891 Static Xor Range Composite Query
ユーザー akakimidoriakakimidori
提出日時 2022-04-07 12:29:11
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,587 ms / 5,000 ms
コード長 5,062 bytes
コンパイル時間 1,089 ms
コンパイル使用メモリ 158,840 KB
実行使用メモリ 26,472 KB
最終ジャッジ日時 2023-08-18 17:06:54
合計ジャッジ時間 20,053 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1,587 ms
26,472 KB
testcase_22 AC 1,582 ms
26,428 KB
testcase_23 AC 1,585 ms
26,472 KB
testcase_24 AC 1,575 ms
26,404 KB
testcase_25 AC 1,574 ms
26,372 KB
testcase_26 AC 1,578 ms
26,452 KB
testcase_27 AC 1,580 ms
26,376 KB
testcase_28 AC 1,574 ms
26,456 KB
testcase_29 AC 1,587 ms
26,372 KB
testcase_30 AC 1,587 ms
26,404 KB
権限があれば一括ダウンロードができます

ソースコード

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 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 XorSegmentTree<T> {
    data: Vec<Vec<T>>,
    size: 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 k = size.trailing_zeros() as usize / 2;
        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 {
                return x.merge(&y);
            }
        }
        let k = self.data.len() - 1;
        l >>= k;
        r >>= k;
        let data = self.data.last().unwrap();
        for i in l..r {
            x = x.merge(&data[(i << k) ^ xor]);
        }
        x.merge(&y)
    }
    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;
        }
    }
}

// ---------- 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