模拟赛 T3，感觉评不了紫。赛时因为忘调用 build没调出来……

题目大意：给你 $n$ 个区间 $[l_i,r_i]$ 和 $q$ 个询问 $[p_i,q_i]$，对每个询问，求最少将 $[p_i,q_i]$ 内的区间划为多少部分，使得：每部分下标连续并且该部分的区间交集为空。

有一个显然的贪心想法就是对于每个部分，尽可能让其越长越好，因为这样后面剩的的线段越少越不容易有交集，于是我们对于每个位置 $i$，求 $f_i=\max\limits_{j\ge i,\bigcap\limits_{k=i}^j=\text{\o}} j$。也就是以 $i$ 为左端点，最右端的右端点。

考虑这个东西怎么求，由于交集运算具有单调性，也就是若 $\bigcap\limits_{k=i}^j [l_k,r_k]\ne \text{\o}$，则 $\bigcap\limits_{k=i}^{j+1} [l_k,r_k]\ne \text{\o}$；若 $\bigcap\limits_{k=i}^j [l_k,r_k]= \text{\o}$，则 $\bigcap\limits_{k=i+1}^j [l_k,r_k]= \text{\o}$。

于是可以双指针求，那怎么判断加入一个区间会不会产生交集呢？由于我们已经扫了 $[i,j-1]$ 的区间了，也就是这里面的区间两两无交，那么只需要判断区间 $j$ 和这些区间是否有交即可。这个可以离散化一下用线段树维护。

求出 $f$ 之后，每次询问相当一个这样的过程：重复 $l=f_l+1$，问最少多少次后 $l\ge r$。于是就可以倍增轻松实现。

代码：

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e5+5;
int n,q,f[N][20],b[N<<1],l[N],r[N],m,ls[N<<2],rs[N<<2],sum[N<<2],cnt,tag[N<<2];
void build(int &u,int l,int r){u=++cnt;if(l==r) return;build(ls[u],l,mid),build(rs[u],mid+1,r);}
void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];}
void pushdown(int u,int l,int r){
	sum[ls[u]]+=(mid-l+1)*tag[u],sum[rs[u]]+=(r-mid)*tag[u];
	tag[ls[u]]+=tag[u],tag[rs[u]]+=tag[u],tag[u]=0;
}
void add(int u,int l,int r,int L,int R,int val){
	if(L<=l&&r<=R){tag[u]+=val,sum[u]+=(r-l+1)*val;return;}
	pushdown(u,l,r);
	if(L<=mid) add(ls[u],l,mid,L,R,val);
	if(mid<R) add(rs[u],mid+1,r,L,R,val);
	pushup(u);
}
int query(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R) return sum[u];
	pushdown(u,l,r);int res=0;
	if(L<=mid) res+=query(ls[u],l,mid,L,R);
	if(mid<R) res+=query(rs[u],mid+1,r,L,R);
	return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++) cin>>l[i]>>r[i],b[++m]=l[i],b[++m]=r[i];
	cin>>q;sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;build(b[0],1,m);
	for(int i=1;i<=n;i++) l[i]=lower_bound(b+1,b+1+m,l[i])-b,r[i]=lower_bound(b+1,b+1+m,r[i])-b;
	for(int i=1,j=0;i<=n;i++){
		while(j<n&&!query(1,1,m,l[j+1],r[j+1])) j++,add(1,1,m,l[j],r[j],1);
		f[i][0]=j+1,add(1,1,m,l[i],r[i],-1);
	}
	for(int k=1;k<=17;k++)for(int i=1;i<=n;i++) f[i][k]=f[f[i][k-1]][k-1];
	for(int i=1,u,v;i<=q;i++){
		cin>>u>>v;int ans=0;
		for(int k=17;~k;k--) if(f[u][k]&&f[u][k]<=v) u=f[u][k],ans|=1<<k;
		cout<<ans+1<<'\n';
	}
	return 0; 
}