题目背景
kkk在赛车~
题目描述
现在有N辆赛车行驶在一条直线跑道（你可以认为跑道无限长）上。它们各自以某种速度匀速前进，如果有两辆车A车和B车，A车在B车的后面，且A车的速度大于B车的速度，那么经过一定的时间后，A车必定会超过B车，这称为一次超车。求超车总数。道路起点的位置为0，没有两辆车的初始位置相同。
输入输出格式
输入格式：
第一行，一个数n，车辆的总数。
第二行~第n+1行，为n辆车的信息，每行有两个正整数x，y。X为起始位置，y为速度。0<x,y<=1000000
输出格式：
超车总数
输入输出样例
输入样例#1：
2
5 6
2 8
输出样例#1：
1
说明
30%的数据，n<=300
50%的数据，n<=3000
100%的数据，n<=300000
*
从题意中可以看出，要求求出a[i]<a[j]&&b[i]>b[j]，我们可以先按a[i]排序，然后求逆序对。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
int a[N],b[N],v,n;long long ans;
struct node{
int pos,v;
};node e[N];
bool cmp(const node&s1,const node&s2){
if(s1.pos!=s2.pos)return s1.pos<s2.pos;
return s1.v<s2.v;
}
void merge_sort(int s,int t){
if(s>=t)return;
int mid=(s+t)>>;
merge_sort(s,mid);
merge_sort(mid+,t);
int i=s,j=mid+,k=s;
while(i<=mid&&j<=t){
if(a[i]>a[j]){
b[k]=a[j];
j++;k++;ans+=(long long)(mid-i+);
}
else {
b[k]=a[i];
i++;k++;
}
}
while(i<=mid){b[k]=a[i];i++;k++;}
while(j<=t){b[k]=a[j];j++;k++;}
for(int l=s;l<=t;l++)a[l]=b[l];
}
int main(){
freopen("jh.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&e[i].pos,&e[i].v);
sort(e+,e+n+,cmp);
for(int i=;i<=n;i++)
a[i]=e[i].v;
merge_sort(,n);
cout<<ans;
return ;
}