クエリ先読みも union-find も使わず、セグメント木を用いてクエリをオンラインに処理する、\(O (N + Q \ln N)\) 時間の方法をご紹介します。

まず \(N - 1\) 個の項からなる数列 \(( V _ i ) _ { i = 1 } ^ { N - 1 }\) と定数 \(x\) に対し、\(N\) 個の不定元 \(( A _ i ) _ { i = 1 } ^ N\) を持つ連立方程式

\[ \begin{aligned} A _ 1 + A _ 2 &= V _ 1, \\ A _ 2 + A _ 3 &= V _ 2, \\ &\vdots \\ A _ { N - 1 } + A _ N &= V _ { N - 1 }, \\ A _ i &= x \\ \end{aligned} \]

が一意な解

\[ \begin{aligned} A _ j &= \mathtt { alt } (i. j) - x &\ & (j -i \in 2 \mathbb Z + 1), \\ A _ j &= x \mp \mathtt { alt } (i. j) &\ & (j -i \in \pm 2 \mathbb N) \\ \end{aligned} \]

（ただし、\(\mathtt { alt } (i. j) \) はインデックス半開区間 \(\lbrack i, j\lbrack\) に対応する交代和 \(\sum _ { k = i } ^ { j - 1 } ( - 1 ) ^ { k - i } V _ k \ ( i \le j)\) です。）を持つことに注意します。

すると、クエリに答えるためには

• \(V\) の特定のインデックス区間 \(\lbrack i, j \lbrack\) に判明していない要素があればその旨を報告し、
• さもなくば交代和 \(\mathtt { alt } ( i, j)\) を計算する

という機能を持つデータ構造があればよいことがわかります。それは次のようなセグメント木で実現できます。

• 値:
  • \(V\) の値 \(x\) が判明している箇所は \((x, 1)\)
  • 判明していない場合は \((0, 0)\)
• 演算:
  • \((x, l) \circ (y, m) = (x + (-1) ^ l y, l + m)\)

なお、結果の第 \(2\) 要素が区間の長さと一致するとき、またそのときに限りその区間の \(V\) の値がすべて判明しており、さらにそのとき第 \(1\) 要素が交代和になっています。

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

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        queries: [(u8, Usize1, Usize1, i64); q],
    }
    let mut seg = Segtree(vec![(0, 0); 2 * n]);
    for &(com, i, j, value) in &queries {
        if com == 0 {
            if seg.sum(i, i + 1).1 == 0 {
                seg.set(i, value);
            }
        } else {
            let (alt, len) = seg.sum(i.min(j), i.max(j));
            if len == i.max(j) - i.min(j) {
                let ans = if len % 2 == 1 {
                    alt - value
                } else {
                    value + if i < j { -alt } else { alt }
                };
                println!("{}", ans);
            } else {
                println!("Ambiguous");
            }
        }
    }
}

struct Segtree(Vec<(i64, usize)>);
impl Segtree {
    fn set(&mut self, mut i: usize, value: i64) {
        i += self.0.len() / 2;
        self.0[i] = (value, 1);
        while i != 1 {
            i /= 2;
            self.0[i] = add(self.0[2 * i], self.0[2 * i + 1]);
        }
    }
    fn sum(&self, l: usize, r: usize) -> (i64, usize) {
        let mut lsum = (0, 0);
        let mut rsum = (0, 0);
        let mut l = l + self.0.len() / 2;
        let mut r = r + self.0.len() / 2;
        while l < r {
            if l % 2 == 1 {
                lsum = add(lsum, self.0[l]);
                l += 1;
            }
            if r % 2 == 1 {
                r -= 1;
                rsum = add(self.0[r], rsum);
            }
            l /= 2;
            r /= 2;
        }
        add(lsum, rsum)
    }
}

fn add(lhs: (i64, usize), rhs: (i64, usize)) -> (i64, usize) {
    (
        lhs.0 + if lhs.1 % 2 == 0 { rhs.0 } else { -rhs.0 },
        lhs.1 + rhs.1,
    )
}

提出 (40 ms): https://atcoder.jp/contests/typical90/submissions/28338771