D2. Seating Arrangements (hard version)

题意 我们要先按照a来排序 然后再来安排d的位置
最开始都能想到的一点就是我们可以每一组内按照逆序排序
我们就可以让组内是0贡献 但是对于不同行来说
这样真的是最优解吗
我们知道要是跨越了两行的同一组数 肯定是前面一行在后面部分
后面一行在前面部分 在前面部分的我们通过逆序 显然是超级小的
可能会造成更大的贡献 但是我们思考我们是不是可以让这前面部分换成大的
反正他和直接几行无关 所以我们组内贡献一定是0的同时还能最小化后面的贡献
而我们前面那一行的 最后部分当然也希望收到的是更小的数 这样子前后都是最小的
正确性显然
但是为了方便我们计算可以不按照组内正序一遍再每一行逆序一遍
我们知道组内贡献为0 我们直接不算组内即可
然后组外的 该小的数还是会算进去的 因为不在同一组 所以肯定排在后面

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 20220911;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int a[N],d[N];
bool cmp(int x,int y){
    if(a[x]==a[y])return x<y;
    return a[x]<a[y];
}//按a的大小将d排序
void solve() {
    int n,m;cin>>n>>m;
    for(int i=0;i<n*m;i++)cin>>a[i],d[i]=i;
    sort(d,d+n*m,cmp);
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=i*m;j<i*m+m;j++)
            for(int k=i*m;k<j;k++)
                if(a[d[j]]!=a[d[k]]&&d[j]>d[k])ans++;
    cout<<ans<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}