Overview

In this problem, information (queries) about interval sums of a hidden sequence \(A\) is given in a format where branching can occur from any past point (version). By interpreting interval sums as differences of prefix sums, the problem reduces to a “Weighted Union-Find” problem that manages relative relationships between elements. Furthermore, by using a “persistent data structure” to handle version branching, we can efficiently process queries while retaining past states.

Analysis

1. Relationship Between Interval Sums and Prefix Sums

The condition that the score of interval \([L, R]\) is \(X\) can be rewritten using the prefix sum \(S_i = (A_1 + \cdots + A_i) \bmod K\) (where \(S_0 = 0\)) as follows: $\(S_R - S_{L-1} \equiv X \pmod K\)\( In other words, this problem can be rephrased as managing the information that "the difference (relative value) between indices \)L-1\( and \)R\( is \)X$.”

2. Using Weighted Union-Find

Weighted Union-Find is well-suited for managing relative differences between elements. - For each element \(i\), we maintain the difference from its parent: \(weight[i] = S_i - S_{parent(i)} \pmod K\). - If two elements \(u, v\) belong to the same connected component, the difference \(S_v - S_u\) is uniquely determined. - If they belong to different connected components, the difference is undetermined (UNKNOWN).

3. Need for Persistence

The key feature of this problem is that operations are performed on “version \(B\),” creating a new version. This means we need to retain the entire history of the data structure and be able to branch from any past state. In a standard Union-Find, path compression and union by rank modify the internal state, so we construct a “persistent Union-Find” by managing the Union-Find arrays (parent, rank, weight) using a persistent segment tree.

Algorithm

1. Array Management via Persistent Segment Tree The information needed for Union-Find is stored in the leaves of a persistent segment tree.

   • par[i]: The parent of element \(i\)
   • rank[i]: The height of the tree (for optimization during union)
   • weight[i]: \(S_i - S_{par[i]} \pmod K\)

2. Find Operation In a persistent data structure, path compression would consume a large amount of memory, so we use only Union by Rank. This ensures the tree height is always \(O(\log N)\). By traversing parents while accumulating weight, we can compute the difference from the root.

3. Union Operation (Type 0 Query)

   • Find the roots \(r_1, r_2\) of \(L-1\) and \(R\) in version \(B\), along with their respective differences from the roots \(w_1, w_2\).
   • If \(r_1 = r_2\):
     • If \(w_2 - w_1 \equiv X \pmod K\), there is no contradiction, so output YES.
     • Otherwise, there is a contradiction, so output NO.
   • If \(r_1 \neq r_2\):
     • Accept this as new information and output YES.
     • Attach the root with smaller rank to the root with larger rank. At this point, compute and update the weight for the new parent appropriately.

4. Query Operation (Type 1 Query)

   • Check whether \(L-1\) and \(R\) belong to the same connected component in version \(B\).
   • If they do, output \((w_2 - w_1) \pmod K\) using the differences from the root.
   • If they don’t, output UNKNOWN.

Complexity

Let \(N\) be the length of the sequence and \(Q\) be the number of operations.

• Time Complexity: \(O(Q \log^2 N)\)
  • Per operation, segment tree lookups (\(O(\log N)\)) are performed for each step of traversing Union-Find parents (\(O(\log N)\)), resulting in \(O(\log^2 N)\) per query.
• Space Complexity: \(O(Q \log N)\)
  • Each update to the persistent segment tree creates \(O(\log N)\) new nodes.

Implementation Notes

• Memory Limit: The persistent segment tree can have a very large number of nodes, so the array size must be allocated sufficiently. In this implementation, approximately \(8 \times 10^6\) nodes are allocated.

• No Path Compression: In a persistent Union-Find, performing path compression would generate \(O(\log N)\) nodes per find call, putting pressure on memory. The standard approach is to use only union by rank (or size) to limit the height while keeping memory consumption low.

• Existence of \(S_0\): The sequence \(A\) ranges from \(1\) to \(N\), but to consider differences of prefix sums, we need to manage \(N+1\) elements from \(0 \dots N\) (including index \(0\)) in the Union-Find.

  Source Code

#include <iostream>
#include <utility>

using namespace std;

// Node structure for the persistent segment tree
// This segment tree stores the parent, rank, and weight for each index in the DSU
struct Node {
    int l, r;
    int par;
    int rank;
    int weight;
};

// Maximum number of nodes in the persistent segment tree
// Initial build: ~2 * (N+1) nodes
// Each update: ~log2(N+1) nodes
// Max updates per query: 2
// Total nodes: 2 * 2e5 + 1e5 * 2 * 18 approx 4e6. 
// Using 8e6 to be safe for 1024 MB memory limit.
const int MAX_NODES = 8000000;
Node tree[MAX_NODES];
int node_count = 0;

// Build the initial segment tree (version 0) where each node is its own parent
int build(int l, int r) {
    int node = ++node_count;
    if (l == r) {
        tree[node].par = l;
        tree[node].rank = 0;
        tree[node].weight = 0;
        tree[node].l = tree[node].r = 0;
        return node;
    }
    int mid = l + (r - l) / 2;
    tree[node].l = build(l, mid);
    tree[node].r = build(mid + 1, r);
    return node;
}

// Update a value in the persistent segment tree and return the new root
int update(int old_node, int l, int r, int idx, int new_par, int new_rank, int new_weight) {
    int node = ++node_count;
    tree[node] = tree[old_node];
    if (l == r) {
        tree[node].par = new_par;
        tree[node].rank = new_rank;
        tree[node].weight = new_weight;
        return node;
    }
    int mid = l + (r - l) / 2;
    if (idx <= mid) tree[node].l = update(tree[old_node].l, l, mid, idx, new_par, new_rank, new_weight);
    else tree[node].r = update(tree[old_node].r, mid + 1, r, idx, new_par, new_rank, new_weight);
    return node;
}

// Query a node's data from the persistent segment tree at a given index
Node query(int node, int l, int r, int idx) {
    if (l == r) return tree[node];
    int mid = l + (r - l) / 2;
    if (idx <= mid) return query(tree[node].l, l, mid, idx);
    else return query(tree[node].r, mid + 1, r, idx);
}

int N, Q;
long long K;

// Find the root of a component and the weight relative to it in the DSU
// weight is defined as S_i - S_root (mod K)
pair<int, long long> find_root(int root_idx, int i) {
    long long w = 0;
    int curr = i;
    while (true) {
        Node res = query(root_idx, 0, N, curr);
        if (res.par == curr) return {curr, w};
        w = (w + res.weight) % K;
        curr = res.par;
    }
}

int roots[100005];

int main() {
    // Optimize I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N >> K >> Q)) return 0;

    // Build the initial version 0 where no information is known
    roots[0] = build(0, N);

    for (int i = 1; i <= Q; ++i) {
        int type;
        cin >> type;
        if (type == 0) {
            int B, L, R;
            long long X;
            cin >> B >> L >> R >> X;
            // Check if the score of [L, R] is already determined in version B
            // Score of [L, R] is (S_R - S_{L-1}) mod K
            pair<int, long long> res1 = find_root(roots[B], L - 1);
            pair<int, long long> res2 = find_root(roots[B], R);
            if (res1.first == res2.first) {
                // Roots are the same, so the score is already fixed
                if ((res2.second - res1.second + K) % K == X) {
                    cout << "YES\n";
                    roots[i] = roots[B];
                } else {
                    cout << "NO\n";
                    roots[i] = roots[B];
                }
            } else {
                // Different components, the claim is consistent, so merge them
                cout << "YES\n";
                int root1 = res1.first;
                long long w1 = res1.second;
                int root2 = res2.first;
                long long w2 = res2.second;
                Node node1 = query(roots[B], 0, N, root1);
                Node node2 = query(roots[B], 0, N, root2);
                
                // Union by rank to maintain O(log N) depth
                if (node1.rank < node2.rank) {
                    // Make root2 the parent of root1
                    // weight[root1] = S_root1 - S_root2 = (w2 - w1 - X) mod K
                    roots[i] = update(roots[B], 0, N, root1, root2, node1.rank, (int)((w2 - w1 - X + 2LL * K) % K));
                } else if (node1.rank > node2.rank) {
                    // Make root1 the parent of root2
                    // weight[root2] = S_root2 - S_root1 = (X + w1 - w2) mod K
                    roots[i] = update(roots[B], 0, N, root2, root1, node2.rank, (int)((w1 - w2 + X + 2LL * K) % K));
                } else {
                    // Ranks are equal, merge and increment rank of the new root
                    int temp_root = update(roots[B], 0, N, root1, root2, node1.rank, (int)((w2 - w1 - X + 2LL * K) % K));
                    roots[i] = update(temp_root, 0, N, root2, root2, node2.rank + 1, 0);
                }
            }
        } else {
            int B, L, R;
            cin >> B >> L >> R;
            // Check if the score of [L, R] is uniquely determined in version B
            pair<int, long long> res1 = find_root(roots[B], L - 1);
            pair<int, long long> res2 = find_root(roots[B], R);
            if (res1.first == res2.first) {
                // Score is uniquely determined
                cout << (res2.second - res1.second + K) % K << "\n";
            } else {
                // Score is not fixed by the accepted claims
                cout << "UNKNOWN\n";
            }
            // Operation type 1 does not change the records, so version i is the same as version B
            roots[i] = roots[B];
        }
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.