Buses and People 3D Processing
Main theme: there are n buses, each bus has s (starting point), f (end point), t (departure time), there are m individuals, each person has l (starting point), R (end point), t (appear time).
For a person, when t <= t (car), s <= l, r <== f, he can get on the car, and ask which one has the earliest departure time.
Similar to the three-dimensional partial order problem, there are three dimensions that need to be solved. First of all, cars and people have l,r,t, three attributes, first sorted according to l, solve the first dimension, so that for a person, all the cars in front are possible to go up. The remaining two dimensions are solved by segment tree, which maintains the maximum value of the interval. The line segment tree subscript corresponds to t, and the maximum maintenance value is r. Sort the car and people together, traverse from the beginning, it is the car, insert r in the t position, it is the person, query the ID corresponding to the smallest subscript less than R from the T position of the line segment tree to the end (i.e., the ID of the car).
It was never expected that a segment tree could be used to solve two-dimensional problems directly.
When a person is queried, the l of the car that has been inserted in front must be smaller than it; the line segment tree queries the T to the end, and the car whose t is larger than the person must be in it; the line segment tree maintains the maximum value of r, so long as the R in the query interval is greater than or equal to the person's r, the person will be able to board the car.
Sorting solves one-dimensional problem, segment tree solves one-dimensional problem, and maximum maintenance solves one-dimensional problem.
#include <cstdio> #include <algorithm> #include <cmath> #define Mid ((a[k].l+a[k].r)>>1) #define cl (k<<1) #define cr (k<<1|1) #define Max 0x3f3f3f3f using namespace std; typedef long long LL; const int maxn=2e5+5; struct Q{ int l,r,t, id,tp;//TP = 0 car, TP = 1 person friend bool operator <(Q a, Q b){ if(a.l!=b.l) return a.l < b.l; //Ordered by l, if l is the same, the person after return a.tp < b.tp; } }q[maxn*2]; struct N{ int l,r; int ma,id; }a[maxn*4]; int dis[maxn*2], cur;//Discretization int ans[maxn]; void build(int k,int l,int r){ a[k].l=l, a[k].r=r; a[k].ma = -1; a[k].id = -1; if(l==r) return; int mid=Mid; build(cl,l,mid), build(cr,mid+1,r); } void updata(int k,int i,int x, int id){ if(a[k].l==a[k].r){ if(a[k].ma < x){ a[k].ma = x; a[k].id = id; } return; } int mid=Mid; if(i<=mid) updata(cl,i,x,id); else updata(cr,i,x,id); if(a[k].ma < a[cl].ma){ a[k].ma = a[cl].ma; a[k].id = a[cl].id; } if(a[k].ma < a[cr].ma){ a[k].ma = a[cr].ma; a[k].id = a[cr].id; } } int get(int k,int l,int r,int x){//Returns the id corresponding to the required minimum subscript if(a[k].l==a[k].r && a[k].ma>=x) return a[k].id; int mid=Mid; int ret=Max; if(l<=mid && a[cl].ma>=x ){ //If there is a match on the left, you can go back directly. The subscript (t) on the left must be smaller than that on the right. ret = get(cl,l,r,x); if(ret!=Max) return ret; } if(r>mid && a[cr].ma>=x ){ ret = get(cr,l,r,x); if(ret!=Max) return ret; } return ret; } int gs(int x){return lower_bound(dis+1,dis+1+cur,x)-dis; }//Discretization int main() { int n,m,qn=0; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++){ qn++; scanf("%d%d%d",&q[qn].l, &q[qn].r, &q[qn].t); q[qn].tp = 0; q[qn].id = i; dis[++cur] = q[qn].t; } for(int i=1; i<=m; i++){ qn++; scanf("%d%d%d",&q[qn].l, &q[qn].r, &q[qn].t); q[qn].tp = 1; q[qn].id = i; dis[++cur] = q[qn].t; } sort(dis+1,dis+cur+1); cur = unique(dis+1,dis+cur+1) - (dis+1); sort(q+1,q+1+qn); build(1,1,cur); for(int i=1; i<=qn; i++){ if(q[i].tp==0){//vehicle updata(1, gs(q[i].t) ,q[i].r, q[i].id); }else{ int x=get(1, gs(q[i].t), cur, q[i].r); if(x==Max)//Can't find ans[q[i].id] = -1; else ans[q[i].id] = x; } } for(int i=1; i<=m; i++){ printf("%d ",ans[i]); } printf("\n"); }