树状数组的题
题意:日本东海岸和西海岸分别有n和m个城市,给出所有连接两个城市的道路,求所有道路的交叉点
做法:将东海岸的城市a进行升序排列,然后a相同的时候按照b升序排列。求出b的逆序数则是道路交叉点的数目
#include <cstdio> #include <string.h> #include <algorithm> #include <cstdlib> using namespace std; const int maxn=1010; int c[maxn]; struct line { int a,b; }way [maxn*maxn]; int n,m,k,t; int lowbit(int i) { return i&(-i); } void update(int i,int x) { while(i<=m) { c[i]+=x; i+=lowbit(i); } } int sum(int i) { int ans=0; while(i>0) { ans+=c[i]; i-=lowbit(i); } return ans; } bool cmp(line x,line y) { if(x.a==y.a) return x.b<y.b; return x.a<y.a; } int main() { scanf("%d",&t); for(int i=0;i<t;i++) { scanf("%d%d%d",&n,&m,&k); for(int j=1;j<=k;j++) { scanf("%d%d",&way[j].a,&way[j].b); } sort(way+1,way+1+k,cmp); memset(c,0,sizeof(c)); long long ans=0; for(int j=1;j<=k;j++) { ans=ans+sum(m)-sum(way[j].b);//求逆序数 update(way[j].b,1); } printf("Test case %d: %I64d\n",i+1,ans); } }