赛车比赛（洛谷U4566）

题目背景

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 ;

}