树状数组
求逆序数。我们先把所有的道路按照X升序，X相同时Y升序的方法排列。这样从头至尾便利，对于每条道路，我们只需要知道它之前有多少道路的Y大于它的Y就 可以了，所以我们只要知道前面有多少Y小于等于它的再用下标减去就可以了。
#include <cstdio> #include <iostream> #include <string.h> #include <algorithm> using namespace std; typedef long long ll; int c[1000010],k,m; struct edge{ int x,y; }l[1000010]; int lowbit(int x){return x&(-x);} ll sum(int b){ ll sum=0; while(b>0){ sum+=c[b]; b-=lowbit(b); } return sum; } void add(int x){ while(x<=m){ ++c[x]; x+=lowbit(x); } } bool cmp(edge a,edge b){ return a.x==b.x?a.y<b.y:a.x<b.x; } int main(){ int n,t; scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d%d%d",&n,&m,&k); for(int j=1;j<=k;++j){ scanf("%d%d",&l[j].x,&l[j].y); } memset(c,0,sizeof(c)); sort(l+1,l+k+1,cmp); ll sum1=0; //不用longlong会爆 for(int j=1;j<=k;++j){ sum1+=j-1-sum(l[j].y); //因为下表从1开始，所以在减1 add(l[j].y); } printf("Test case %d: %lld ",i,sum1); } return 0; }