Overview

A problem where constraints on interval sums (mod \(K\)) of a hidden sequence are managed across versions that branch in a tree structure, requiring consistency checking of constraints and unique determination of values. Solved by combining a weighted Union-Find (DSU with potentials) with rollback functionality.

Analysis

Reduction to Prefix Sums

Define \(S_0 = 0,\ S_i = (A_1 + A_2 + \cdots + A_i) \bmod K\). Then the score of interval \([L, R]\) is:

\[ (A_L + \cdots + A_R) \bmod K = (S_R - S_{L-1}) \bmod K \]

In other words, the claim “the score of interval \([L, R]\) is \(X\)” can be transformed into a constraint on the difference between two nodes: \(S_R - S_{L-1} \equiv X \pmod{K}\).

Weighted Union-Find

The optimal data structure for managing such “difference constraints between two variables” is a weighted (potential-based) Union-Find. It has nodes \(0, 1, \ldots, N\) (prefix sum indices), and within the same connected component, the potential difference between any two nodes is uniquely determined.

• Type 0 (acceptance check): Unite \(S_{L-1}\) and \(S_R\) with difference \(X\). If they are already in the same component and the difference is contradictory, reject.
• Type 1 (value query): If \(S_{L-1}\) and \(S_R\) are in the same component, return the potential difference; otherwise, UNKNOWN.

Tree Structure of Versions and Rollback

Versions branch in a tree structure. Each operation \(i\) creates a new version \(i\) with version \(B_i\) as its parent. We perform DFS on this tree structure, applying unite when entering a node and rolling back (undoing) when leaving.

To enable rollback, we do not use path compression and only use union by rank. We record the par/rank/wt that were modified during unite, and restore them when backtracking.

Algorithm

1. Build a tree from the parent-child relationships of versions (edge from version \(B_i\) → version \(i\)).
2. Prepare a weighted Union-Find (with rollback support). The number of nodes is \(N+1\).
3. Explore the version tree with DFS:
   • Type 0 operation: Attempt unite(L-1, R, X). If successful, output YES; if contradictory, output NO (proceed without uniting).
   • Type 1 operation: If find(L-1) and find(R) have the same root, output the potential difference; otherwise, output UNKNOWN.
   • After processing all children in DFS, rollback the unite added by this operation.

Complexity

• Time complexity: \(O(Q \log N)\)
  • find with no path compression and union by rank is \(O(\log N)\)
  • Each operation calls find a constant number of times
• Space complexity: \(O(N + Q)\)
  • \(O(N)\) for DSU, \(O(Q)\) for the version tree and rollback history

Implementation Notes

• Do not use path compression. Since rollback and path compression are difficult to combine, use only union by rank to keep the tree height at \(O(\log N)\).

• Implement find with a loop (not recursion) that traces to the root, accumulating weights along the way.

• Since writing DFS recursively may cause stack overflow, implement it with iterative DFS (using a stack). Use a reference to the stack top and process children sequentially.

• Even when a Type 0 operation is rejected, a version is still created (with the same content as the parent version), so record the rollback amount as 0.

• To avoid negative numbers in mod \(K\) calculations, use the pattern ((x % K) + K) % K.

  Source Code

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

struct DSU {
    vector<int> par, rnk;
    vector<long long> wt;
    long long K;
    vector<tuple<int,int,int,long long>> hist;
    
    DSU(int n, long long K) : par(n), rnk(n, 0), wt(n, 0), K(K) {
        iota(par.begin(), par.end(), 0);
    }
    
    pair<int, long long> find(int x) {
        long long w = 0;
        while (par[x] != x) {
            w = (w + wt[x]) % K;
            x = par[x];
        }
        return {x, w};
    }
    
    // returns number of history entries added, or -1 if inconsistent
    int unite(int a, int b, long long X) {
        auto [ra, wa] = find(a);
        auto [rb, wb] = find(b);
        if (ra == rb) {
            return ((wb - wa) % K + K) % K == X ? 0 : -1;
        }
        long long diff = ((X - wb + wa) % K + K) % K;
        if (rnk[ra] < rnk[rb]) {
            hist.push_back({ra, par[ra], rnk[ra], wt[ra]});
            par[ra] = rb;
            wt[ra] = (K - diff) % K;
            return 1;
        } else if (rnk[ra] > rnk[rb]) {
            hist.push_back({rb, par[rb], rnk[rb], wt[rb]});
            par[rb] = ra;
            wt[rb] = diff;
            return 1;
        } else {
            hist.push_back({rb, par[rb], rnk[rb], wt[rb]});
            hist.push_back({ra, par[ra], rnk[ra], wt[ra]});
            par[rb] = ra;
            wt[rb] = diff;
            rnk[ra]++;
            return 2;
        }
    }
    
    void rollback(int cnt) {
        for (int i = 0; i < cnt; i++) {
            auto [node, op, ork, ow] = hist.back();
            hist.pop_back();
            par[node] = op;
            rnk[node] = ork;
            wt[node] = ow;
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, Q;
    long long K;
    cin >> N >> K >> Q;
    
    vector<int> type(Q), B(Q), L(Q), R(Q);
    vector<long long> X(Q);
    vector<vector<int>> children(Q + 1); // version tree, root is version 0
    
    for(int i = 0; i < Q; i++){
        cin >> type[i] >> B[i] >> L[i] >> R[i];
        if(type[i] == 0) cin >> X[i];
        children[B[i]].push_back(i);
    }
    
    DSU dsu(N + 1, K);
    vector<string> ans(Q);
    
    // DFS on version tree
    // Stack: (version_index, child_iterator, rollback_count)
    // version 0 is special (no operation), versions 1..Q correspond to operations 0..Q-1
    // Actually: children of version j are operations i where B[i] = j, creating version i+1? No.
    // Version i (1-indexed in operations) is created by operation i. Let me use 0-indexed operations.
    // Operation i creates version i+1. Wait, re-read: "i-th operation creates version i"
    // So version 0 exists initially, operation 1 creates version 1, ..., operation Q creates version Q.
    // But 0-indexed in my arrays: operation index i (0-based) creates version i+1.
    // children[B[i]] has operation i, which creates version (i+1).
    
    // DFS iteratively
    stack<pair<int,int>> stk; // (child_list_owner, index_in_child_list)
    vector<int> rollback_cnt(Q, 0);
    
    // Start: process children of version 0
    stk.push({0, 0});
    
    while(!stk.empty()){
        auto &[v, idx] = stk.top();
        if(idx == (int)children[v].size()){
            // leaving: rollback if v is an operation (v >= 1 means operation v-1)
            stk.pop();
            if(v >= 1){
                int op = v - 1;
                dsu.rollback(rollback_cnt[op]);
            }
            continue;
        }
        int op = children[v][idx];
        idx++;
        int ver = op + 1; // new version created
        
        if(type[op] == 0){
            int res = dsu.unite(L[op] - 1, R[op], X[op]);
            if(res == -1){
                ans[op] = "NO";
                rollback_cnt[op] = 0;
            } else {
                ans[op] = "YES";
                rollback_cnt[op] = res;
            }
        } else {
            auto [ra, wa] = dsu.find(L[op] - 1);
            auto [rb, wb] = dsu.find(R[op]);
            if(ra == rb){
                long long val = ((wb - wa) % K + K) % K;
                ans[op] = to_string(val);
            } else {
                ans[op] = "UNKNOWN";
            }
            rollback_cnt[op] = 0;
        }
        
        stk.push({ver, 0});
    }
    
    for(int i = 0; i < Q; i++){
        cout << ans[i] << '\n';
    }
    
    return 0;
}

This editorial was generated by claude4.6opus-thinking.