「POJ 2893」M × N Puzzle

题目大意：判断 $n \times m$ 的八数码问题是否有解。$n, m < 1000$

横向交换时逆序对数不变，纵向交换相当于将区间 $[l,r]$ 循环右移一位，因此当 $m$ 为奇数时，纵向交换一次逆序对数奇偶性不变，$m$ 为偶数时，纵向交换一次逆序对数奇偶性取反。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int N = 1000000;
int a[N], b[N], cnt;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int lowbit(int x) {
    return x & (-x);
}
void update(int x) {
    while (x <= cnt) ++b[x], x += lowbit(x);
}
int query(int x) {
    int res = 0;
    while (x) res += b[x], x -= lowbit(x);
    return res;
}

int main() {
    while (1) {
        int n = read(), m = read(), k;
        if (!n) break;
        cnt = 0;
        memset(b, 0, sizeof b);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                int x = read();
                if (x) a[++cnt] = x;
                else k = i;
            }
        LL ans = 0;
        for (int i = cnt; i >= 1; --i) {
            ans += query(a[i] - 1);
            update(a[i]);
        }
        if (m & 1) {
            if (ans & 1) puts("NO");
            else puts("YES");
        } else {
            if ((ans + m - k) & 1) puts("NO"); //空格从初始位置移到目标位置后, 逆序对数奇偶性取反m-k次
            else puts("YES");
        }
    }
    return 0;
}