Hust oj 1400 汽车比赛(树状数组）_综合

汽车比赛

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 438(119 users)

Total Accepted: 168(98 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

杨和禹

还记得这是上学期上实验课的时候看的一道题，那时候傻傻的贪心以为能过，结果稳稳地超时，今天开始学树状数组就又把这道题拿了出来，感觉体会深了不少；

先按距离从小到大排序，距离相同的按速度从大到小排序。然后按每辆车的速度update树状数组->add（v,1),把值定为1只是为了计数，因为车是按距离由小到大排列，所以只要距离小于i车且速度大于i车的车都可以发生超车，所以不可能超过i车的数量=getsum（i）（包括自己），则可超过i车的数量=i-getsum[i];

可能说的不太明白，用第二组样例举个例子；

Sample Input

5
2 6
9 4
3 1
4 9
9 1

after sort

v 6 1 9 4 1

x 2 3 4 9 9

此时树状数组

v 1 2 3 4 5 6 7 8 9

n 2 0 0 1 0 1 0 0 1

用最后一辆车距离，此车是第五辆车，速度为1，比它速度小的有2辆（包括自己），所以getsum（1）=2，所以结果=5-2=3；

上代码~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;struct Car
{int s,v;
}c[100005];int a[100005];int cmp(Car x,Car y)
{if(x.s==y.s)return x.v>y.v;elsereturn x.s<y.s;
}int lowbit(int x)
{return x&(-x);
}void add(int pos,int num)
{while(pos<=100005){a[pos]+=num;pos+=lowbit(pos);}
}long long int getsum(int n)
{long long int sum=0;while(n>0){sum+=a[n];n-=lowbit(n);}return sum;
}int main()
{int n;int i,j,k;while(cin>>n){long long int sum=0;memset(a,0,sizeof(a));for(i=1;i<=n;i++){cin>>c[i].s>>c[i].v;}sort(c+1,c+n+1,cmp);for(i=1;i<=n;i++){add(c[i].v,1);sum+=(i-getsum(c[i].v));}cout<<sum<<endl;}
}