Submission #65814623

---

Source Code Expand

use proconio::input;

const HEIGHT: usize = 30;

fn main() {
    input! {
        q: usize,
        queries: [usize; q],
    }
    let mut root = SegtreeNode {
        children: [None, None],
        value: Value {
            sum: [0, 0],
            parity: 0,
        },
    };
    let mut prev_ans = 0;
    for &query in &queries {
        let query = (prev_ans + query) % 1_000_000_000 + 1;
        root.insert(query, HEIGHT);
        let ans = root.value.sum[0];
        println!("{ans}");
        prev_ans = ans;
    }
}

#[derive(PartialEq, Eq, Clone, Copy)]
struct Value {
    sum: [usize; 2],
    parity: usize,
}
impl std::fmt::Debug for Value {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_tuple("")
            .field(&self.sum)
            .field(&self.parity)
            .finish()
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
struct SegtreeNode {
    children: [Option<Box<SegtreeNode>>; 2],
    value: Value,
}
impl SegtreeNode {
    fn insert(&mut self, query: usize, height: usize) {
        if height == 0 {
            self.value.sum[self.value.parity] += query;
            self.value.parity ^= 1;
            return;
        }
        let dir = (query >> (height - 1)) & 1;
        if self.children[dir].is_none() {
            self.children[dir] = Some(Box::new(SegtreeNode {
                children: [None, None],
                value: Value {
                    sum: [0, 0],
                    parity: 0,
                },
            }));
        }
        let child = self.children[dir].as_mut().unwrap();
        child.insert(query, height - 1);
        let value = [
            self.children[0].as_ref().map_or([0, 0], |c| c.value.sum),
            self.children[1].as_ref().map_or([0, 0], |c| c.value.sum),
        ];
        let parity = [
            self.children[0].as_ref().map_or(0, |c| c.value.parity),
            self.children[1].as_ref().map_or(0, |c| c.value.parity),
        ];
        self.value.sum = [
            value[0][0] + value[1][parity[0]],
            value[0][1] + value[1][1 ^ parity[0]],
        ];
        self.value.parity = parity[0] ^ parity[1];
    }
}

Submission Info

Judge Result