这题看见没有用树状数组的，也没有对奇数码问题进行证明的，于是我就来补一发。

首先，对于一个矩阵，我们先来考虑左右移动对逆序对的贡献。

我们计算逆序对的时候不会算空格，所以左右移动不会对逆序对产生影响。

我们再来讨论一下上下移动对逆序对的贡献。

由于上下移动是一回事，所以我以向上移动来举例子。

x … x X x … x
x … x _ x … x

变成

x … x _ x … x
x … x X x … x

那么，逆序对就会有影响，影响的是我用粗体标注的东西。

x … x X x … x
x … x X x … x

因为一行的是奇数个格子，所以，我用黑体标注的数字的个数一定是偶数。

假设这些数字中有 $x$ 比 X 大，$y$ 个比 X 小，那么对逆序对的影响就是 $x-y$。

因为 X 走了后，这串数字中比 X 小的逆序对全部没了，所以会损失 $y$ 个；因为 X 来了后，这串数字中比 X 大的逆序对新增加了，所以会增加 $x$ 个。

又由于 $x+y$ 是偶数，所以 $x$ 和 $y$ 的奇偶性相同，所以 $x-y$ 为偶数。

综上所述，上下左右移动对逆序对的奇偶性没有影响。

证毕.

因此我们可以求逆序对判断是否有可行答案，我们就可以用树状数组来求教。

关于树状数组不会的同学，请看这里

我们可以建立值域树状数组，顾名思义就是对数的值域去建立树状数组，树状数组的下标就是值域。

由于这题很良心，所以我们不需要对值域离散化。

我们考虑把所有数字倒过来，问题就转化成了求左侧有多少个数字比它小。

这恰恰是我们树状数组能做的事情，我们对倒过来的数字从左往右扫，扫到一个数字就在这个数字作为下标的地方+1，打上标记，做差分，然后查询就直接求前缀和就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
int a[250010],b[250010],n;
struct WXQ_AK_IOI{
    bool t[250010];
    int lowbit(int x){return x&(-x);}
    void add(int x){for(int i=x;i<=n*n;i+=lowbit(i))t[i]^=1;}
    bool query(int x){int ans=0;for(int i=x;i;i-=lowbit(i))ans^=t[i];return ans;}
}T[2];
int main(){
    while(cin>>n){
        for(int i=1;i<=n*n;i++)read(a[i]),T[0].t[i]=0;
        for(int i=1;i<=n*n;i++)read(b[i]),T[1].t[i]=0;
        bool ans1=0,ans2=0;
        for(int i=n*n;i>=1;i--){
            if(a[i]!=0){ans1^=T[0].query(a[i]-1);T[0].add(a[i]);}
            if(b[i]!=0){ans2^=T[1].query(b[i]-1);T[1].add(b[i]);}
        }
        if(ans1==ans2)puts("TAK");
        else puts("NIE");
    }
    return 0;
}

我的代码里没有一个地方用到了 $\texttt{long long}$，那是因为我们求的只和逆序对值的奇偶性有关，所以我们不需要关注它的值到底是多少，只需要知道它 $\bmod\ 2$ 的余数是多少，这里我用了位运算。