概要

区間 \([L,R]\) のスコアは、累積和を使うと「2 点間の差」として表せます。
各版を木として見て、木を DFS しながら rollback 可能な重み付き Union-Find で制約を管理します。

考察

まず、累積和を考えます。

\(P_0 = 0\)、\(P_i = (A_1 + A_2 + \cdots + A_i) \bmod K\) とすると、区間 \([L,R]\) のスコアは

\[ (P_R - P_{L-1}) \bmod K \]

です。

つまり、主張

\[ \text{区間 } [L,R] \text{ のスコアは } X \]

は、次のような制約になります。

\[ P_R - P_{L-1} \equiv X \pmod K \]

これは「頂点 \(L-1\) と頂点 \(R\) の差が \(X\)」という形の制約です。

例えば \(K=10\) のとき、

• \([2,4]\) のスコアが \(3\)
  \(\Rightarrow P_4 - P_1 \equiv 3 \pmod{10}\)
• \([1,1]\) のスコアが \(7\)
  \(\Rightarrow P_1 - P_0 \equiv 7 \pmod{10}\)

なら、

\[ P_4 - P_0 = (P_4 - P_1) + (P_1 - P_0) \equiv 3 + 7 \equiv 0 \pmod{10} \]

となり、\([1,4]\) のスコアは \(0\) と一意に分かります。

このように、問題は「差分制約を追加したり、2 点間の差が一意に分かるかを判定する問題」になります。

差分制約は、重み付き Union-Find で扱えます。

• \(P_v - P_u = X\) という制約を追加するとき
  • \(u, v\) が別連結成分なら、矛盾しないので連結する
  • すでに同じ連結成分なら、既に分かっている差と \(X\) が一致するか確認する
• \(P_v - P_u\) を質問するとき
  • \(u, v\) が同じ連結成分なら、その差は一意に分かる
  • 別連結成分なら、一方の成分全体をずらせるので一意には決まらない

素朴に各版ごとに Union-Find をコピーすると、各操作で \(O(N)\) かかり、\(O(NQ)\) となって間に合いません。

そこで、版の構造に注目します。

操作 \(i\) は既存の版 \(B\) から新しい版 \(i\) を作ります。
つまり、版を頂点、参照元 \(B\) から \(i\) へ辺を張ると、版全体は根を版 \(0\) とする木になります。

この木を DFS しながら、

1. 親の状態から操作を適用する
2. 子孫を処理する
3. 処理が終わったら操作前の状態に戻す

という流れにすれば、Union-Find をコピーせずに済みます。

状態を戻すために、rollback 可能な重み付き Union-Find を使います。

アルゴリズム

頂点は累積和 \(P_0, P_1, \ldots, P_N\) に対応するので、\(N+1\) 個用意します。

操作で与えられる区間 \([L,R]\) は、

\[ u = L-1,\quad v = R \]

として、差分制約

\[ P_v - P_u \]

を扱います。

重み付き Union-Find

各頂点 \(x\) について、親への重みを

\[ \text{weight}[x] = P_x - P_{\text{parent}[x]} \pmod K \]

として持ちます。

find(x) では、根とともに

\[ P_x - P_{\text{root}} \]

を返します。

制約

\[ P_v - P_u \equiv w \pmod K \]

を追加する場合を考えます。

find(u) により

\[ P_u - P_{r_u} = p_u \]

find(v) により

\[ P_v - P_{r_v} = p_v \]

が分かっているとします。

• \(r_u = r_v\) の場合
  既に

$\( P_v - P_u \equiv p_v - p_u \pmod K \)$

が分かっています。
これが \(w\) と一致すれば受理、しなければ矛盾です。

• \(r_u \ne r_v\) の場合
  2 つの連結成分を併合します。
  このとき、根同士の相対的な差を適切に設定すれば、必ず制約を満たせます。

版の木を DFS

まず全操作を読み込み、children[B] に操作番号 \(i\) を追加します。
これにより、版 \(B\) から版 \(i\) への辺を作ります。

DFS では、現在の Union-Find の状態が「現在の版の状態」を表すようにします。

各子 idx について、

1. rollback 用に現在の状態を保存する
2. 操作 idx を適用する
   • 種類 \(0\) なら制約を追加できるか判定し、YES / NO
   • 種類 \(1\) なら差が分かるか判定し、値または UNKNOWN
3. DFS で版 idx の子孫を処理する
4. 保存した状態まで rollback する

種類 \(0\) の操作で矛盾した場合、その制約は追加されません。
したがって、その版は参照元の版と同じ状態になります。
これは、Union-Find の状態を変更しないことで自然に表現できます。

また、種類 \(1\) の操作も制約を追加しないので、状態は変わりません。

計算量

• 時間計算量: \(O(N + Q \log N)\)
• 空間計算量: \(O(N + Q)\)

重み付き Union-Find では rollback のために経路圧縮を使わず、union by size のみを使います。
そのため、find は \(O(\log N)\) です。

実装のポイント

• 区間 \([L,R]\) は頂点 \(L-1\) と \(R\) の差として扱います。

• 値はすべて \(\bmod K\) で管理します。負になった場合は \(K\) を足して正規化します。

• rollback のため、Union-Find では経路圧縮をしません。

• 併合時には、変更前の情報を履歴に積みます。

  • どちらの根を子にしたか
  • 併合先の根
  • 併合先のサイズ

• DFS の各子を処理する前に snapshot() を取り、処理後に rollback() します。

• DFS の順番は入力順と異なる可能性があるため、答えは配列に保存しておき、最後に操作番号順に出力します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct RollbackWeightedDSU {
    int n;
    long long mod;
    vector<int> parent, sz;
    vector<long long> weight; // weight[x] = value[x] - value[parent[x]] (mod mod)

    struct Change {
        int child;
        int root;
        int oldSize;
    };
    vector<Change> history;

    RollbackWeightedDSU() = default;

    void init(int n_, long long mod_) {
        n = n_;
        mod = mod_;
        parent.resize(n);
        sz.assign(n, 1);
        weight.assign(n, 0);
        iota(parent.begin(), parent.end(), 0);
        history.clear();
    }

    long long norm(long long x) const {
        x %= mod;
        if (x < 0) x += mod;
        return x;
    }

    pair<int, long long> find(int x) const {
        long long pot = 0;
        while (parent[x] != x) {
            pot += weight[x];
            pot %= mod;
            x = parent[x];
        }
        return {x, pot};
    }

    size_t snapshot() const {
        return history.size();
    }

    void rollback(size_t snap) {
        while (history.size() > snap) {
            auto c = history.back();
            history.pop_back();
            parent[c.child] = c.child;
            weight[c.child] = 0;
            sz[c.root] = c.oldSize;
        }
    }

    bool addConstraint(int u, int v, long long w) {
        w = norm(w);

        auto [ru, pu] = find(u);
        auto [rv, pv] = find(v);

        if (ru == rv) {
            return norm(pv - pu) == w;
        }

        if (sz[ru] < sz[rv]) {
            history.push_back({ru, rv, sz[rv]});
            parent[ru] = rv;
            weight[ru] = norm(pv - pu - w);
            sz[rv] += sz[ru];
        } else {
            history.push_back({rv, ru, sz[ru]});
            parent[rv] = ru;
            weight[rv] = norm(w + pu - pv);
            sz[ru] += sz[rv];
        }

        return true;
    }

    pair<bool, long long> queryDiff(int u, int v) const {
        auto [ru, pu] = find(u);
        auto [rv, pv] = find(v);

        if (ru != rv) return {false, 0};
        return {true, norm(pv - pu)};
    }
};

struct Query {
    int type;
    int B;
    int L;
    int R;
    long long X;
};

int N, Q;
long long K;
vector<Query> queries;
vector<vector<int>> children;
vector<string> answer;
RollbackWeightedDSU dsu;

void dfs(int ver) {
    for (int idx : children[ver]) {
        size_t snap = dsu.snapshot();
        const auto &q = queries[idx];

        int u = q.L - 1;
        int v = q.R;

        if (q.type == 0) {
            bool ok = dsu.addConstraint(u, v, q.X);
            answer[idx] = ok ? "YES" : "NO";
        } else {
            auto [known, val] = dsu.queryDiff(u, v);
            answer[idx] = known ? to_string(val) : "UNKNOWN";
        }

        dfs(idx);
        dsu.rollback(snap);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K >> Q;

    queries.resize(Q + 1);
    children.assign(Q + 1, {});
    answer.resize(Q + 1);

    for (int i = 1; i <= Q; i++) {
        int type;
        cin >> type;

        queries[i].type = type;

        if (type == 0) {
            cin >> queries[i].B >> queries[i].L >> queries[i].R >> queries[i].X;
        } else {
            cin >> queries[i].B >> queries[i].L >> queries[i].R;
            queries[i].X = 0;
        }

        children[queries[i].B].push_back(i);
    }

    dsu.init(N + 1, K);

    dfs(0);

    for (int i = 1; i <= Q; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。