この問題は、 永続 segment tree を用いることで正答できます。

永続 segment tree 自体の説明は、先日オープンした AtCoder Algorithm Lectures 中に存在するため、そちらをお読みください。

数列そのものを保持するのではなく、代わりに永続 segment tree のある時点での根を保持します。
数列 \(A_i\) に対応する根を \(R_i\) とすると、各タイプのクエリは以下に対応します。

• タイプ \(1\) : \(R_{X_i}\) を \(R_{Y_i}\) で置き換える。時間計算量は \(O(1)\) である。
• タイプ \(2\) : \(R_{X_i}\) が対応する時点の segment tree に対し、一点更新を行う。時間計算量は \(O(\log N)\) である。
• タイプ \(3\) : \(R_{X_i}\) が対応する時点の segment tree に対し、区間演算を行う。時間計算量は \(O(\log N)\) である。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

// https://ei1333.github.io/library/structure/segment-tree/persistent-segment-tree.hpp.html
template <typename Monoid>
struct PersistentSegmentTree {
  using S = typename Monoid::S;
  struct Node {
    S d;
    Node *l, *r;
  };
  using NP = Node*;

 private:
  int n{};
  Monoid m;

  NP merge(NP l, NP r) const { return new Node{m.op(l->d, r->d), l, r}; }

  NP build(int l, int r, const vector<S>& v) const {
    if (l + 1 == r) return new Node{v[l], nullptr, nullptr};
    NP lp = build(l, (l + r) / 2, v);
    NP rp = build((l + r) / 2, r, v);
    return merge(lp, rp);
  }

  NP set(int a, const S& x, NP k, int l, int r) const {
    if (r <= a || a + 1 <= l) {
      return k;
    } else if (a <= l && r <= a + 1) {
      return new Node{x, nullptr, nullptr};
    } else {
      return merge(set(a, x, k->l, l, (l + r) >> 1),
                   set(a, x, k->r, (l + r) >> 1, r));
    }
  }

  NP apply(int a, const S& x, NP k, int l, int r) const {
    if (r <= a || a + 1 <= l) {
      return k;
    } else if (a <= l && r <= a + 1) {
      return new Node{m.op(k->d, x), nullptr, nullptr};
    } else {
      return merge(apply(a, x, k->l, l, (l + r) >> 1),
                   apply(a, x, k->r, (l + r) >> 1, r));
    }
  }

  S prod(int a, int b, NP k, int l, int r) const {
    if (r <= a || b <= l) {
      return m.e();
    } else if (a <= l && r <= b) {
      return k->d;
    } else {
      return m.op(prod(a, b, k->l, l, (l + r) >> 1),
                  prod(a, b, k->r, (l + r) >> 1, r));
    }
  }

 public:
  PersistentSegmentTree() = default;

  explicit PersistentSegmentTree(Monoid m, int n) : m(m), n(n) {}

  NP build(const vector<S>& v) const {
    assert(n == (int)v.size());
    return build(0, n, v);
  }

  NP set(NP t, int k, const S& x) const { return set(k, x, t, 0, n); }

  S get(NP t, int k) const {
    int l = 0, r = n;
    while (l + 1 < r) {
      int p = (l + r) / 2;
      if (k < p) {
        t = t->l;
        r = p;
      } else {
        t = t->r;
        l = p;
      }
    }
    return t->d;
  }

  NP apply(NP t, int k, const S& x) const { return apply(k, x, t, 0, n); }

  S prod(NP t, int a, int b) const { return prod(a, b, t, 0, n); }

  S all_prod(NP t) const { return t->d; }
};

using ll=long long;

struct Mnd {
  using S = ll;
  static constexpr S op(const S& a, const S& b) { return (a+b); }
  static constexpr S e() { return 0; }
};

int main(){
  ll n,m,q;
  cin >> n >> m >> q;
  PersistentSegmentTree pseg(Mnd(),m);
  vector<ll> ini(m,0);
  auto iseg=pseg.build(ini);
  vector< decltype(pseg)::NP > root(n,iseg);

  vector<ll> res;
  while(q--){
    ll typ;
    cin >> typ;
    if(typ==1){
      ll x,y;
      cin >> x >> y;
      x--; y--;
      root[x]=root[y];
    }
    else if(typ==2){
      ll x,y,z;
      cin >> x >> y >> z;
      x--; y--;
      root[x]=pseg.set(root[x],y,z);
    }
    else{
      ll x,l,r;
      cin >> x >> l >> r;
      x--; l--;
      res.push_back(pseg.prod(root[x],l,r));
    }
  }
  for(auto &nx : res){
    cout << nx << "\n";
  }
  return 0;
}