D. Yet Another Sorting Problem - 树状数组求逆序数

本文主要是介绍D. Yet Another Sorting Problem - 树状数组求逆序数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

选三个下标，如果能够将这三个下标换成排好序的数，那么一定是逆序数为2或者-2，所以对于整体来说，只要是逆序数个数为偶数就可以实现，其次，如果有两个相同的数存在，那么一定可以实现排序，每次都可以将两个相同的数放到正确的位置。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve() {int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i ++) cin >> a[i];vector<int> c(n + 1);auto add = [&](int k, int x) {for(int i = k; i <= n; i += i & -i) c[i] += x;};auto query = [&](int x) {int sum = 0;for(int i = x; i >= 1; i -= i & -i) sum += c[i];return sum;};map<int, int> m;int flag = 0;for(int i = 0; i < n; i ++) {m[a[i]] ++;if(m[a[i]] >= 2) flag = 1;}if(flag == 1) {cout << "YES\n";return ;}int ans = 0;for(int i = n - 1; i >= 0; i --) {ans += query(a[i] - 1);add(a[i], 1);}cout << ((ans % 2) ? "NO\n" : "YES\n");
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}

这篇关于D. Yet Another Sorting Problem - 树状数组求逆序数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---