这道题从看到它开始到做出来，已经过了快两周【因为第一次思路完全跑偏写的是暴力模拟想水过】；
题意是这样的：
jzabc除了对多米诺骨牌感兴趣外，对赛车也很感兴趣。上个周末他观看了一场赛车比赛。他总是能想出许多稀奇的问题。某一时刻，他看到有n辆车（总是匀速行驶）在同一直线上，并且处在一个无限长度的直道上，而且n辆车有严格的先后之分。他通过特殊的器材测出了每一辆车的速度。那么问题出现了，如果有两辆车A车和B车，A车在B车的后面，并且A车的速度比B车的快，那么经过一段时间后，A车一定会超过B车。我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0。没有两辆车的坐标相同。
输入：
第一行，一个数n，车辆总数。
第二行至第n+1行，为n辆车的信息
每行有两个正整数x，y，x和y之间有一个空格
x为车的坐标，y为车的速度
0<x，y<=1000000000
输出：超车总数【逆序对个数】
先说说我第一次没看书理解的题意：开一个结构体，按坐标从小到大sort记录位次，然后sort按速度排序，用总数减去每次的位次，然后累加。后来发现如果速度大的在前次大的数不可能超过，而记录它之前的车总数-1不管从时间上还是从策略上都很难满足【已经按速度排序不可能从1循环到这辆车】。
然后从书上看到了这道题，本来准备看代码试一下，然后yyx同学告诉我这个代码完全是个bug，我就信了，根本不敢打，事实上证明书上的代码是正确的orz
事实证明自己努力想一些东西还是好的。解题思路大概就是将序列分开然后排序，然后把两个排过的合并。因为两边的序列有序，那么在一边选取的数和另一边比较，前面的数肯定全
都是逆序的。将排序和统计同时进行，不会影响最终答案。ps：注意统计数据量...会爆掉int
下面放代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n; long long ans=0; struct qaq { int x; int y; }; qaq car[300100]; int c[300100]; int a[300100]; bool mycmp(qaq a,qaq b) {return a.x<b.x;} void init() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&car[i].x,&car[i].y); sort(car+1,car+1+n,mycmp); for(int i=1;i<=n;i++) a[i]=car[i].y; //for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl<<"----------------"; } void work(int l,int r) { int i,j,mid,temp; if(l+1<r) { mid=(l+r)/2; work(l,mid-1); work(mid,r); temp=l; for(i=l,j=mid;(i<=mid-1)&&(j<=r);) { if(a[i]>a[j]) { c[temp++]=a[j++]; ans+=mid-i; } else c[temp++]=a[i++]; } if(j<=r) { for(;j<=r;j++) c[temp++]=a[j]; } else { for(;i<=mid-1;i++) c[temp++]=a[i]; } for(int i=l;i<=r;i++) a[i]=c[i]; } else { if(l+1==r) { if(a[l]>a[r]) { int tt=a[r]; a[r]=a[l]; a[l]=tt; ans++; } } } } int main() { init(); work(1,n); cout<<ans<<endl; return 0; }