CF2195B题解

对于一个位置 \(i\)，可以与 \(i\times 2\) 交换，\(i\times 2\) 可以和 \(i\times 2\times 2\) 交换，以此类推，只有每一个下标除去所有 \(2\) 因子后结果相同的下标集合可以互相交换位置，而且是任意的。枚举位置起点，标 \(vis\) 保证不会重复枚举集合，这样枚举的每一个集合中元素数量的总和不会超过 \(n\)。对于每个集合内部排序，时间复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>const int N = 2e5 + 1;using namespace std;int a[N], vis[N];int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {int n;cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i], vis[i] = 0;for (int i = 1; i * 2 <= n; ++i) {if (vis[i]) continue;vector<int> q;for (int j = i; j <= n; j *= 2) q.push_back(a[j]), vis[j] = 1;sort(q.begin(), q.end());for (int j = i, k = 0; j <= n; j *= 2, ++k) a[j] = q[k];}bool flag = true;for (int i = 1; i <= n; ++i) {if (a[i] != i) {flag = false;break;}}if (flag) cout << "YES" << '\n';else cout << "NO" << '\n';}return 0;
}