题解：SP23875 DCEPC14A - Another Version of Inversion

我们注意到这道题是二维的，所以要用到二维树状数组，不会的可以看一下这篇文章。

这题的思路和 P1908 很像，按价值从大到小排序，排完序之后用树状数组维护，每次把这个数的位置加入到树状数组中，因为是排完序之后，所以之前加入的一定比后加入的大，然后在查询当前这个数前面位置的数（是前面位置的数，要当前这个数减1），就是逆序对的个数了。

#include<bits/stdc++.h>
using namespace std;

const int maxx=325;

int N,M;
int a[maxx][maxx],ft[maxx][maxx];
vector<pair<int,pair<int,int>>> data;

void add(int x,int y){
    for(int i=x;i<maxx;i+=(i&-i)){
        for(int j=y;j<maxx;j+=(j&-j)){
            ft[i][j]++;
        }
    }
}
int get(int x,int y){
    int s=0;
    for(int i=x;i>0;i-=(i&-i)){
        for(int j=y;j>0;j-=(j&-j)){
            s+=ft[i][j];
        }
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin>>a[i][j];
            data.push_back(make_pair(a[i][j],make_pair(i,j)));
        }
    }
    sort(data.begin(),data.end());
    int result=0,added=0;
    for(auto i:data){
        int x=i.second.first,y=i.second.second;
        result+=added-get(x-1,maxx-1)-get(maxx-1,y-1)+get(x-1,y-1);
        add(i.second.first,i.second.second);
        added++;
    }
    cout<<result<<endl;
    return 0;
}