树状数组求相交公路_POJ3067
传送门:POJ3067
题意:日本岛东海岸与西海岸分别有N和M个城市,现在修高速公路连接东西海岸的城市,求交点个数。
这题也是类似于求逆序对。
做法:记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时,满足(x1-x2)*(y1-y2) < 0。所以,将每条路按x从小到达排序,若x相同,按y从小到大排序。 然后按排序后的公路用树状数组在线更新,求y的逆序数之 和 即为交点个数。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define inff 1LL<<60
#define mem(x) memset(x,0,sizeof(x))
#define LL long long
#define maxn 1000100
int K,n,m;;
LL c[1100];
struct line
{
int s,e;
}s[maxn];
bool cmp(line a,line b){
if(a.s!=b.s) return a.s<b.s;
else return a.e<b.e;
}
int lowbit(int x){
return x&(-x);
}
void update(int x){
for(;x<=m;c[x]+=1,x+=lowbit(x));
}
int sum(int x){
int t=0;
for(;x>0;t+=c[x],x-=lowbit(x));
return t;
}
int main(int argc, char const *argv[])
{
int t;
cin>>t;
for(int k=1;k<=t;k++){
LL ans=0;
mem(c);
scanf("%d%d%d",&n,&m,&K);
for (int i = 1; i <= K; ++i)
{
scanf("%d%d",&s[i].s,&s[i].e);
}
sort(s+1,s+K+1,cmp);
for(int i=1;i<=K;i++){
ans+=sum(m)-sum(s[i].e);
update(s[i].e);
}
cout<<"Test case "<<k<<": "<<ans<<endl;
}
return 0;
}