POJ 3067 Japan 【 树状数组 】

题意:左边有n个城市,右边有m个城市,现在修k条路,问会形成多少个交点

先按照x从小到大排,x相同的话,则按照y从小到大排,然后对于每一个y统计前面有多少个y比它大,它们就一定会相交

另外要用long long

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int a[maxn];
int c[maxn];//树状数组
int n,m,k; struct node{
int x,y;
}p[maxn]; int cmp(node n1,node n2){
if(n1.x != n2.x) return n1.x < n2.x;
return n1.y < n2.y;
} int lowbit(int x){ return x & (-x);} int sum(int x){
int ret =;
while(x > ){
ret+=c[x];x-=lowbit(x);
}
return ret;
} void add(int x,int d){
while(x < maxn){
c[x]+=d;x+=lowbit(x);
}
} int main(){
int T;
scanf("%d",&T);
int kase=;
while(T--){
scanf("%d %d %d",&n,&m,&k);
for(int i=;i<=k;i++) scanf("%d %d",&p[i].x,&p[i].y);
sort(p+,p+k+,cmp); memset(c,,sizeof(c));
LL ans=;
for(int i=;i<=k;i++){
add(p[i].y,);
ans += i- sum(p[i].y);
}
printf("Test case %d: %I64d\n",++kase,ans);
}
return ;
}
上一篇:Error creating bean with name xxxx,xxxx must be provided


下一篇:20145205 java语言实现数据结构实验一