本文共 1114 字，大约阅读时间需要 3 分钟。
题意：
日本东海岸有N个城市（从北到南命名为1, 2, ..., N），西海岸有M个城市（从北到南命名为1, 2, ..., M），东西之间有K条高速公路，问这K条高速公路有多少个交叉点（一个交叉点有且只有两条高速公路经过）（1000 <= N, M <= 1000）。
题解：
记每条高速公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时，满足（x1-x2）*（y1-y2） < 0。所以，将每条路按x从小到达排序，若x相同，按y从小到大排序。 然后按排序后的公路用树状数组在线更新，求y的逆序数之 和 即为交点个数。
题目没给k的范围，没给T的范围......
自己试了一下这个题数组开到1e6就过了，1e5还不行，最后的结果需要开long long
#include #include #include #include #define maxn 400010#define pr printfusing namespace std;#define ll long long#define pr pair #define maxn 1000000pr a[maxn];int c[maxn];int n,m,k;bool cmp(pr x,pr y){ if(x.first==y.first) return x.second 0) { s+=c[i]; i-=lowbit(i); } return s;}int main(){ //freopen("input.txt","r",stdin); int T; scanf("%d",&T); for(int cas=1;cas<=T;++cas) { for(int i=0;i<=maxn;++i) c[i]=0; //memset(c,0,sizeof(c)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=k;++i) scanf("%d%d",&a[i].first,&a[i].second); sort(a+1,a+1+k,cmp); ll ans=0; for(int i=1;i<=k;++i) { add(a[i].second,1);//有点的地方就是1,没点的地方就是0 ans+=i-sum(a[i].second); } printf("Test case %d: %lld\n",cas,ans); } return 0;}
转载地址：http://wzfgf.baihongyu.com/