Overview

This problem involves converting congruence conditions on interval sums into “difference equalities,” and traversing a structure where versions branch in a tree-like manner using DFS, while performing consistency checks and value determination using a weighted Union-Find (with rollback).

Key Observations

The core of this problem is handling interval sums of the form: [ (A_L+\cdots+A_R)\bmod K ]

First, define the prefix sums (mod \(K\)) as: [ S_i = (A_1+\cdots+A_i)\bmod K,\quad S_0=0 ]

Then: [ (A_L+\cdots+A_R)\bmod K = (SR-S{L-1})\bmod K ]

So the claim score(L,R)=X becomes a “constraint on the difference between two points”: [ SR - S{L-1} \equiv X \pmod K ]

---

Naively copying the constraint set for each version and checking would be far too slow, since the number of versions can be up to \(10^5\).
Also, since each query “creates version \(i\) with version \(B\) as its parent,” the versions form a tree (with 0 as the root).

Using this structure:

• Explore the version tree with DFS
• Add constraints when going down an edge in the DFS
• Undo constraints when backtracking (rollback)

This allows us to efficiently reconstruct the state of each version.

---

To manage the difference constraints, we use a weighted Union-Find.
Each node \(x\) stores the “difference from its parent,” and for nodes in the same connected component, we can compute: [ S_y-S_x \pmod K ]

• Type 0 (adding a claim)
  Add [SR-S{L-1}=X] as unite(L-1, R, X).
  If they are already in the same component, check for contradiction; if in different components, merge them.

• Type 1 (query)
  If \(L-1\) and \(R\) are in the same component, the difference is uniquely determined, so output that value.
  If they are in different components, output UNKNOWN.

This correctly handles both “whether it is acceptable” and “whether it is uniquely determined.”

Algorithm

1. Read the queries and build the version tree with children[B].push_back(i).
2. Use nodes \(0..N\) (prefix sums \(S_0..S_N\)).
3. Prepare a rollback-capable weighted DSU:
   • findp(x): returns the root and \(S_x-S_{root}\)
   • unite(x,y,w): adds the constraint \(S_y-S_x=w\), returns false if contradictory
   • queryDiff(x,y): if in the same component, returns \(S_y-S_x\)
   • snapshot()/rollback(): history management
4. DFS on the version tree:
   • Before entering a child version, snap = snapshot()
   • Process the query:
     • type 0: unite(L-1, R, X)
       

          - Success: `YES`
          - Failure: `NO` (state effectively unchanged)
       

     • type 1: queryDiff(L-1, R)
       

          - If obtainable: output the value
          - If not: `UNKNOWN`
       

   • After processing descendants, rollback(snap) to restore the parent version’s state
5. Output the answers for each query in order.

Complexity

• Time complexity: approximately \(O((N+Q)\log N)\) (considering find depth with union by size)
• Space complexity: \(O(N+Q)\) (DSU arrays, history, version tree)

Implementation Notes

• The interval \([L,R]\) must always be converted to the difference (L-1, R).

• Since mod calculations can become negative, normalize with (x % K + K) % K.

• For rollback history, it stabilizes the implementation to also push “operations that changed nothing” (in this code, b=-1).

• When type 0 results in a contradiction and outputs NO, the version’s content is the same as the parent’s. The DFS can proceed as-is (the state is preserved by rollback).

  Source Code

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

struct RollbackDSU {
    int n;
    long long K;
    vector<int> parent, sz;
    vector<long long> diff; // value[x] - value[parent[x]] mod K

    struct Hist {
        int b, old_parent_b, old_sz_a;
        long long old_diff_b;
    };
    vector<Hist> hist;

    RollbackDSU(int n_=0, long long K_=1): n(n_), K(K_) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        diff.assign(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);
    }

    pair<int,long long> findp(int x) {
        long long acc = 0;
        while (parent[x] != x) {
            acc += diff[x];
            acc %= K;
            x = parent[x];
        }
        return {x, acc}; // value[orig] - value[root]
    }

    int snapshot() const { return (int)hist.size(); }

    void rollback(int snap) {
        while ((int)hist.size() > snap) {
            auto h = hist.back(); hist.pop_back();
            if (h.b == -1) continue;
            int a = parent[h.b]; // currently parent of b is a
            parent[h.b] = h.old_parent_b;
            diff[h.b] = h.old_diff_b;
            sz[a] = h.old_sz_a;
        }
    }

    // enforce: val[y] - val[x] = w (mod K)
    bool unite(int x, int y, long long w) {
        auto [rx, vx] = findp(x); // val[x]-val[rx]
        auto [ry, vy] = findp(y); // val[y]-val[ry]
        w %= K; if (w < 0) w += K;

        if (rx == ry) {
            long long cur = (vy - vx) % K;
            if (cur < 0) cur += K;
            hist.push_back({-1,0,0,0});
            return cur == w;
        }

        // attach smaller to larger
        // need diff[rootChild] = val[rootChild] - val[rootParent]
        if (sz[rx] < sz[ry]) {
            // parent rx -> ry
            // from equation: (val[ry]+vy) - (val[rx]+vx) = w
            // val[rx] - val[ry] = vy - vx - w
            long long d = (vy - vx - w) % K;
            if (d < 0) d += K;

            hist.push_back({rx, parent[rx], sz[ry], diff[rx]});
            parent[rx] = ry;
            diff[rx] = d;
            sz[ry] += sz[rx];
        } else {
            // parent ry -> rx
            // val[ry] - val[rx] = w + vx - vy
            long long d = (w + vx - vy) % K;
            if (d < 0) d += K;

            hist.push_back({ry, parent[ry], sz[rx], diff[ry]});
            parent[ry] = rx;
            diff[ry] = d;
            sz[rx] += sz[ry];
        }
        return true;
    }

    // get val[y]-val[x] if connected
    pair<bool,long long> queryDiff(int x, int y) {
        auto [rx, vx] = findp(x);
        auto [ry, vy] = findp(y);
        if (rx != ry) return {false, 0};
        long long d = (vy - vx) % K;
        if (d < 0) d += K;
        return {true, d};
    }
};

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

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

    int N, Q;
    long long K;
    cin >> N >> K >> Q;

    vector<Query> qs(Q + 1);
    vector<vector<int>> children(Q + 1);

    for (int i = 1; i <= Q; i++) {
        int t; cin >> t;
        qs[i].type = t;
        if (t == 0) {
            int B, L, R; long long X;
            cin >> B >> L >> R >> X;
            qs[i] = {t, B, L, R, X};
            children[B].push_back(i);
        } else {
            int B, L, R;
            cin >> B >> L >> R;
            qs[i] = {t, B, L, R, 0};
            children[B].push_back(i);
        }
    }

    RollbackDSU dsu(N + 1, K);
    vector<string> ans(Q + 1);

    function<void(int)> dfs = [&](int v) {
        for (int u : children[v]) {
            int snap = dsu.snapshot();

            auto &qq = qs[u];
            int a = qq.L - 1;
            int b = qq.R;

            if (qq.type == 0) {
                bool ok = dsu.unite(a, b, qq.X);
                if (ok) {
                    ans[u] = "YES";
                    dfs(u);
                } else {
                    ans[u] = "NO";
                    // version u is same as version B => traverse children with base state (no added constraint)
                    dfs(u);
                }
            } else {
                auto [known, d] = dsu.queryDiff(a, b);
                if (known) ans[u] = to_string(d);
                else ans[u] = "UNKNOWN";
                dfs(u);
            }

            dsu.rollback(snap);
        }
    };

    dfs(0);

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

---

This editorial was generated by gpt-5.3-codex.