【CodeForces】1585D Yet Another Sorting Problem题解

题目大意

给定一个 $n$ 个数的数组 $a$（$1 \le n, a_i \le 10^5$）。

每次可以选择三个下标 $i, j, k$（$1 \le i, j, k \le n$），将 $a_i$ 移到 $a_j$ 原来的位置，$a_j$ 移到 $a_k$ 原来的位置，$a_k$ 移到 $a_i$ 原来的位置（三元循环移动）。

问是否可以通过这种方式使得数组变成升序有序数组？

题目地址

思路

首先需要知道这么一个规律：交换一个序列中两个不同的数会使这个序列的逆序对数改变奇数个。

而题目的这种操作就像连续进行两次交换（交换 $a_i, a_j$，再交换 $a_j, a_k$），所以每次操作使逆序对数改变偶数个，也就是每次操作不改变逆序对数的奇偶性。

所以，只要原序列的逆序对数是偶数，那么肯定可以做到。

当然还有一种特殊情况：

有两个相同的数，那么我们可以把这两个数作为媒介，可以等价于随意交换任意两个数，所以此时无论如何都能交换成功。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxN = 5e5 + 7;

int T, n, a[maxN], b[maxN], c[maxN];

bool cmp(int x, int y)
{
    return x < y;
}

inline void Add(int x, int k)
{
    for(; x <= n; x += x&(-x))
        c[x] += k;
}

inline int GetSum(int x)
{
    int ans = 0;
    for(; x; x -= x&(-x))
        ans += c[x];
    return ans;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(a + 1, a + 1 + n, cmp);
        int cnt = 0; bool mul = false;
        for(int i = 1; i <= n; ++i)
            if(a[i] == a[i - 1]) { //判断是否有重复
                mul = true;
                break;
            }
        if(mul)
            printf("YES\n");
        else  {
            int num = 0;
            memset(c, 0, sizeof c);
            for(int i = n; i > 0; i--) {
                num += GetSum(b[i] - 1);
                Add(b[i], 1);
            }
            if(num & 1)
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
    return 0;
}