#1177222 (Rust) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-15 11:55:27
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 4,440 ms / 6,000 ms
• コード長: 12,125 bytes
• コンパイル時間: 8,933 ms
• コンパイル使用メモリ: 190,712 KB
• 実行使用メモリ: 46,592 KB
• 最終ジャッジ日時: 2026-09-04 22:27:01
• 合計ジャッジ時間: 40,347 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 19

ソースコード

use std::fmt::Write as _;
use std::io::{self, Read};

const BITS: usize = 30;
const VALUE_MASK: u32 = (1u32 << BITS) - 1;

#[derive(Clone, Copy)]
struct Node {
    sum: u64,
    cnt: [u32; BITS],
    any: u32,
    all: u32,
    lazy_and: u32,
    lazy_or: u32,
}

impl Node {
    fn new() -> Self {
        Self {
            sum: 0,
            cnt: [0; BITS],
            any: 0,
            all: 0,
            lazy_and: VALUE_MASK,
            lazy_or: 0,
        }
    }
}

struct RollbackLazySegTree {
    n: usize,
    size: usize,
    tree: Vec<Node>,

    // A node is copied at most once in each subproblem.
    saved_epoch: Vec<usize>,
    epoch: usize,
    history: Vec<(usize, Node)>,
}

impl RollbackLazySegTree {
    fn new(a: &[u32]) -> Self {
        let n = a.len();
        let mut size = 1usize;

        while size < n {
            size <<= 1;
        }

        let mut seg = Self {
            n,
            size,
            tree: vec![Node::new(); size << 1],
            saved_epoch: vec![0; size << 1],
            epoch: 0,
            history: Vec::with_capacity(4096),
        };

        seg.build(1, 0, size - 1, a);
        seg
    }

    #[inline]
    fn contribution(count: u32, bit: usize) -> u64 {
        (count as u64) << bit
    }

    #[inline]
    fn save(&mut self, p: usize) {
        if self.saved_epoch[p] == self.epoch {
            return;
        }

        self.saved_epoch[p] = self.epoch;
        self.history.push((p, self.tree[p]));
    }

    fn build(
        &mut self,
        p: usize,
        l: usize,
        r: usize,
        a: &[u32],
    ) {
        self.tree[p] = Node::new();

        if l == r {
            let value = if l < self.n {
                a[l]
            } else {
                0
            };

            let cur = &mut self.tree[p];

            cur.sum = value as u64;
            cur.any = value;
            cur.all = value;

            for b in 0..BITS {
                cur.cnt[b] = (value >> b) & 1;
            }

            return;
        }

        let mid = (l + r) >> 1;

        self.build(p << 1, l, mid, a);
        self.build(p << 1 | 1, mid + 1, r, a);

        let left = self.tree[p << 1];
        let right = self.tree[p << 1 | 1];

        let cur = &mut self.tree[p];

        cur.sum = left.sum + right.sum;
        cur.any = left.any | right.any;
        cur.all = left.all & right.all;

        for b in 0..BITS {
            cur.cnt[b] = left.cnt[b] + right.cnt[b];
        }
    }

    fn apply_or(
        &mut self,
        p: usize,
        len: usize,
        mask: u32,
    ) -> u32 {
        let changed = mask & !self.tree[p].all;

        if changed == 0 {
            return 0;
        }

        self.save(p);

        let cur = &mut self.tree[p];
        let mut bits = changed;

        while bits != 0 {
            let b = bits.trailing_zeros() as usize;
            bits &= bits - 1;

            let old_count = cur.cnt[b];
            let new_count = len as u32;

            cur.sum += Self::contribution(new_count - old_count, b);
            cur.cnt[b] = new_count;
        }

        cur.any |= mask;
        cur.all |= mask;
        cur.lazy_or |= mask;

        changed
    }

    fn apply_and(
        &mut self,
        p: usize,
        mask: u32,
    ) -> u32 {
        let changed = self.tree[p].any & !mask;

        if changed == 0 {
            return 0;
        }

        self.save(p);

        let cur = &mut self.tree[p];
        let mut bits = changed;

        while bits != 0 {
            let b = bits.trailing_zeros() as usize;
            bits &= bits - 1;

            let old_count = cur.cnt[b];

            cur.sum -= Self::contribution(old_count, b);
            cur.cnt[b] = 0;
        }

        cur.any &= mask;
        cur.all &= mask;
        cur.lazy_and &= mask;
        cur.lazy_or &= mask;

        changed
    }

    fn push(
        &mut self,
        p: usize,
        l: usize,
        r: usize,
    ) {
        let lazy_and = self.tree[p].lazy_and;
        let lazy_or = self.tree[p].lazy_or;

        if l == r || (lazy_and == VALUE_MASK && lazy_or == 0) {
            return;
        }

        let mid = (l + r) >> 1;
        let left_len = mid - l + 1;
        let right_len = r - mid;

        self.apply_and(p << 1, lazy_and);
        self.apply_or(p << 1, left_len, lazy_or);

        self.apply_and(p << 1 | 1, lazy_and);
        self.apply_or(p << 1 | 1, right_len, lazy_or);

        self.save(p);

        self.tree[p].lazy_and = VALUE_MASK;
        self.tree[p].lazy_or = 0;
    }

    fn pull_changed(
        &mut self,
        p: usize,
        len: usize,
        changed: u32,
    ) {
        if changed == 0 {
            return;
        }

        self.save(p);

        let left = self.tree[p << 1];
        let right = self.tree[p << 1 | 1];

        let cur = &mut self.tree[p];

        let mut bits = changed;

        while bits != 0 {
            let b = bits.trailing_zeros() as usize;
            bits &= bits - 1;

            let bit_mask = 1u32 << b;

            let old_count = cur.cnt[b];
            let new_count = left.cnt[b] + right.cnt[b];

            if new_count > old_count {
                cur.sum +=
                    Self::contribution(new_count - old_count, b);
            } else {
                cur.sum -=
                    Self::contribution(old_count - new_count, b);
            }

            cur.cnt[b] = new_count;

            if new_count == 0 {
                cur.any &= !bit_mask;
            } else {
                cur.any |= bit_mask;
            }

            if new_count == len as u32 {
                cur.all |= bit_mask;
            } else {
                cur.all &= !bit_mask;
            }
        }
    }

    fn range_or_impl(
        &mut self,
        p: usize,
        l: usize,
        r: usize,
        ql: usize,
        qr: usize,
        mask: u32,
    ) -> u32 {
        if qr < l || r < ql {
            return 0;
        }

        if (mask & !self.tree[p].all) == 0 {
            return 0;
        }

        if ql <= l && r <= qr {
            return self.apply_or(
                p,
                r - l + 1,
                mask,
            );
        }

        self.push(p, l, r);

        let mid = (l + r) >> 1;

        let changed_left = self.range_or_impl(
            p << 1,
            l,
            mid,
            ql,
            qr,
            mask,
        );

        let changed_right = self.range_or_impl(
            p << 1 | 1,
            mid + 1,
            r,
            ql,
            qr,
            mask,
        );

        let changed = changed_left | changed_right;

        self.pull_changed(
            p,
            r - l + 1,
            changed,
        );

        changed
    }

    fn range_and_impl(
        &mut self,
        p: usize,
        l: usize,
        r: usize,
        ql: usize,
        qr: usize,
        mask: u32,
    ) -> u32 {
        if qr < l || r < ql {
            return 0;
        }

        if (self.tree[p].any & !mask) == 0 {
            return 0;
        }

        if ql <= l && r <= qr {
            return self.apply_and(p, mask);
        }

        self.push(p, l, r);

        let mid = (l + r) >> 1;

        let changed_left = self.range_and_impl(
            p << 1,
            l,
            mid,
            ql,
            qr,
            mask,
        );

        let changed_right = self.range_and_impl(
            p << 1 | 1,
            mid + 1,
            r,
            ql,
            qr,
            mask,
        );

        let changed = changed_left | changed_right;

        self.pull_changed(
            p,
            r - l + 1,
            changed,
        );

        changed
    }

    fn range_sum_impl(
        &mut self,
        p: usize,
        l: usize,
        r: usize,
        ql: usize,
        qr: usize,
    ) -> u64 {
        if qr < l || r < ql {
            return 0;
        }

        if ql <= l && r <= qr {
            return self.tree[p].sum;
        }

        self.push(p, l, r);

        let mid = (l + r) >> 1;

        self.range_sum_impl(
            p << 1,
            l,
            mid,
            ql,
            qr,
        ) + self.range_sum_impl(
            p << 1 | 1,
            mid + 1,
            r,
            ql,
            qr,
        )
    }

    fn begin_subproblem(&mut self) {
        self.epoch += 1;
        self.history.clear();
    }

    fn rollback(&mut self) {
        for &(p, node) in self.history.iter().rev() {
            self.tree[p] = node;
        }

        self.history.clear();
    }

    fn range_or(
        &mut self,
        l: usize,
        r: usize,
        mask: u32,
    ) {
        self.range_or_impl(
            1,
            0,
            self.size - 1,
            l,
            r,
            mask,
        );
    }

    fn range_and(
        &mut self,
        l: usize,
        r: usize,
        mask: u32,
    ) {
        self.range_and_impl(
            1,
            0,
            self.size - 1,
            l,
            r,
            mask,
        );
    }

    fn range_sum(
        &mut self,
        l: usize,
        r: usize,
    ) -> u64 {
        self.range_sum_impl(
            1,
            0,
            self.size - 1,
            l,
            r,
        )
    }
}

#[inline]
fn clamp_index(
    value: u32,
    n: usize,
) -> usize {
    if value < 1 {
        1
    } else if value > n as u32 {
        n
    } else {
        value as usize
    }
}

fn main() {
    let mut input = String::new();
    io::stdin()
        .read_to_string(&mut input)
        .unwrap();

    let mut it = input.split_whitespace();

    let n: usize =
        it.next().unwrap().parse().unwrap();
    let m: usize =
        it.next().unwrap().parse().unwrap();

    let mut a = vec![0u32; n];

    for value in &mut a {
        *value =
            it.next().unwrap().parse().unwrap();
    }

    let mut l = vec![0u32; m + 1];
    let mut r = vec![0u32; m + 1];
    let mut x = vec![0u32; m + 1];
    let mut big_l = vec![0u32; m + 1];
    let mut big_r = vec![0u32; m + 1];

    for i in 1..=m {
        l[i] =
            it.next().unwrap().parse().unwrap();
    }

    for i in 1..=m {
        r[i] =
            it.next().unwrap().parse().unwrap();
    }

    for i in 1..=m {
        x[i] =
            it.next().unwrap().parse().unwrap();
    }

    for i in 1..=m {
        big_l[i] =
            it.next().unwrap().parse().unwrap();
    }

    for i in 1..=m {
        big_r[i] =
            it.next().unwrap().parse().unwrap();
    }

    let mut seg =
        RollbackLazySegTree::new(&a);

    let q_count: usize =
        it.next().unwrap().parse().unwrap();

    let mut output = String::new();

    for i in 1..=q_count {
        let s: usize =
            it.next().unwrap().parse().unwrap();

        let q: usize =
            it.next().unwrap().parse().unwrap();

        seg.begin_subproblem();

        let mut y = i as u32;

        for j in 1..=q {
            let z = ((s + j) % m) + 1;

            let u =
                clamp_index(l[z] ^ y, n);
            let v =
                clamp_index(r[z] ^ y, n);

            let ql = u.min(v) - 1;
            let qr = u.max(v) - 1;

            let big_u =
                clamp_index(big_l[z] ^ y, n);
            let big_v =
                clamp_index(big_r[z] ^ y, n);

            let sum_l =
                big_u.min(big_v) - 1;
            let sum_r =
                big_u.max(big_v) - 1;

            let mask = x[z] ^ y;

            if (z & 1) == 0 {
                seg.range_or(
                    ql,
                    qr,
                    mask,
                );
            } else {
                seg.range_and(
                    ql,
                    qr,
                    mask,
                );
            }

            y =
                (seg.range_sum(sum_l, sum_r) as u32)
                    & VALUE_MASK;
        }

        writeln!(&mut output, "{}", y).unwrap();

        seg.rollback();
    }

    print!("{}", output);
}