[JOISC2014]バス通学
题目大意：
有\(n(n\le10^5)\)个点和\(m(m\le3\times10^5)\)条交通线路。第\(i\)条交通线路可以让你在时间\(x_i\)从\(a_i\)出发，并在\(y_i\)时到达\(b_i\)。\(q(q\le10^5)\)次询问，每次询问若要在时间\(l_i\)到达\(n\)点，最晚什么时候要从\(1\)点出发。
思路：
将每条交通线路拆成两种操作：出发和到达。
用\(f_i\)表示乘上第\(i\)辆车最晚几点出发，\(g_i\)表示到达第\(i\)个点最晚几点出发。
将所有操作按照发生的时间\(t_i\)排序，对于出发和到达，分别进行以下两种操作：
- 出发：询问\(g_{a_i}\)。
- 到达：用\(f_i\)更新\(g_{b_i}\)。
而对于最后的询问，也相当于第一种操作。
时间复杂度\(\mathcal O((m+q)\log(m+q))\)。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
const int N=1e5+1,M=3e5;
int f[M*2],g[N];
struct Query {int x,t,id;bool type;//0->Start, 1->Endbool operator < (const Query &rhs) const {if(t==rhs.t) return type>rhs.type;return t<rhs.t;}
};
std::vector<Query> v;
int main() {const int n=getint(),m=getint();for(register int i=0;i<m;i++) {const int x=getint(),y=getint(),s=getint(),t=getint();v.push_back((Query){x,s,i,0});v.push_back((Query){y,t,i,1});}const int q=getint();for(register int i=0;i<q;i++) {v.push_back((Query){n,getint(),m+i,0});}const int k=v.size();std::sort(v.begin(),v.end());std::fill(&g[2],&g[n]+1,-1);for(register int i=0;i<k;i++) {const int &x=v[i].x,&id=v[i].id;if(v[i].type) {//Endg[x]=std::max(g[x],f[id]);} else {//Startf[id]=x!=1?g[x]:v[i].t;}}for(register int i=0;i<q;i++) {printf("%d\n",f[m+i]);}return 0;
}
