题目背景
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
说明
n最大30W
【题目链接】:https://www.luogu.org/problem/show?pid=U4566
【题解】
五中的一个小学弟问我的。。
预处理出每个位置的车的编号i,存在h数组中;
记录每辆车的信息在x[i],v[i]中;
枚举0->100W位置i;
直接在线段树中返回速度区间在0..v[h[i]]-1的车的数量;
累加进答案;
然后在线段树中递减v[h[i]]这个节点;
(线段树单节点更新);
这样可以保证我们询问的时候返回的速度都是在后面的车的速度;
【完整代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAX = 1000009;
const int MAXN = 300009;
int pre[MAX];
int x[MAXN],y[MAXN],sum[MAX<<2]= {0};
int h[MAX];
void updata(int c,int pos,int l,int r,int rt)
{
if (l==r)
{
sum[rt]+=c;
return;
}
int m = (l+r)>>1;
if (pos <=m)
updata(c,pos,l,m,rt<<1);
else
updata(c,pos,m+1,r,rt<<1|1);
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
LL query(int L,int R,int l,int r,int rt)
{
if (L <= l && r<= R)
return sum[rt];
int m = (l+r)>>1;
LL temp1 = 0,temp2 = 0;
if (L <= m)
temp1+=query(L,R,l,m,rt<<1);
if (m < R)
temp2+=query(L,R,m+1,r,rt<<1|1);
return temp1+temp2;
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
int n;
scanf("%d",&n);
for (int i =1;i <= n;i++)
{
scanf("%d%d",&x[i],&y[i]);
h[x[i]] = i;
updata(1,y[i],0,MAX-9,1);
}
LL ans = 0;
for (int i = 0;i <= MAX-9;i++)
if (h[i])
{
int v = y[h[i]];
ans += query(0,v-1,0,MAX-9,1);
updata(-1,v,0,MAX-9,1);
}
cout << ans<<endl;
return 0;
}