Posted on 2010-10-29 15:23
acronix 阅读(1821)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：自己看吧。
分析：对左边的点从小到大排序，相等则对右边的从小到大排，最后只要求左边的逆序对即可，求逆序对除了树状数组还有归并排序。
注意：边可以达到1000*1000，结果会超int。
cpp代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int maxn,n,m,k;
struct Point{
int x,y;
}a[1000010];
long long c[1005];
int Lowbit(int i)
{
return i&(-i);
}
long long up(int x)
{
int i = x;
long long res = 0;
while (i <= maxn)
{
res += c[i];
i += Lowbit(i);
}
return res;
}
void down(int x)
{
int i = x;
while (i > 0)
{
c[i]++;
i -= Lowbit(i);
}
}
bool cmp(const Point &a,const Point &b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
int t,cas = 1,i;
long long ans;
scanf("%d ", &t);
while (t--)
{
ans = 0;
scanf("%d %d %d",&n,&m,&k);
for (i = 1; i <= m; i++)
c[i] = 0;
maxn = m;
for (i = 1; i <= k; i++)
{
scanf("%d %d",&a[i].x, &a[i].y);
}
sort(a+1, a+1+k, cmp);
for (i = 1; i <= k; i++)
{
ans += up(a[i].y + 1);
down(a[i].y);
}
printf("Test case %d: %I64d\n",cas++, ans);
}
return 0;
}