【Codeforces Round #111 (Div. 2) E. Buses and People】离散化+线段树

链接：

Codeforces Round #111 (Div. 2) E. Buses and People

题意

有n个公交车，每个公交车的信息有$s_i$(公交车起始下标)，$f_i$（公交车终点下标）,$t_i$(公交车发车时间)。
有m个乘客，每个乘客的信息有$l_i$(乘客起始下标)，$r_i$(乘客下车的下标)，$b_i$(乘客上车时间)。
乘客$i$坐上公交车$j$的前提是$s_j\le l_i$,$r_i\le f_j$,$b_i\le t_j$,问每一个乘客能坐的公交车中发车时间最小的公交车编号。

做法

首先先将所有公交车和乘客放到一起，之后按照起始下标排序，这样就能保证每个人乘客之前的公交车一定满足$s_j\le l_i$。

之后我们对时间进行离散化建立线段树,每个节点存储当前t能到达的最大的$f$，对于每个乘客，我们只需要查找小于等于$t_i$的时间区间中最小的满足$r_i\le f_j$的t即可。

所以问题就转换为给定一个区间，求区间内最小的下标满足权值大于某个给定值。这个问题只需要在线段树上优先查询左子区间是否有满足情况的点，向下递归询问即可，注意要用区间max进行剪枝。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5+5;
struct T
{
    int l,r,mid;int val,id;
}tree[maxn<<2];
void push_up(int rt)
{
    tree[rt].val=max(tree[rt<<1].val,tree[rt<<1|1].val);
}
void build(int rt ,int l,int r)
{
    tree[rt].l=l;tree[rt].r=r;if(l==r){
    tree[rt].id=-1;tree[rt].val=0;return ;}int mid=tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);
}
void update(int rt,int pos,int val,int id)
{
    if(tree[rt].l==tree[rt].r){
    tree[rt].val=max(tree[rt].val,val);tree[rt].id=id;return ;}if(pos<=tree[rt].mid) update(rt<<1,pos,val,id);else update(rt<<1|1,pos,val,id);push_up(rt);
}
int query(int rt,int val,int l,int r)
{
    if(tree[rt].l>=l&&tree[rt].r<=r){
    if(tree[rt].val<val) return -1;}if(tree[rt].l==tree[rt].r) return tree[rt].id;int ans=-1;if(tree[rt].mid>=l){
    ans=query(rt<<1,val,l,r);if(ans!=-1) return ans;}if(tree[rt].id<r){
    ans=query(rt<<1|1,val,l,r);if(ans!=-1) return ans;}return -1;
}
struct Bus
{
    int l,r,t,id;bool operator<(const Bus y)const{
    if(l==y.l) return id<y.id;//要注意一个l同时有公交车和乘客，先更新公交车信息。return l<y.l;}
}bus[maxn<<2];
int Hash[maxn<<2],cnt;
int ans[maxn<<2];
int main()
{
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n+m;i++){
    scanf("%d%d%d",&bus[i].l,&bus[i].r,&bus[i].t);bus[i].id=i;Hash[++cnt]=bus[i].t;}sort(bus+1,bus+1+n+m);sort(Hash+1,Hash+1+cnt);build(1,1,cnt);int d=unique(Hash+1,Hash+1+cnt)-Hash-1;//对时间进行离散化for(int i=1;i<=n+m;i++){
    int pos=lower_bound(Hash+1,Hash+1+d,bus[i].t)-Hash;if(bus[i].id<=n) update(1,pos,bus[i].r,bus[i].id);//公交车信息进行更新else ans[bus[i].id-n]=query(1,bus[i].r,pos,cnt);//乘客进行查询}for(int i=1;i<=m;i++) printf("%d ",ans[i]);return 0;
}