题意：
现在有n辆bus，然后有m个乘客。
每辆bus有自己相应的开车路段，与开车时间。
s,f,t,表示开车的起始站，终点站，开车时间。
l,r,b分别表示乘客想要从l到达r站，然后乘客开始等车时间为b。
那么就可以猜想到这个乘客要搭乘这辆车，需要满足一下条件
s<l,r<f,t>b,
那么此时我们按照起始点排序把所有的路段都包含进来，按照时间点来建立线段树，然后从单点更新，剩下的自己来看一下吧。。。
View Code
1 #include<iostream> 2 #include<stdlib.h> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 using std::max; 7 using std::sort; 8 using std::lower_bound; 9 const int N = 222000; 10 int n,m; 11 int rmax[N<<2],id[N<<2],tt[N<<1],answer[N]; 12 struct node 13 { 14 int l,r,t,id; 15 bool operator<(const node tmp)const 16 { 17 return (l<tmp.l)||(l==tmp.l&&id<tmp.id); 18 } 19 }L[N<<1]; 20 void PushUp(int t) 21 { 22 rmax[t]=max(rmax[t<<1],rmax[t<<1|1]); 23 } 24 void update(int L,int Raim,int idx,int l,int r,int t) 25 { 26 if(l==r) 27 { 28 rmax[t]=Raim; 29 id[t]=idx; 30 return ; 31 } 32 int m=(l+r)>>1; 33 if(L<=m)update(L,Raim,idx,l,m,t<<1); 34 else update(L,Raim,idx,m+1,r,t<<1|1); 35 rmax[t]=max(rmax[t<<1],rmax[t<<1|1]); 36 } 37 int query(int pos,int Raim,int l,int r,int t) 38 { 39 if(Raim>rmax[t])return -1; 40 if(l==r)return id[t]; 41 int ans=-1; 42 int m=(l+r)>>1; 43 if(pos<=m) 44 { 45 ans=query(pos,Raim,l,m,t<<1); 46 if(ans>0)return ans; 47 } 48 return query(pos,Raim,m+1,r,t<<1|1); 49 } 50 int main() 51 { 52 while(~scanf("%d %d",&n,&m)) 53 { 54 for(int i=1;i<=n+m;i++) 55 { 56 scanf("%d %d %d",&L[i].l,&L[i].r,&L[i].t); 57 L[i].id=i; 58 tt[i]=L[i].t; 59 } 60 sort(tt+1,tt+n+m+1); 61 sort(L+1,L+n+m+1); 62 for(int i=1;i<=n+m+1;i++) 63 { 64 int p=lower_bound(tt+1,tt+n+m+1,L[i].t)-tt; 65 if(L[i].id<=n)update(p,L[i].r,L[i].id,1,n+m,1); 66 else answer[L[i].id-n]=query(p,L[i].r,1,n+m,1); 67 } 68 for(int i=1;i<m;i++)printf("%d ",answer[i]); 69 printf("%d\n",answer[m]); 70 } 71 return 0; 72 }