結果
| 問題 | No.1641 Tree Xor Query |
| ユーザー |
 ziita
|
| 提出日時 | 2021-09-07 19:11:28 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 258 ms / 5,000 ms |
| コード長 | 7,390 bytes |
| コンパイル時間 | 13,960 ms |
| コンパイル使用メモリ | 377,732 KB |
| 実行使用メモリ | 40,320 KB |
| 最終ジャッジ日時 | 2024-12-23 17:52:46 |
| 合計ジャッジ時間 | 16,551 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
#![allow(unused_imports)]#![allow(non_snake_case, unused)]// ---------- begin input macro ----------// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 よりmacro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------use std::cmp::*;use std::collections::*;use std::ops::*;use std::marker::*;const INF: i64 = std::i64::MAX/100;const MOD: i64 = 1_000_000_007;// const MOD: i64 = 998_244_353;struct EulerTour {G: Vec<Vec<(usize,i64)>>,tour: Vec<usize>,L: Vec<usize>,R: Vec<usize>,depth: Vec<usize>,weight: Vec<i64>,n: usize,}impl EulerTour{fn new(n: usize) -> EulerTour {EulerTour{G: vec![vec![];n],tour: vec![],L: vec![0;n],R: vec![0;n],depth: vec![0;n],weight: vec![0;n],n: n,}}fn add_edge(&mut self, s: usize, t: usize, w: i64){self.G[s].push((t,w));self.G[t].push((s,w));}fn init(&mut self, root: usize) {self.dfs(root, self.n, 0, 0);}fn dfs(&mut self, v: usize, p: usize, d: usize, w: i64){self.tour.push(v);self.L[v] = self.tour.len()-1;self.depth[v] = d;self.weight[v] = w;for z in self.G[v].clone() {if z.0 == p {continue;}self.dfs(z.0, v, d+1, w+z.1);self.tour.push(v);}self.R[v] = self.tour.len()-1;}}// ---------- begin lazy segment tree ----------// https://yukicoder.me/submissions/379658 よりpub trait TE {type T: Clone;type E: Clone;fn fold(l:Self::T, r:Self::T) -> Self::T;fn eval(p:Self::T, x:Self::E) -> Self::T;fn merge(f:Self::E, g:Self::E) -> Self::E;fn e() -> Self::T;fn id() -> Self::E;}pub struct LazySegmentTree<R: TE> {size: usize,bit: usize,a: Vec<(R::T, R::E)>,}impl <R: TE> LazySegmentTree<R> {pub fn new(n: usize) -> LazySegmentTree<R> {let mut bit = 0;while (1 << bit) < n {bit += 1;}LazySegmentTree {size: 1 << bit,bit: bit,a: vec![(R::e(), R::id()); 2 << bit],}}pub fn build_by(z: &[R::T]) -> LazySegmentTree<R> {let n = z.len();let mut bit = 0;while (1 << bit) < n {bit += 1;}let mut a = vec![(R::e(), R::id()); 2 << bit];for (a, z) in a[(1 << bit)..].iter_mut().zip(z.iter()) {a.0 = z.clone();}for i in (1..(1 << bit)).rev() {let l = R::eval(a[2 * i].0.clone(), a[2 * i].1.clone());let r = R::eval(a[2 * i + 1].0.clone(), a[2 * i + 1].1.clone());a[i].0 = R::fold(l, r);}LazySegmentTree {size: 1 << bit,bit : bit,a: a,}}fn eval(&self, k: usize) -> R::T {R::eval(self.a[k].0.clone(), self.a[k].1.clone())}fn propagate(&mut self, x: usize) {let x = x + self.size;for i in (1..(self.bit + 1)).rev() {let k = x >> i;self.a[2 * k].1 = R::merge(self.a[2 * k].1.clone(), self.a[k].1.clone());self.a[2 * k + 1].1 = R::merge(self.a[2 * k + 1].1.clone(), self.a[k].1.clone());self.a[k].1 = R::id();self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1));}}fn save(&mut self, x: usize) {let x = x + self.size;for i in 1..(self.bit + 1) {let k = x >> i;self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1));}}pub fn update(&mut self, l: usize, r: usize, op: R::E) {self.propagate(l);self.propagate(r - 1);let mut x = l + self.size;let mut y = r + self.size;while x < y {if x & 1 == 1 {self.a[x].1 = R::merge(self.a[x].1.clone(), op.clone());x += 1;}if y & 1 == 1 {y -= 1;self.a[y].1 = R::merge(self.a[y].1.clone(), op.clone());}x >>= 1;y >>= 1;}self.save(l);self.save(r - 1);}pub fn find(&mut self, l: usize, r: usize) -> R::T {self.propagate(l);self.propagate(r - 1);let mut x = l + self.size;let mut y = r + self.size;let mut p = R::e();let mut q = R::e();while x < y {if x & 1 == 1 {p = R::fold(p, self.eval(x));x += 1;}if y & 1 == 1 {y -= 1;q = R::fold(self.eval(y), q);}x >>= 1;y >>= 1;}R::fold(p, q)}}struct R;impl TE for R {type T = usize;type E = usize;fn fold(l: Self::T, r: Self::T) -> Self::T {l ^ r}fn eval(p: Self::T, x: Self::E) -> Self::T {p ^ x}fn merge(f: Self::E, g: Self::E) -> Self::E {f ^ g}fn e() -> Self::T {0}fn id() -> Self::E {0}}// ---------- end lazy segment tree ----------fn main() {input! {n: usize,q: usize,c: [usize;n],ab: [(usize,usize);n-1],txy: [(usize,usize,usize);q],}let mut eulor = EulerTour::new(n);for &(a,b) in &ab {eulor.add_edge(a-1, b-1, 0);}eulor.init(0);let mut seg = LazySegmentTree::<R>::new(2*n);for i in 0..n {let col = c[i];let l = eulor.L[i];let r = eulor.R[i];seg.update(l,l+1,col);}for &(t,x,y) in &txy {if t==1 {let idx = eulor.L[x-1];// println!("{}",idx);seg.update(idx,idx+1,y);}else {let l = eulor.L[x-1];let r = eulor.R[x-1];let ans = seg.find(l,r+1);println!("{}",ans);}}}