CF 1619H. Permutation and Queries（分块）

CF 1619H. Permutation and Queries（分块）

传送门

显然形成了链环结构，然后每次改变只是重构断点处的链。

一开始想的是st表，但是不会修改 *** 作，然后想到了分块，修改时只要把受到影响的块重新处理就好，由于是链环的结构，可以直接使用双指针。

// Problem: H. Permutation and Queries
// Contest: Codeforces - Codeforces Round #762 (Div. 3)
// URL: https://codeforces.com/contest/1619/problem/H
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
using namespace std;

int main() {
  ios_base :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, q; cin >> n >> q;
  vector nex(n + 1, 0), pre(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> nex[i], pre[nex[i]] = i;
  }
  const int block = sqrt(n) + 1;
  vector jump(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    jump[i] = i;
    for (int j = 1; j <= block; j++) {
      jump[i] = nex[jump[i]];
    }
  }
  auto change = [&](const int x) {
    int to = x;
    for (int i = 1; i <= block; i++) {
      to = nex[to];
    }
    for (int i = 1, from = x; i <= block; i++) {
      jump[from] = to;
      from = pre[from], to = pre[to];
    }
  };
  for (int op, x, y; q--; ) {
    cin >> op >> x >> y;
    if (op == 1) {
      swap(nex[x], nex[y]);
      pre[nex[x]] = x, pre[nex[y]] = y;
      change(x), change(y);
    } else {
      int ans = x;
      for (; y >= block; y -= block) ans = jump[ans];
      for (; y; y--) ans = nex[ans];

      cout << ans;
      if (q) cout << 'n';
    }
  }
  return 0;
}