E 题题解（并查集 + set）

首先我们要观察根据下表差值交换和根据值的差值交换这两个操做的特性。

• 根据下标交换，任何值只要能交换到这个位置，那么就能通过这个位置为跳板跳到和这个位置下标差值为 k 的任何地方，也就是所以模 k 后值相同的点都能相互交换。
• 根据值交换，只能和自己值差值为 k 的进行交换。

根据上面两个特性，我们可以发现我们可以先对数值差距为 k 的建一个并查集，对于在一个并查集内的点他们能够到达的位置是互通的（只要是在并查集内的两个点，其中一个能到达则另一个也能到达）。所以我们可以在并查集根节点位置维护一个set，用于记录这个并查集内元素能到达到那些地方。

代码

#include<bits/stdc++.h>
using namespace std;   

const int N = 1e5 + 10, P = 13331 , M = 3e5 + 10, Mod = 1e9 + 7, INF = 0x3f3f3f3f;
const double eps = 1e-8;
  
/* #define x first
#define y second */
#define MAXN 99999999 
  
typedef unsigned long long ull; 
typedef long long ll; 
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll a[N], p[N], pos[N];
pll b[N];

int find(int x) 
{
   if(p[x] != x) p[x] = find(p[x]);
   return p[x];
}

void Solved()
{
   ll n, k;
   cin >> n >> k;
   
   map<int, int> mp;
   for(int i = 1; i <= n; i ++) {
      cin >> a[i];
      b[i] = {a[i], i};
      mp[a[i]] = i;
      p[i] = i;
   }

   //排序找到每个位置的目标位置 
   sort(b + 1, b + 1 + n);
   for(int i = 1; i <= n; i ++) pos[b[i].second] = i;
   
   vector<set<int>> f(n + 10);
   for(int i = 1; i <= n; i ++)
   {
      int t1 = b[i].first, t2 = b[i].second;
      //判断这个元素是否存在
      if(mp.count(t1 - k)) {
         int pa = find(mp[t1 - k]), pb = find(t2);
         p[pb] = pa;
         f[pa].insert(t2 % k); 
      }
      else f[t2].insert(t2 % k);
   }

   bool flag = true;
   for(int i = 1; i <= n; i ++) {
      int pa = find(i);
      if(!f[pa].count(pos[i] % k)) 
        flag = false;
   }

   if(flag) cout << "Yes" << "\n";
   else cout << "No" << "\n";
}
   
int main()
{   
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int t;
  //cin >> t;
  t = 1;
 
 
  while (t --)
  {
    Solved();
  }
  
  return 0;
}