Overview

We treat interval sum information as constraints on differences between prefix sums.
Since versions branch in a tree structure, we DFS over the version tree while managing constraints with a rollback-capable weighted Union-Find.

Analysis

The score of interval \([L,R]\) is

\[ (A_L + A_{L+1} + \cdots + A_R) \bmod K \]

Here, defining the prefix sum as

\[ P_i = (A_1 + A_2 + \cdots + A_i) \bmod K \]

the score of interval \([L,R]\) becomes

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

In other words, the claim

\[ \text{score}(L,R) = X \]

can be rephrased as the following difference constraint:

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

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

---

Viewing the constraints as a graph, each vertex corresponds to a prefix sum \(P_i\) for \(i = 0, 1, \dots, N\).

If two vertices \(u, v\) belong to the same connected component, then from the constraints so far,

\[ P_v - P_u \pmod K \]

is uniquely determined.

Conversely, if they belong to different connected components, the entire component can be freely shifted, so the difference is not uniquely determined. Therefore, the answer is UNKNOWN.

---

If we naively copy the constraint set or Union-Find for each version, since the number of versions can be up to \(Q\), the complexity becomes \(O(NQ)\) or similar, which is too slow.

The key insight is to view the versions created by operations as a tree.

Each operation \(i\) references an existing version \(B\) to create a new version \(i\), so by drawing an edge from version \(B\) to version \(i\), all versions form a tree rooted at version \(0\).

By DFS-ing over this tree:

• When going down the tree, add constraints
• When going back up the tree, undo the added constraints

we can efficiently reproduce the state corresponding to each version.

For this purpose, we use a rollback-capable weighted Union-Find.

Algorithm

First, read all operations and draw edges from the referenced version \(B\) to the current version \(i\) to build the version tree.

Each interval \([L,R]\) corresponds to prefix sum vertices

\[ a = L-1,\quad b = R \]

Type \(0\) operations check whether the constraint

\[ P_b - P_a \equiv X \pmod K \]

can be added.

Type \(1\) operations check whether

\[ P_b - P_a \pmod K \]

is uniquely determined.

---

In the weighted Union-Find, each vertex stores the difference to its parent.

find(v) returns, along with the root,

\[ P_v - P_{\mathrm{root}} \pmod K \]

Consider adding the constraint

\[ P_b - P_a \equiv X \pmod K \]

• If \(a\) and \(b\) are already in the same connected component:
  If the already determined difference matches \(X\), accept; otherwise it’s a contradiction, so reject.

• If \(a\) and \(b\) are in different connected components:
  The relative position of the two components is still free, so the constraint can always be added.
  Merge using Union-Find.

---

DFS over the version tree.

The state of the Union-Find just before entering version \(v\) is the state of the parent version.

Process the operation of version \(v\):

• For type \(0\):
  • If the constraint can be added: YES
  • If it contradicts: NO
• For type \(1\):
  • If both endpoints are in the same connected component, output the difference
  • Otherwise, output UNKNOWN

Then, proceed to child versions.

After the DFS finishes processing the entire subtree of version \(v\), rollback the Union-Find to the state before entering version \(v\).

---

For example, the constraint 0 B L R X becomes an operation on the Union-Find that adds the edge

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

The query 1 B L R checks whether vertices \(L-1\) and \(R\) are in the same connected component, and if so, outputs their difference.

Complexity

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

The Union-Find does not use path compression due to rollback, but since we merge by size, the height is bounded by \(O(\log N)\).

Implementation Notes

In a rollback-capable Union-Find, path compression must NOT be used.
This is because path compression rewrites many parent pointers, making it difficult to undo.

Instead, we keep the height low by merging the smaller tree into the larger tree.

When merging, we save in the history:

• Which root became a child
• Which root became the parent
• The size of the parent side before merging

When returning from the DFS, we use this history to restore the Union-Find to its original state.

In the code, we use an explicit stack instead of recursive DFS.
This is because \(Q\) can be as large as \(10^5\), and recursion might hit Python’s recursion limit.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K, Q = map(int, input().split())

    children = [[] for _ in range(Q + 1)]
    typ = [0] * (Q + 1)
    aa = [0] * (Q + 1)
    bb = [0] * (Q + 1)
    xx = [0] * (Q + 1)

    for i in range(1, Q + 1):
        q = list(map(int, input().split()))
        t = q[0]
        B = q[1]
        typ[i] = t
        children[B].append(i)
        if t == 0:
            _, _, L, R, X = q
            aa[i] = L - 1
            bb[i] = R
            xx[i] = X
        else:
            _, _, L, R = q
            aa[i] = L - 1
            bb[i] = R

    parent = list(range(N + 1))
    size = [1] * (N + 1)
    weight = [0] * (N + 1)
    history = []

    def find(v):
        s = 0
        while parent[v] != v:
            s += weight[v]
            if s >= K:
                s -= K
            v = parent[v]
        return v, s

    def unite(a, b, x):
        ra, pa = find(a)
        rb, pb = find(b)

        if ra == rb:
            d = pb - pa
            if d < 0:
                d += K
            return d == x

        if size[ra] < size[rb]:
            history.append((ra, rb, size[rb]))
            parent[ra] = rb
            weight[ra] = (pb - pa - x) % K
            size[rb] += size[ra]
        else:
            history.append((rb, ra, size[ra]))
            parent[rb] = ra
            weight[rb] = (x + pa - pb) % K
            size[ra] += size[rb]

        return True

    def rollback(snap):
        while len(history) > snap:
            child, par, old_size = history.pop()
            parent[child] = child
            weight[child] = 0
            size[par] = old_size

    ans = [""] * (Q + 1)
    stack = [(0, 0, 0)]

    while stack:
        v, state, snap = stack.pop()

        if state == 1:
            rollback(snap)
            continue

        snap = len(history)

        if v:
            a = aa[v]
            b = bb[v]

            if typ[v] == 0:
                if unite(a, b, xx[v]):
                    ans[v] = "YES"
                else:
                    ans[v] = "NO"
            else:
                ra, pa = find(a)
                rb, pb = find(b)
                if ra == rb:
                    d = pb - pa
                    if d < 0:
                        d += K
                    ans[v] = str(d)
                else:
                    ans[v] = "UNKNOWN"

        stack.append((v, 1, snap))
        for c in reversed(children[v]):
            stack.append((c, 0, 0))

    print("\n".join(ans[1:]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.