https://codeforces.ml/contest/1546/problem/C

题意：
Meaning:
给定一个无序数组，可以任意交换相邻两数的位置，要求最终数组有序并且每个数被交换次数为偶数。问是否能达到要求达到要求，输出yes or no
Given an unordered array, the positions of two adjacent numbers can be exchanged arbitrarily. The final array is required to be ordered and the number of times each number is exchanged is even. Ask whether it can meet the requirements, output yes or no
思路：
假设一个数的位置在7，最终位置在5，那么这个数在数组有序时交换次数必为2+2k，为偶数。但如样例，有些数吧，它会重复，可能位置在3，4的数最终位置在1，2，那么你可以让两个数交换次数都是奇数也可以都是偶数。位置1，3要到8，10去，那就交换次数都是偶数了。但是还在数的位置最多只有1e5个，所以我的做法是，复制一个a数组，排序，我们就知道每个数最终的位置。
Suppose that the position of a number is 7 and the final position is 5, then when the array is ordered, the number of exchanges must be 2 + 2K, which is even. But for example, some numbers will be repeated, maybe the numbers in position 3 and 4 will eventually be in position 1 and 2. Then you can make both numbers exchange odd or even. Position 1, 3 to 8, 10, then the number of exchanges are even. However, there are only 1E5 positions at most, so my method is to copy an a array and sort it, so we can know the final position of each number.
同样举例说明，排序后的数组为1，1，2，3，那么我回到原数组，1的位置有：1，2。2的位置有3。3的位置有4。这意味着我可以在原数组中遍历，如果遇到1，我就看看有没有它可以通过偶数次交换可以去到的位置，如果有，那就换过去，把这个位置删掉，没有的话，输出no结束。
For the same example, the sorted array is 1, 1, 2, 3. Then I go back to the original array. The position of 1 is: 1, 2. The position of two is three. The position of three is four. This means that I can traverse the original array. If I encounter 1, I will see if there is a position it can go to through even number of exchanges. If there is, I will switch to it and delete the position. If not, I will output No.
比赛的时候我是这样遍历的，开的vector，过了，现在想想，如果分奇偶位置的话复杂度会更低，具体可以看代码。
During the competition, I traversed like this, opened the vector, passed, now think about it, if divided into odd and even positions, the complexity will be lower, see the code for details.

Code：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int t, n, odd[N], even[N];

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        vector<int> a(n), b(n);
        for(int i = 0; i < n; i ++) cin >> a[i], b[i] = a[i];
        sort(b.begin(), b.end());

        memset(odd, 0, sizeof odd);
        memset(even, 0, sizeof even);
        for(int i = 0; i < n; i += 2) even[b[i]] ++;
        for(int i = 1; i < n; i += 2) odd[b[i]] ++;

        bool flag = true;
        for(int i = 0; flag && i < n; i ++)
            if(i & 1 && odd[a[i]]) odd[a[i]] --;
            else if (!(i & 1) && even[a[i]]) even[a[i]] --;
            else flag = false;

        if(flag) cout << "YES\n"; else cout << "NO\n";
    }
}