AT_abc470_d

jojo222 · 2026-08-08 22:27:45 · 题解

首先证明：变换两次一定会变成原来的数列。 :::success[证明] 假设变换数列 b 满足 a_{b_i}=i，那么要证明的就是 b_{a_i}=i。
我们来算 b_{a_{b_i}}，它的值是 b_i（把下标换掉）。
设 t=b_i，可以发现 b_{a_t}=t。这不就是要证明的式子吗？ ::: 根据这个性质，就可以把数列分成变换偶数次和奇数次两类（分别可以视为 a 和 b）。

• 在 a 交换两个数，由 b_{a_i}=i 可得，交换 b_{a_x} 和 b_{a_y}；
• 在 b 交换两个数，由 a_{b_i}=i 可得，交换 a_{b_x} 和 a_{b_y}。

  int n, q, op, x, y, a[55n], b[55n];
  bool f;
  signed main()
  {
  read(n, q), read(a, n);
  rep(i, 1, n) b[a[i]] = i;
  while(q--)
  {
      read(op);
      if(op == 1)
      {
          read(x, y);
          if(f) swap(a[b[x]], a[b[y]]), swap(b[x], b[y]);
          else swap(a[x], a[y]), swap(b[a[x]], b[a[y]]);
      }
      else f = !f;
  }
  if(f) rep(i, 1, n) write(b[i], ' ');
  else rep(i, 1, n) write(a[i], ' ');
  return 0;
  }