Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 题意解析 + 两种解法（归并排序 + BIT）

Posted by 947186602 at 2020-09-17 11:16:49 on Problem 3067
```/**

M <= 1000, N <= 1000

(排序是为了更好算逆序数,固定住x，求y的逆序对，并不是说排了序就没有逆序对了，只是排序后无需考虑x只需看y)

Sample Input
1
3 4 4
1 4
2 3
3 2
3 1
Sample Output
Test case 1: 5

**/
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node
{
int x,y;
bool operator < (const Node& a) const
{
if(a.x == x)
return y < a.y;
else return x < a.x;
}
} node[1005 * 1005];
int a[1005 * 1005],c[1005 * 1005]; // K的范围
int N,M,K,T;
long long cnt; //

void merge_sort(int x[],int left,int right,int y[])
{
if(left < right) //大于等于不用管
{
int mid = left + (right - left) / 2;//好习惯，防溢出
//先对左右归并排序
merge_sort(x,left,mid,y);
merge_sort(x,mid+1,right,y);

//此时左右都已经排好序了，归并开销
int i = left,j = mid + 1,k = left;//左起点，右起点，临时存储起点
while(i <= mid && j <= right)
{
if(x[i] <= x[j])
{
y[k++] = x[i++];
}
else
{
y[k++] = x[j++];
cnt += mid - i + 1;//记录逆序对，相当于对右边每个值，计算左边有多少比它大的
}
}
//补上剩下的
while(i <= mid)
y[k++] = x[i++];
while(j <= right)
y[k++] = x[j++];
//临时工转正
for(i = left ; i <= right; i++)
{
x[i] = y[i];
}
}
}

void solve_by_sort() //454MS
{
for(int i = 0; i < K; ++i)
{
a[i] = node[i].y; //给归并的数组赋值
}
cnt = 0;// 重置逆序对数
merge_sort(a,0,K-1,c);
}

int BIT[1005 << 1];
while(n < 1005){
BIT[n] += v;
n += n&-n;
}
}

int sum(int n){  //区域求和
int res = 0;
while(n > 0){
res += BIT[n];
n -= n&-n;
}
return res;
}

void solve_by_BIT(){  //391MS
memset(BIT,0,sizeof(BIT));
cnt = 0;
for(int i = 0;i < K;++i){
cnt += i - sum(node[i].y); //加上j < i 的且aj > ai  sum(node[i].y) 代表j < i 且 aj <= ai 的数量
}
}

int main()
{
scanf("%d",&T);
for(int j = 1; j <= T; ++j)
{
scanf("%d%d%d",&N,&M,&K);
for(int i = 0; i < K; ++i)
{
scanf("%d%d",&node[i].x,&node[i].y);
}
sort(node,node+K);
//解法任选1种
//solve_by_sort();
solve_by_BIT();
printf("Test case %d: %lld\n",j,cnt);
}
return 0;
}
```

Followed by: