POJ2893-M × N Puzzle【M*N数码问题】

思路：这题思路参考了网上大佬v5zsq 的思路，但我用的归并排序来求逆序对。

#include<set>
#include<map>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int a[maxn], temp[maxn];
int ans = 0;
void Merge(int l, int mid, int r)
{
    int i = l, j = mid +1, k = l;
    while(i <= mid && j <= r)
    {
        if(a[j] < a[i])
        {
            temp[k++] = a[j++];
            ans += mid - i + 1;
        }
        else
            temp[k++] = a[i++];
    }
    while(i <= mid)
        temp[k++] = a[i++];
    while(j <= r)
        temp[k++] = a[j++];
    for(int i = l; i <= r; ++i)
        a[i] = temp[i];
}
void Mergesort(int l, int r)
{
   if(l <r)
   {
       int mid = (l + r) >> 1;
       Mergesort(l, mid);
       Mergesort(mid + 1, r);
       Merge(l, mid, r);
   }
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m) && n + m)
    {
        int tmp, row, cnt = 1;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                scanf("%d", &tmp);
                if(tmp)
                    a[cnt++] = tmp;
                else
                    row = i;
            }
        }
        ans = 0;
        Mergesort(1, cnt - 1);
        bool flag = false;
        if(m&1)
        {
            if((ans&1) == 0)
                flag = true;
        }
        else
        {
            if((ans + n - row)&1)
                flag = true;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
        //printf("%d\n", ans);
    }
    return 0;
}