暴力代码

record目前是第二优解 卡常后可以变成最优解

int v[(int)1e6 + 5], ops[(int)1e6 + 5][3];
int find(int idx, int base) {
  if (base == 0)
    return v[idx];
  else if (ops[base][1] == idx)
    return ops[base][2];
  else
    return find(idx, ops[base][0]);
}
signed main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> v[i];
  for (int i = 1; i <= m; ++i) {
    int v, op, p;
    cin >> v >> op >> p;
    p--;
    if (op == 1) {
      int c;
      cin >> c;
      ops[i][0] = v;
      ops[i][1] = p;
      ops[i][2] = c;
    } else {
      ops[i][0] = v;
      ops[i][1] = p;
      ops[i][2] = find(p, v);
      cout << ops[i][2] << endl;
    }
  }
  return 0;
}

如何卡掉

由题意，取$n=m$

前$n/2$次基于上一个版本更改

后$n/2$次查询第$n/2$个版本没有被更改的位置

则取到最坏时间复杂度$O(n^2)$

如何改进

取块长为$B$，到这个长度就memcpy上一层的再修改$B$个

常数和memcpy等有关，估计常数较小，不好卡掉

取$B = O(\sqrt n)$，则复杂度为$O(n\sqrt n)$

或许哪个分块题用过 不记得了

PS.我用的可持久化Trie做法

我写的不够卡常 但还是在$O(n\log n)$算法中速度最快

2叉树 1.56s

4叉树 939ms