概要

隠された数列の区間和 (mod \(K\)) に関する制約を木状に分岐する版で管理し、制約の整合性判定と値の一意決定を行う問題。重み付き Union-Find（ポテンシャル付き DSU）とロールバック機能を組み合わせて解く。

考察

累積和への帰着

\(S_0 = 0,\ S_i = (A_1 + A_2 + \cdots + A_i) \bmod K\) と定義すると、区間 \([L, R]\) のスコアは：

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

つまり「区間 \([L, R]\) のスコアが \(X\)」という主張は、\(S_R - S_{L-1} \equiv X \pmod{K}\) という 2 ノード間の差の制約に変換できます。

重み付き Union-Find

このような「2 変数間の差の制約」を管理するのに最適なのが重み付き（ポテンシャル付き）Union-Find です。ノード \(0, 1, \ldots, N\)（累積和のインデックス）を持ち、同じ連結成分内の 2 ノード間ではポテンシャル差が一意に定まります。

• 種類 0（受理判定）: \(S_{L-1}\) と \(S_R\) を差 \(X\) で unite する。既に同じ成分内にいて差が矛盾すれば却下。
• 種類 1（値の問い合わせ）: \(S_{L-1}\) と \(S_R\) が同じ成分にあればポテンシャル差を返し、なければ UNKNOWN。

版の木構造とロールバック

版は木状に分岐します。各操作 \(i\) は版 \(B_i\) を親として新しい版 \(i\) を作ります。この木構造上で DFS を行い、ノードに入るとき unite を適用し、離れるときロールバック（元に戻す）します。

ロールバックを可能にするため、経路圧縮を使わず、union by rank のみを使います。unite 時に変更した par/rank/wt を記録しておき、戻るときに復元します。

アルゴリズム

1. 版の親子関係から木を構築する（版 \(B_i\) → 版 \(i\) の辺）。
2. 重み付き Union-Find（ロールバック対応）を用意する。ノード数は \(N+1\)。
3. 版の木を DFS で探索する：
   • 操作が種類 0：unite(L-1, R, X) を試みる。成功すれば YES、矛盾すれば NO（unite せず進む）。
   • 操作が種類 1：find(L-1) と find(R) の根が同じならポテンシャル差を出力、異なれば UNKNOWN。
   • DFS で子をすべて処理し終わったら、この操作で追加した unite をロールバックする。

計算量

• 時間計算量: \(O(Q \log N)\)
  • 経路圧縮なし・union by rank ありの find は \(O(\log N)\)
  • 各操作で find を定数回呼ぶ
• 空間計算量: \(O(N + Q)\)
  • DSU に \(O(N)\)、版の木とロールバック履歴に \(O(Q)\)

実装のポイント

• 経路圧縮を使わないこと。ロールバックと経路圧縮は両立が難しいため、union by rank のみで木の高さを \(O(\log N)\) に抑える。

• find は再帰ではなくループで根まで辿り、途中の重みを累積する。

• DFS を再帰で書くとスタックオーバーフローの恐れがあるため、反復的な DFS（スタック使用） で実装する。スタックトップの参照を使い、子を順に処理する。

• 種類 0 で却下された場合も版は生成される（親版と同じ内容）ため、ロールバック量を 0 として記録する。

• mod \(K\) の計算で負の数が出ないよう ((x % K) + K) % K のパターンを使う。

  ソースコード

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

この解説は claude4.6opus-thinking によって生成されました。