汽车比赛

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 188(56 users)

Total Accepted: 72(50 users)

Rating:

Special Judge: No

Description

XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛，这种的比赛规模很大，涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛，XianGe幻想着有许多人参赛，那是人山人海啊，不过XianGe只允许最多100000人参加比赛。

这么大规模的比赛应该有技术统计，在XianGe的比赛中所有车辆的起始点可能不同，速度当然也会有差异。XianGe想知道比赛中会出现多少次超车（如果两辆车起点相同速度不同也算发生一次超车）。

Input

本题有多组测试数据，第一行一个整数n，代表参赛人数，接下来n行，每行输入两个数据，车辆起始位置X i 和速度 V i（0<Xi,Vi<1000000）

Output

输出比赛中超车的次数，每组输出占一行

Sample Input

2

2 1

2 2

5

2 6

9 4

3 1

4 9

9 1

7

5 5

6 10

5 6

3 10

9 10

9 5

2 2

Sample Output

1

6

7

Author

杨和禹

解题思路：

 

给出n个汽车的起始位置和速度，问总共可以发生多少次超车，位置相同，速度不一样也算一次超车。

位置小速度大的车肯定能超过位置大速度小的车。把n个车按起始位置从小到大，如果相等按速度从大到小进行排序。用树状数组进行统计，区间为速度大小，对第j辆车来说，假设他的速度为v，则首先更新vn[v] ++，并利用lowbit向上更新，因为这是第j辆车，统计区间【1，v】的速度有多少辆车（包括自己），这些车是不可能超过它的，那么j- sum(v)则是前j辆车有多少辆可以超过当前的车，也就是超车的次数。

拿第二组测试数据为例：

5

2 6

9 4

3 1

4 9

9 1

排序后

2 6

3 1

4 9

9 4

9 1

速度    1  2  3  4  5  6  7  8  9

多少辆  2  0  0  1  0  1   0  0  1

拿最后一个数据具体说明 9  1 ,这是第5辆车，他的速度为v，在他之前速度小于等于它的有两辆（包括自身），那么前面能够超过它的车有 5-2=3辆 ，对于每辆车都统计出前面能够超过它的车有多少辆，加起来就是所求的超车次数了。

代码：

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=100002;const int maxv=1000002;int vn[maxv];struct Car{    int x;    int v;}car[maxn];bool cmp(Car a,Car b)//先按位置从小到大进行排序，如果位置相等，按速度从大到小进行{    if(a.x
       
        =b.v)            return true;        return false;    }    return false;}int lowbit(int x){    return x&(-x);}void update(int p,int max){    while(p<=max)    {        vn[p]++;        p+=lowbit(p);    }}int  sum(int p)//这题这里的意思是前p辆车中比当前车速度小或相等的车有几辆（包括它自己）{    int s=0;    while(p>0)    {        s+=vn[p];        p-=lowbit(p);    }    return s;}int main(){    int n;    while(cin>>n)    {        memset(vn,0,sizeof(vn));        int max=0;        for(int i=1;i<=n;i++)        {            cin>>car[i].x>>car[i].v;            if(max