Codeforces Round #111 (Div. 2) E. Buses and People 线段树数据结构与算法weixin43824564的博客-

这很像一个偏序的问题 但是我们要用线段树来解决它  仔细想想cdq应该也可 但是写起来比较麻烦

我们就写线段树

首先我们把人和车都按上车起始点排序  这样可以减少一维  

剩下还有终止点和时间这两维  我们对时间离散化 并且以时间（车辆的信息）开一棵线段树维护终止点的最大值 以及车辆的编号（应该是不存在时间相同的车的）  

对于每辆车 我们更新对应时间点的终止点以及车辆编号

对于每个人 我们根据维护的终止点最大值 在pos~tot的区间上 去找最左端的合法点 

pos是这个人的时间离散后排的位置  tot是时间离散后的总数   这个询问区间可以保证 车的时间大于人的时间

根据终止点最大值 可以进行剪枝

 #include<bits/stdc++.h> using namespace std; const int N = 2e5+100; int n,m,has[N],tot,ans[N]; #define lson id<<1,l,mid #define rson id<<1|1,mid+1,r struct Bus{  int l,r,b,id;  bool operator < (const Bus& a)const{//车和人起始点相同时 车排前面   if(l==a.l) return id<a.id;   return l<a.l;  }  }bus[2*N]; int mx[N<<2],k[N<<2]; void pushup(int id){  mx[id]=max(mx[id<<1],mx[id<<1|1]); } void update(int id,int l,int r,int pos,int val,int v){  if(l==r){   mx[id]=max(mx[id],val);   k[id]=v;   return;  }int mid = l+r>>1;  if(pos<=mid) update(lson,pos,val,v);  else update(rson,pos,val,v);  pushup(id);  } int query(int id,int l,int r,int L,int R,int q){  if(L<=l&&R>=r)   if(mx[id]<q) return -1;  if(l==r) return k[id];  int mid = l+r>>1,ret=-1;  if(L<=mid) ret=query(lson,L,R,q);  if(ret!=-1) return ret;  if(R>mid) ret=query(rson,L,R,q);  return ret; } int main(){  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].b);   has[++tot]=bus[i].b;   bus[i].id=i;  }  sort(has+1,has+1+tot);  tot=unique(has+1,has+1+tot)-has-1;  sort(bus+1,bus+1+n+m);  for(int i = 1; i <= n+m; i++){   int pos = lower_bound(has+1,has+1+tot,bus[i].b)-has;   if(bus[i].id<=n) update(1,1,tot,pos,bus[i].r,bus[i].id);   else ans[bus[i].id-n]=query(1,1,tot,pos,tot,bus[i].r);  }  for(int i = 1; i <= m; i++) printf("%d ",ans[i]);  return 0; }