Overview

The score of an interval \([L,R]\) can be expressed as a “difference between two points” using prefix sums.
We view each version as a tree, and manage constraints using a rollback-capable weighted Union-Find while performing DFS on the tree.

Analysis

First, consider prefix sums.

Let \(P_0 = 0\) and \(P_i = (A_1 + A_2 + \cdots + A_i) \bmod K\). Then the score of interval \([L,R]\) is

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

In other words, the claim

\[ \text{The score of interval } [L,R] \text{ is } X \]

becomes the following constraint:

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

This is a constraint of the form “the difference between vertex \(L-1\) and vertex \(R\) is \(X\).”

For example, when \(K=10\):

• The score of \([2,4]\) is \(3\)
  \(\Rightarrow P_4 - P_1 \equiv 3 \pmod{10}\)
• The score of \([1,1]\) is \(7\)
  \(\Rightarrow P_1 - P_0 \equiv 7 \pmod{10}\)

Then,

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

so the score of \([1,4]\) is uniquely determined to be \(0\).

In this way, the problem becomes “a problem of adding difference constraints and determining whether the difference between two points is uniquely determined.”

Difference constraints can be handled with a weighted Union-Find.

• When adding a constraint \(P_v - P_u = X\):
  • If \(u\) and \(v\) are in different connected components, there is no contradiction, so we merge them
  • If they are already in the same connected component, we check whether the already known difference matches \(X\)
• When querying \(P_v - P_u\):
  • If \(u\) and \(v\) are in the same connected component, the difference is uniquely determined
  • If they are in different components, we can shift one entire component, so it is not uniquely determined

If we naively copy the Union-Find for each version, each operation takes \(O(N)\), resulting in \(O(NQ)\) which is too slow.

Therefore, we focus on the structure of versions.

Operation \(i\) creates a new version \(i\) from an existing version \(B\).
In other words, if we treat versions as vertices and draw edges from the reference version \(B\) to \(i\), all versions form a tree rooted at version \(0\).

By performing DFS on this tree:

1. Apply the operation from the parent’s state
2. Process descendants
3. After processing is complete, restore the state before the operation

This way, we avoid copying the Union-Find.

To restore state, we use a rollback-capable weighted Union-Find.

Algorithm

Vertices correspond to prefix sums \(P_0, P_1, \ldots, P_N\), so we prepare \(N+1\) of them.

For an interval \([L,R]\) given in an operation, we set

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

and handle the difference constraint

\[ P_v - P_u \]

Weighted Union-Find

For each vertex \(x\), we maintain the weight to its parent as

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

find(x) returns the root along with

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

Consider adding the constraint

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

From find(u) we know

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

From find(v) we know

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

• Case \(r_u = r_v\):
  We already know that

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

If this matches \(w\), the constraint is accepted; otherwise, it is a contradiction.

• Case \(r_u \ne r_v\):
  We merge the two connected components.
  By appropriately setting the relative difference between the roots, the constraint can always be satisfied.

DFS on the Version Tree

First, read all operations and add operation number \(i\) to children[B].
This creates an edge from version \(B\) to version \(i\).

During DFS, the current Union-Find state represents “the state of the current version.”

For each child idx:

1. Save the current state for rollback
2. Apply operation idx
   • If type \(0\): determine whether the constraint can be added, output YES / NO
   • If type \(1\): determine whether the difference is known, output the value or UNKNOWN
3. Process descendants of version idx via DFS
4. Rollback to the saved state

If a type \(0\) operation results in a contradiction, that constraint is not added.
Therefore, that version has the same state as its reference version.
This is naturally represented by not modifying the Union-Find state.

Also, type \(1\) operations do not add constraints, so the state does not change.

Complexity

• Time complexity: \(O(N + Q \log N)\)
• Space complexity: \(O(N + Q)\)

In the weighted Union-Find, we do not use path compression for rollback purposes, and only use union by size.
Therefore, find is \(O(\log N)\).

Implementation Notes

• Interval \([L,R]\) is handled as the difference between vertices \(L-1\) and \(R\).

• All values are managed \(\bmod K\). If a value becomes negative, add \(K\) to normalize it.

• Path compression is not used in the Union-Find due to rollback requirements.

• During merging, pre-modification information is pushed onto the history stack:

  • Which root was made a child
  • The root of the merge target
  • The size of the merge target

• Before processing each child in DFS, take a snapshot(), and after processing, perform rollback().

• Since the DFS order may differ from the input order, answers are stored in an array and output in operation number order at the end.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.