概要

この問題は、隠された数列 \(A\) の区間和に関する情報（クエリ）が、過去のどの時点（版）からでも分岐して与えられる形式です。区間和を累積和の差として捉えることで、要素間の相対的な関係を管理する「重み付きUnion-Find」の問題に帰着できます。さらに、版の分岐に対応するために「永続データ構造」を用いることで、過去の状態を保持したまま効率的にクエリを処理します。

考察

1. 区間和と累積和の関係

区間 \([L, R]\) のスコアが \(X\) であるという条件は、累積和 \(S_i = (A_1 + \cdots + A_i) \bmod K\) （ただし \(S_0 = 0\)）を用いると、以下のように書き換えられます。 $\(S_R - S_{L-1} \equiv X \pmod K\)\( つまり、この問題は「インデックス \)L-1\( と \)R\( の間の差（相対的な値）が \)X$ である」という情報を管理する問題と言い換えられます。

2. 重み付きUnion-Findの利用

要素間の相対的な差を管理するには、重み付きUnion-Findが適しています。 - 各要素 \(i\) について、親要素との差 \(weight[i] = S_i - S_{parent(i)} \pmod K\) を保持します。 - 2つの要素 \(u, v\) が同じ連結成分に属していれば、その間の差 \(S_v - S_u\) は一意に決まります。 - 異なる連結成分に属していれば、その間の差は決まりません（UNKNOWN）。

3. 永続化の必要性

本問題の最大の特徴は、操作が「版 \(B\)」に対して行われ、新しい版が作られるという点です。これは、データ構造の履歴をすべて保持し、任意の過去の状態から分岐できる必要があることを意味します。 通常のUnion-Findでは、経路圧縮やランクによる合体で内部状態が書き換わってしまうため、永続セグメントツリーを用いてUnion-Findの配列（parent, rank, weight）を管理する「永続Union-Find」を構築します。

アルゴリズム

1. 永続セグメントツリーによる配列の管理 Union-Findで必要な情報を、永続セグメントツリー上の葉に格納します。

   • par[i]: 要素 \(i\) の親
   • rank[i]: 木の高さ（合体時の最適化用）
   • weight[i]: \(S_i - S_{par[i]} \pmod K\)

2. Find操作 永続データ構造では経路圧縮を行うとメモリを大量に消費するため、ランクによる合体（Union by Rank）のみを使用します。これにより、木の高さは常に \(O(\log N)\) に保たれます。親を辿りながら weight を加算していくことで、根との差を計算できます。

3. Union操作（種類0のクエリ）

   • 版 \(B\) における \(L-1\) と \(R\) の根 \(r_1, r_2\) と、それぞれの根との差 \(w_1, w_2\) を求めます。
   • \(r_1 = r_2\) の場合：
     • \(w_2 - w_1 \equiv X \pmod K\) なら矛盾しないので YES。
     • そうでなければ矛盾するので NO。
   • \(r_1 \neq r_2\) の場合：
     • 新たな情報として受け入れ YES を出力。
     • ランクが小さい方の根を大きい方の根に繋ぎます。この際、新しい親との間の weight を適切に計算して更新します。

4. 判定操作（種類1のクエリ）

   • 版 \(B\) における \(L-1\) と \(R\) が同じ連結成分に属しているか確認します。
   • 同じであれば、根との差を利用して \((w_2 - w_1) \pmod K\) を出力します。
   • 異なれば UNKNOWN を出力します。

計算量

\(N\) を数列の長さ、\(Q\) を操作数とします。

• 時間計算量: \(O(Q \log^2 N)\)
  • 1回の操作につき、セグメントツリーの探索（\(O(\log N)\)）を、Union-Findの親を辿る回数（\(O(\log N)\)）だけ行うため、一回あたりのクエリは \(O(\log^2 N)\) となります。
• 空間計算量: \(O(Q \log N)\)
  • 永続セグメントツリーの更新ごとに \(O(\log N)\) 個のノードが新しく生成されます。

実装のポイント

• メモリ制限: 永続セグメントツリーはノード数が非常に多くなるため、配列のサイズを十分に確保する必要があります。この実装では約 \(8 \times 10^6\) ノードを確保しています。

• 経路圧縮の禁止: 永続Union-Findでは、経路圧縮を行うと1回の find で \(O(\log N)\) 個のノードが生成されてしまい、メモリを圧迫します。ランク（またはサイズ）による合体のみを用いることで、高さを制限しつつメモリ消費を抑えるのが定石です。

• \(S_0\) の存在: 数列 \(A\) は \(1\) から \(N\) までですが、累積和の差を考えるためにインデックス \(0\) を含めた \(0 \dots N\) の \(N+1\) 要素をUnion-Findで管理する必要があります。

  ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。