HLG 1400 汽车赛事 （11年黑龙江省赛）树状数组（逆序数）
HLG 1400 汽车比赛 （11年黑龙江省赛）树状数组（逆序数）
链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1400
Description：
XianGe非常喜欢赛车比赛尤其是像达喀尔拉力赛，这种的比赛规模很大，涉及到很多国家的车队的许多车手参赛。XianGe也梦想着自己能举办一个这样大规模的比赛，XianGe幻想着有许多人参赛，那是人山人海啊，不过XianGe只允许最多100000人参加比赛。
这么大规模的比赛应该有技术统计，在XianGe的比赛中所有车辆的起始点可能不同，速度当然也会有差异。XianGe想知道比赛中会出现多少次超车（如果两辆车起点相同速度不同也算发生一次超车）。
Input：
本题有多组测试数据，第一行一个整数n，代表参赛人数，接下来n行，每行输入两个数据，车辆起始位置X i 和速度 V i（0<Xi,Vi<1000000）
Output：
输出比赛中超车的次数，每组输出占一行
思路：这道题跟POJ 3067 Japan很像，基本上是一样的思路和方法，详细请看我博客上一贴；
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 1000000
using namespace std;
int c[MAXN], MAXV;
struct point
{
int x, v;
};
point car[MAXN];
int lowbit(int x){ return x & (-x); }
void add(int x,int val)
{
int i = x;
while(i <= MAXV) {
c[i] += val;
i += lowbit(i);
}
}
int get_sum(int x)
{
int s = 0;
while(x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
int cmp(point Y1, point Y2)
{
if(Y1.x != Y2.x) return Y1.x < Y2.x;
else return Y1.v > Y2.v;
}
int main()
{
int n;
long long sum;
while(scanf("%d", &n)!=EOF) {
MAXV = 0;
memset(c, 0, sizeof(c));
for(int i=1; i<=n; i++) {
scanf("%d%d", &car[i].x, &car[i].v);
if(MAXV < car[i].v)
MAXV = car[i].v;
}
sort(car, car+n+1, cmp);
sum = 0;
for(int i=1; i<=n; i++) {
//cout<<car[i].x<<" "<<car[i].v<<endl;
add(car[i].v, 1);
sum += i-get_sum(car[i].v);
}
printf("%lld\n", sum);
}
return 0;
}