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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: akakimidori
• 提出日時: 2026-09-05 00:42:02
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 12,183 bytes
• コンパイル時間: 1,650 ms
• コンパイル使用メモリ: 209,928 KB
• 実行使用メモリ: 100,912 KB
• 最終ジャッジ日時: 2026-09-05 00:42:19
• 合計ジャッジ時間: 15,067 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 9 TLE * 1 -- * 9

コンパイルメッセージ

warning: unused import: `std::io::Write`
 --> src/main.rs:2:5
  |
2 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: unused variable: `w`
  --> src/main.rs:21:9
   |
21 |     let w = std::mem::size_of::<usize>() * 8;
   |         ^ help: if this is intentional, prefix it with an underscore: `_w`
   |
   = note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Map` is never used
 --> src/main.rs:4:6
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

warning: variable `L` should have a snake case name
  --> src/main.rs:16:9
   |
16 |         L: [usize; m],
   |         ^ help: convert the identifier to snake case: `l`
   |
   = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default

warning: variable `R` should have a snake case name
  --> src/main.rs:17:9
   |
17 |         R: [usize; m],
   |         ^ help: convert the identifier to snake case: `r`

warning: variable `U` should have a snake case name
  --> src/main.rs:36:17
   |
36 |             let U = (L[z - 1] ^ y).max(1).min(n);
   |                 ^ help: convert the identifier to snake case (notice the capitalization): `u`

warning: variable `V` should have a snake case name
  --> src/main.rs:37:17
   |
37 |             let V = (R[z - 1] ^ y).max(1).min(n);
   |                 ^ help: convert the identifier to snake case (notice the capitalization): `v`

warning: variable `L` should have a snake case name
  --> src/main.rs:39:18
   |
39 |             let (L, R) = (U.min(V) - 1, U.max(V));
   |                  ^ help: convert the identifier to snake

ソースコード

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        n: usize,
        m: usize,
        a: [u32; n],
        l: [usize; m],
        r: [usize; m],
        x: [usize; m],
        L: [usize; m],
        R: [usize; m],
        q: usize,
        ask: [(usize, usize); q],
    }
    let w = std::mem::size_of::<usize>() * 8;
    let mut seg = vec![];
    for i in 0..30 {
        seg.push(LazySegmentTree::build(
            a.iter().map(|a| (*a >> i & 1, 1)),
            n,
            Sol,
        ));
    }
    for (i, (s, q)) in ask.into_iter().enumerate() {
        let mut y = i + 1;
        for j in 1..=q {
            let z = (s + j) % m + 1;
            let u = (l[z - 1] ^ y).max(1).min(n);
            let v = (r[z - 1] ^ y).max(1).min(n);
            let U = (L[z - 1] ^ y).max(1).min(n);
            let V = (R[z - 1] ^ y).max(1).min(n);
            let (l, r) = (u.min(v) - 1, u.max(v));
            let (L, R) = (U.min(V) - 1, U.max(V));
            let v = x[z - 1] ^ y;
            let mut sum = 0;
            for (i, seg) in seg.iter_mut().enumerate() {
                if z & 1 == 0 && v >> i & 1 == 1 {
                    seg.update(l, r, 1);
                }
                if z & 1 == 1 && v >> i & 1 == 0 {
                    seg.update(l, r, 0);
                }
                sum += seg.find(L, R).0 << i;
            }
            y = (sum % (1 << 30)) as usize;
        }
        println!("{}", y);
        for s in seg.iter_mut() {
            s.rollback();
        }
    }
}

struct Sol;
impl TE for Sol {
    type T = (u32, u32);
    type E = i32;
    fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T {
        (l.0 + r.0, l.1 + r.1)
    }
    fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T {
        if *f == -1 {
            *x
        } else if *f == 0 {
            (0, x.1)
        } else {
            (x.1, x.1)
        }
    }
    fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E {
        if *h != -1 {
            *h
        } else {
            *g
        }
    }
    fn e(&self) -> Self::T {
        (0, 0)
    }
    fn id(&self) -> Self::E {
        -1
    }
}

fn main() {
    run();
}

// 問題が読めん
// 区間or,and 区間和をonlineで処理して
// というのを複数個のパターンについて解いて
// 一つについて解くだけならbeatsでいい
// 毎回やると均しが破綻
// 欲しいのは和だし30個セグ木もって遅延伝搬すれば解けてはいる
// メモリが大変なことになってるが？
// 64個ずつ管理？
// rollback でメモリが大変にならないか？
// いやq_i <= 10^3 だった、なんとかなるか

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
// ---------- begin Lazy Segment Tree ----------
pub trait TE {
    type T: Copy;
    type E: Copy;
    fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T;
    fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T;
    fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E;
    fn e(&self) -> Self::T;
    fn id(&self) -> Self::E;
}

pub struct LazySegmentTree<R: TE> {
    n: usize,
    size: usize,
    bit: u32,
    op: R,
    data: InitArray<(R::T, R::E)>,
}

impl<R: TE> LazySegmentTree<R> {
    pub fn new(n: usize, op: R) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let bit = size.trailing_zeros();
        let data = InitArray::new_ini(vec![(op.e(), op.id()); 2 * size]);
        Self {
            n,
            size,
            bit,
            op,
            data,
        }
    }
    pub fn build<I>(init: I, n: usize, op: R) -> Self
    where
        I: Iterator<Item = R::T>,
    {
        let mut seg = Self::new(n, op);
        for (data, ini) in seg.data.data[seg.size..].iter_mut().zip(init) {
            data.0 = ini;
        }
        for i in (1..seg.size).rev() {
            seg.pull(i);
        }
        seg.data = InitArray::new_ini(seg.data.data);
        seg
    }
    pub fn update(&mut self, l: usize, r: usize, f: R::E) {
        assert!(l <= r && r <= self.n);
        if l == r {
            return;
        }
        self.push_range(l, r);
        let mut s = l + self.size;
        let mut t = r + self.size;
        while s < t {
            if s & 1 == 1 {
                self.apply(s, &f);
                s += 1;
            }
            if t & 1 == 1 {
                t -= 1;
                self.apply(t, &f);
            }
            s >>= 1;
            t >>= 1;
        }
        let l = l + self.size;
        let r = r + self.size;
        for k in 1..=self.bit {
            if (l >> k) << k != l {
                self.pull(l >> k);
            }
            if (r >> k) << k != r {
                self.pull((r - 1) >> k);
            }
        }
    }
    pub fn find(&mut self, l: usize, r: usize) -> R::T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.op.e();
        }
        self.push_range(l, r);
        let mut l = l + self.size;
        let mut r = r + self.size;
        let mut p = self.op.e();
        let mut q = self.op.e();
        while l < r {
            if l & 1 == 1 {
                p = self.op.fold(&p, &self.data[l].0);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                q = self.op.fold(&self.data[r].0, &q);
            }
            l >>= 1;
            r >>= 1;
        }
        self.op.fold(&p, &q)
    }
    pub fn set_at(&mut self, x: usize, v: R::T) {
        assert!(x < self.n);
        let x = x + self.size;
        for k in (1..=self.bit).rev() {
            self.push(x >> k);
        }
        self.data[x].0 = v;
        for k in 1..=self.bit {
            self.pull(x >> k);
        }
    }
    /*
    pub fn max_right<P>(&mut self, l: usize, f: P) -> usize
    where
        P: Fn(&R::T) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&self.op.e()));
        if l == self.n {
            return self.n;
        }
        self.push_range(l, self.n);
        let mut l = l + self.size;
        let mut sum = self.op.e();
        while {
            l >>= l.trailing_zeros();
            let v = self.op.fold(&sum, &self.data[l].0);
            if !f(&v) {
                while l < self.size {
                    self.push(l);
                    l <<= 1;
                    let v = self.op.fold(&sum, &self.data[l].0);
                    if f(&v) {
                        sum = v;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sum = v;
            l += 1;
            l.count_ones() > 1
        } {}
        self.n
    }
    pub fn min_left<P>(&mut self, r: usize, f: P) -> usize
    where
        P: Fn(&R::T) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&self.op.e()));
        if r == 0 {
            return 0;
        }
        self.push_range(0, r);
        let mut r = r + self.size;
        let mut sum = self.op.e();
        while {
            r -= 1;
            while r > 1 && r & 1 == 1 {
                r >>= 1;
            }
            let v = self.op.fold(&self.data[r].0, &sum);
            if !f(&v) {
                while r < self.size {
                    self.push(r);
                    r = 2 * r + 1;
                    let v = self.op.fold(&self.data[r].0, &sum);
                    if f(&v) {
                        sum = v;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sum = v;
            (r & (!r + 1)) != r
        } {}
        0
    }
    */
    fn push_range(&mut self, l: usize, r: usize) {
        let l = l + self.size;
        let r = r + self.size;
        for k in (1..(self.bit + 1)).rev() {
            if (l >> k) << k != l {
                self.push(l >> k);
            }
            if (r >> k) << k != r {
                self.push((r - 1) >> k);
            }
        }
    }
    fn apply(&mut self, x: usize, f: &R::E) {
        self.data[x].0 = self.op.eval(&self.data[x].0, f);
        self.data[x].1 = self.op.merge(&self.data[x].1, f);
    }
    fn push(&mut self, x: usize) {
        let f = std::mem::replace(&mut self.data[x].1, self.op.id());
        self.apply(2 * x, &f);
        self.apply(2 * x + 1, &f);
    }
    fn pull(&mut self, x: usize) {
        self.data[x].0 = self.op.fold(&self.data[2 * x].0, &self.data[2 * x + 1].0);
    }
    pub fn rollback(&mut self) {
        self.data.init();
    }
}
// ---------- end Lazy Segment Tree ----------
// ---------- begin init array ----------
// 初期化配列
// 初期値とサイズを与えて適当にやる系
// new(size, zero): zero埋めした長さsizeの配列を返す
// init(&mut self): 初期化
// init_with(&mut self, f): 非zero な添字とその値をfに渡して初期化
// indexMut でアクセスしたときその履歴を溜め込む
// それ以外でアクセスすると死ぬので注意
//
// 考えるべきこと
// 1. deref で dataへアクセスできるようにしていいか
//    derefmut はダメ
// 2. 今のままだと二次元配列の初期化とかには対応できない
//    なんか方法を考えたい
#[derive(Clone)]
pub struct InitArray<T> {
    data: Vec<T>,
    pre: Vec<T>,
    used: Vec<bool>,
    list: Vec<u32>,
}

impl<T: Copy> InitArray<T> {
    pub fn new(zero: T, size: usize) -> Self {
        InitArray {
            data: vec![zero; size],
            pre: vec![zero; size],
            used: vec![false; size],
            list: vec![],
        }
    }
    pub fn new_ini(pre: Vec<T>) -> Self {
        let size = pre.len();
        InitArray {
            data: pre.clone(),
            pre,
            used: vec![false; size],
            list: vec![],
        }
    }
    pub fn init(&mut self) {
        self.init_with(|_, _| ());
    }
    pub fn init_with<F>(&mut self, mut f: F)
    where
        F: FnMut(usize, T),
    {
        for x in self.list.drain(..) {
            let x = x as usize;
            self.used[x] = false;
            let v = std::mem::replace(&mut self.data[x], self.pre[x]);
            f(x, v);
        }
    }
}

impl<T> std::ops::Index<usize> for InitArray<T> {
    type Output = T;
    fn index(&self, pos: usize) -> &Self::Output {
        &self.data[pos]
    }
}

impl<T> std::ops::IndexMut<usize> for InitArray<T> {
    fn index_mut(&mut self, pos: usize) -> &mut Self::Output {
        if !self.used[pos] {
            self.used[pos] = true;
            self.list.push(pos as u32);
        }
        &mut self.data[pos]
    }
}
// ---------- end init array ----------