文章标题 HRBUST 1400 ： 汽车比赛（树状数组 ）

树状数组 ）"/>

文章标题 HRBUST 1400 ： 汽车比赛（树状数组 ）

汽车比赛

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
题意：中文题干。。。
分析：首先，如果一个人的速度大于另一个人的话，要使得有超车那就得这个人的位置比另一个人的位置要靠前或者同一位置。所以我们可以先按位置从大到小排序，位置一样的按速度从小到大排序，然后用树状数组来维护每个速度的数量，然后枚举每一个人，对于当前整个人，能超车的都是速度小于当前这个人的速度的，所以只要查找下比当前速度还小的前缀和就行了，这个操作就少树状数组的区间查询，然后每次枚举完一个人之后，还得将当前这个人的速度插入进树状数组，这个就是单点修改
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;const int mod=1e9+7;
const int maxn=1e5+10;int tree[maxn];
int n;struct node {int pos,v;bool operator <(const node & t)const {return pos>t.pos||(pos==t.pos&&v<t.v);} 
}a[maxn];int lowbit(int x){return x&(-x);
}int sum(int i){int s=0;while (i>0){s+=tree[i];i-=lowbit(i);}return s;
}void add(int i,int val){while (i<=100000){tree[i]+=val;i+=lowbit(i);}
}int main()
{while (scanf ("%d",&n)!=EOF){memset (tree,0,sizeof (tree));for (int i=0;i<n;i++){scanf ("%d%d",&a[i].pos,&a[i].v);}sort(a,a+n);ll ans=0;for (int i=0;i<n;i++){int tmp=a[i].v;add(tmp,1);ans+=sum(tmp-1);}printf ("%lld\n",ans);}return 0;
}