posts - 64, comments - 4, trackbacks - 0, articles - 0

poj3067Japan(树状数组求逆序对)

Posted on 2010-10-29 15:23 acronix 阅读(1796) 评论(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
;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理