仪征网站建设seo引擎优化外包公司

题意：

首先一行是T组数据，每组数据第一行是N,M,K，N代表左侧点的数量，M代表右侧点的数量，K代表有K条连线

次下K行有两个值X，Y代表左边第X和右边第Y个点相连。

问这些连线最多有几个交点。（同起点的线不相交）

思路：

显然，无论插入线段的顺序是怎么样的，交点的个数都不会改变

根据左边从小到大排序，求右边的逆序数就行

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1000000;
typedef struct Node{int x;int y;bool operator < (const Node &a)const{if(a.x==x)return a.y>y;return a.x>x;}
}Node;
int b[MAXN];
Node a[MAXN];
int lowbit(int x){return x&(-x);
}
void modify(int x,int add){while(x<=MAXN){b[x]+=add;x+=lowbit(x);}
}
int get_sum(int x){int ret=0;while(x!=0){ret+=b[x];x-=lowbit(x);}return ret;
}
int main()
{//ios::sync_with_stdio(false);int T;scanf("%d",&T);for(int ppp=1;ppp<=T;ppp++){int x,y,k;scanf("%d%d%d",&x,&y,&k);int n=max(x,y);long long ans=0;memset(b,0,sizeof(b));for(int i=0;i<k;i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a,a+k);for(int i=0;i<k;i++){modify(a[i].y,1);ans+=get_sum(n)-get_sum(a[i].y);}printf("Test case %d: %lld\n",ppp,ans);}
}

1
3 4 4
1 4
2 3
3 2
3 1

Test case 1: 5