q068.rs

// B[i] = ((-1)^i)*A[i]とおく (iは0-indexed. 以下小文字の添字はは0_indexed)
// T=0 で与えられる情報は(-1)^x * B[x] + (-1)^(x+1) * B[x+1] = V
// diff_b[x] = B[x+1] - B[x]と定義すると、diff_b[x] = -(-1)^x * V
// T=1 でB[x]が与えられるので、例えば x<y の場合、diff_b[x], .., diff_b[y-1]が判明していればB[y]が求められる。
// diff_b[x] + .. + diff_b[y-1]を高速に計算するためにBITを利用する。
// diff_b[x], .., diff_b[y-1]が全て判明しているかもBITで管理する。

use proconio::{input, fastout, marker::Usize1};

#[fastout]
fn main() {
    // #1 入力
    input! {
        n: usize,
        q: usize,
        txyv: [(i32, Usize1, Usize1, i64); q]
    }
    // diff_b[i]が未判明ならambiguous_cnt[i] = 1, 判明していれば0.
    let mut ambiguous_cnt = BITree::new(n);
    for i in 0..n { ambiguous_cnt.set(i, 1); }
    // diff_b[i] = b[i+1] - b[i].
    let mut diff_b = BITree::new(n);

    for (t, x, y, v) in txyv {
        // s(i) = (-1)^i
        let s = |i| if i&1==0 {1} else {-1};
        if t == 0 {
            if ambiguous_cnt.get(x) == 1 {
            // diff_b[i]が新規に判明すれば、代入する
                ambiguous_cnt.set(x, 0);
                diff_b.set(x, -v*s(x));
            }
            else {
            // 以前に判明していた情報なら、矛盾のないことを保証する
                assert_eq!{diff_b.get(x), -v*s(x)};
            }
        } else if x < y {
            if ambiguous_cnt.sumlr(x, y-1) != 0 {
            // (B[x+1] - B[x]) + .. + (B[y] - B[y-1])までに不明なところが１つでもあればambiguous
                println!("Ambiguous");
            } else {
            // B[y] = B[x] + (B[y] - B[x])
                let b = v*s(x) + diff_b.sumlr(x, y-1);
            // A[y] = (-1)^y * B[y]
                println!("{}", b*s(y));
            }
        } else if x > y {
            // (B[y+1] - B[y]) + .. + (B[x] - B[x-1])までに不明なところが１つでもあればambiguous
            if ambiguous_cnt.sumlr(y, x-1) != 0 {
                println!("Ambiguous");
            } else {
            // B[y] = B[x] - (B[x] - B[y])
                let b = v*s(x) - diff_b.sumlr(y, x-1); 
            // A[y] = (-1)^y * B[y]
                println!("{}", b*s(y));
            }
        } else if x == y {
            println!("{}", v);
        }
    }
}

use num::Num;
struct BITree<N> {
    n: usize,
    data: Vec<N>,
}
impl<N: Num + Copy> BITree<N> {
    fn new (n: usize) -> Self {
        Self { n, data: vec![N::zero(); n+1]}
    }
    fn add(&mut self, i: usize, x: N) {
        assert!(i < self.n);
        let mut ip1 = i + 1;
        while ip1 <= self.n {
            self.data[ip1] = self.data[ip1] + x;
            ip1 += 1 << ip1.trailing_zeros();
        }
    }
    fn sum(&self, mut ip1: usize) -> N {
        assert!(ip1 <= self.n);
        let mut res = N::zero();
        while ip1 != 0 {
            res = res + self.data[ip1];
            ip1 -= 1 << ip1.trailing_zeros();
        }
        res
    }
    fn sumlr(&self, l: usize, r: usize) -> N {
        assert!(l <= r && r < self.n);
        let res = self.sum(r+1) - self.sum(l);
        res
    }
    fn get(&self, i: usize) -> N {
        assert!(i < self.n);
        let res = self.sumlr(i, i);
        res
    }
    fn set(&mut self, i: usize, x: N) {
        assert!(i < self.n);
        let diff = x - self.get(i);
        self.add(i, diff);
    }
}