SPOJ：Another Version of Inversion（二维数组的逆序对）

DCE Coders admins are way much geekier than they actually seem! Kartik has been following that tradition lately. How? Well, he took the inversion count problem to a whole new level!

Sounds pretty normal to you, huh? Wanna challenge him? Try solving his version of inversion count then!

You are given a 2-d array of integers. You need to find out the inversion count of that array. A pair of integers in the 2-d array counts as an inversion pair (A,B) if and only if:

There exists a valid path from top-left corner (0,0) to bottom right corner (r,c) such that A and B integers lie on that path.
A occurs before B on that path.
And, A > B.

A valid path is defined as a path that can be traversed from top-left corner (0,0) to bottom-right corner (r,c) by moving only in right or downwards direction, without moving out of the grid.

Are you geekier than Kartik?

Constraints:

0 < R,C <= 300

0 < Ai <= 10^5, where Ai stands for an integer in the array.

Input

First line contains space separated 2 integers, R and C, denoting the number of rows and columns.

Next R lines contain C space separated integers representing the 2-d array

Output

Output the number of inversion pairs as described in the problem statement.

Example

Input:

4 4

3 4 2 5

1 7 11 16

8 9 6 12

10 13 15 14

Output:

题意：就是二维平面上，如果(i,j)左方，上方，左上方的数大于a[i][j]，则称其为一堆逆序对，求逆序数。

思路：因为自己之前写的数状数组求逆序对都是离散化然后倒序累加，这个方法在这里不适用。正确的打开方式是：按从大到小的顺序加入数状数组，然后统计比自己先加入（即比自己大或者等于），而且X坐标和Y坐标小于等于自己的数的个数（保证了反向）。同时注意处理大小相同的数！

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct in{
    int a,x,y;
}s[maxn*maxn];
bool cmp(in w,in v){
    if(w.a==v.a) {
        if(w.x==v.x) return w.y>v.y;
        return w.x>v.x; //这里保证了两个数相同的时候，在树状数组里没有包含关系。 
    }
    return w.a>v.a;
}
int sum[maxn][maxn],N,M;
void add(int x,int y){
    for(int i=x;i<=N;i+=(-i)&i)
     for(int j=y;j<=M;j+=(-j)&j)
      sum[i][j]++;
}
long long query(int x,int y){
    long long res=0;
    for(int i=x;i;i-=(-i)&i)
     for(int j=y;j;j-=(-j)&j)
      res+=sum[i][j];
    return res;
}
int main()
{
    int i,j,cnt=0; long long ans=0;
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)
      for(j=1;j<=M;j++){
       scanf("%d",&s[++cnt].a);
       s[cnt].x=i; s[cnt].y=j;
    }
    sort(s+1,s+cnt+1,cmp);
    for(i=1;i<=cnt;i++){
        ans+=query(s[i].x,s[i].y);
        add(s[i].x,s[i].y);
    }
    printf("%lld
",ans);
    return 0;
}

感谢Wxk给的思路！不然我一直用之前的方法做，几乎不会想出来。