結果
問題 | 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>whereF: 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>whereF: 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)}}