結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-08-06 23:10:11 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 259 ms / 5,000 ms |
コード長 | 3,559 bytes |
コンパイル時間 | 13,498 ms |
コンパイル使用メモリ | 379,844 KB |
実行使用メモリ | 23,312 KB |
最終ジャッジ日時 | 2024-09-17 03:25:54 |
合計ジャッジ時間 | 15,766 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
コンパイルメッセージ
warning: unused variable: `i` --> src/main.rs:23:9 | 23 | for i in 0..n - 1 { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `i` --> src/main.rs:30:9 | 30 | for i in 0..q { | ^ help: if this is intentional, prefix it with an underscore: `_i`
ソースコード
#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::<usize>(); let (n, q) = (v[0], v[1]); let c = read_vec::<i64>(); let mut edges = vec![vec![]; n]; for i in 0..n - 1 { let v = read_vec::<usize>(); let (a, b) = (v[0] - 1, v[1] - 1); edges[a].push(b); edges[b].push(a); } let mut queries = vec![]; for i in 0..q { let v = read_vec::<i64>(); let (t, x, y) = (v[0], v[1] as usize - 1, v[2]); queries.push((t, x, y)); } let mut pre_order = vec![0usize; n]; let mut post_order = vec![0usize; n]; dfs(0, 0, &edges, &mut 0, &mut pre_order, &mut post_order); debug!(pre_order); debug!(post_order); let mut seg = SegTree::new(n, 0i64, |x, y| x ^ y); for i in 0..n { seg.update(pre_order[i], c[i]); } for (t, x, y) in queries { if t == 1 { let val = seg.query(pre_order[x], pre_order[x] + 1); seg.update(pre_order[x], val ^ y); } else { let ans = seg.query(pre_order[x], post_order[x]); println!("{}", ans); } } } fn dfs( cur: usize, parent: usize, edges: &Vec<Vec<usize>>, count: &mut usize, pre_order: &mut Vec<usize>, post_order: &mut Vec<usize>, ) { pre_order[cur] = *count; *count += 1; for &to in edges[cur].iter().filter(|&&x| x != parent) { dfs(to, cur, edges, count, pre_order, post_order); } post_order[cur] = *count; } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone)] struct SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { n: usize, dat: Vec<T>, init: T, functor: F, } impl<T, F> SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { fn new(n: usize, init: T, f: F) -> SegTree<T, F> { let mut m = 1; // For simplicity, we use 2 ** n sized SegTree. while m < n { m *= 2; } SegTree { n: m, dat: vec![init; 2 * m - 1], init: init, functor: f, } } // dat[k] = a; fn update(&mut self, k: usize, a: T) { let mut k = k; k += self.n - 1; self.dat[k] = a; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]); } } // [a, b) fn query(&self, a: usize, b: usize) -> T { self.query_inner(a, b, 0, 0, self.n) } fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.init; } if a <= l && r <= b { return self.dat[k]; } let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2); let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r); (self.functor)(vl, vr) } }