E. Minimal Segment Cover
题意
给你n个区间和m次询问，每次询问给出一个区间，问最少多少条线段可以覆盖这个区间。
做法
首先考虑n^2贪心的做法，每次从左端点L开始，找到包含这个点的r最大的区间，再从这个新区间的r出发，不断进行这个操作，直到包含R。我们发现对于每个点来说，一定是跳到他经过一个区间能跳到的最右侧的点，这样每个点只指向一个点，就形成一棵树，之后把L，R看成树上的两个节点，从L向上倍增直到当前节点值大于R即可，复杂度O(nlog?n)O(n \log n)O(nlogn)
代码
```#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e6+10;vector<int> v[maxn],v2[maxn];
int l[maxn],r[maxn],fa[maxn];
int f[maxn][20];//重置0
int deep[maxn];//重置0
int vis2[maxn];//重置0
int ff[maxn];
vector<int> G[maxn];//清空
void dfs_LCA(int u,int fat,int ffa)//调用dfs_LCA(rt,rt)
{
ff[u]=ffa;f[u][0]=fat;vis2[u]=1;for(int i=1;i<=19;i++) f[u][i]=f[f[u][i-1]][i-1];for(int i=0;i<G[u].size();i++){
int v=G[u][i];if(vis2[v]==1)continue;deep[v]=deep[u]+1;dfs_LCA(v,u,ffa);}
}
int lca(int a,int b)
{
int lim=0;while((1LL<<lim)<=deep[a]) lim++;if(a>=b)return a;for(int i=lim;i>=0;i--){
if(f[a][i]<b){
a=f[a][i];}}return f[a][0];
}
int main()
{
int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);v[l[i]].push_back(r[i]);v2[r[i]].push_back(r[i]);}multiset<int> s;for(int i=0;i<=500000;i++){
fa[i]=i;for(int j=0;j<v[i].size();j++){
int to=v[i][j];s.insert(to);}if(!s.empty())fa[i]=max(fa[i],*s.rbegin());for(int j=0;j<v2[i].size();j++){
int to=v2[i][j];multiset<int>::iterator it = s.lower_bound(to);s.erase(it);}}for(int i=0;i<=500000;i++){
if(i!=fa[i]) G[fa[i]].push_back(i);}for(int i=0;i<=500000;i++){
if(fa[i]==i) dfs_LCA(i,i,i);}while(m--){
int l,r;scanf("%d%d",&l,&r);int ans=lca(l,r);if(ff[l]!=ff[r]) printf("-1\n");else printf("%d\n",max(1,deep[l]-deep[ans]));}return 0;
}