思考

不难发现，很容易抽象成图:

有一个显然性质，如果两个由一段黄色线段连接的两个紫色方块位于同一询问区间，显然靠左紫色方块那一行的机器人可以直接并到右紫色方块那一行，于是我尝试正向思考，类似合并区间信息的方式用线段树来维护。后面发现，这样太复杂，几乎是不可做的，于是开始逆向思考。

注意题面中提到了，不同询问可能的方块填色方案可能是不同的，那么也就意味着最后机器人的终点集合可能不同。所以其实不同填色方案也就约等于不同的机器人终点集合。那么，我们思考不同的机器人集合，有什么不同之处。

观察到，我们可以确定一个终点所能涵盖的起点范围，也就是可以抵达它的起点范围，像是上图中第 $4$ 行的黑方格，它就可以涵盖第 $3$ 行到第 $5$ 行的起点。

于是，对于一种机器人终点集合，也就意味着一系列涵盖区间的并集，转化一下题意，也就是我们需要用最少的区间并出一个包含询问区间的区间，问最少区间数。

首先，对于一个询问区间 $[l,r]$，考虑从左到右去覆盖它，我们肯定寻找一个左端点小于等于 $l$ 的区间，否则无法询问区间左端点 $l$，同时贪心地，我们一定取满足能覆盖左端点 $l$ 且右端点尽可能大的区间，然后覆盖完后未被覆盖的区间部分构成新区间，重复上述过程即可。关于如何维护取得左端点小于等于某值的区间最大右端点有多种数据结构可以做到，树状数组、线段树均可。

但是只是这样重复，效率难以保证通过。不难发现，对于一个左端点 $l$ 可以唯一确定一个最优区间，所以，我们可以用倍增维护对于一个左端点选择 $2^i$ 个区间所能覆盖到的最大右端点。

关于如何维护出这些区间，对于一个终点 $(a,w+1)$，它能覆盖的区间一定取决于 $a-1,a+1$ 行能够转移到它的紫色方块，从左到右递推出所有紫色方块能够涵盖到的最大区间，最后再递推出终点即可。

code

#include<bits/stdc++.h>
#define lb(x) (-(x)&(x))
using namespace std;
const int N=2e5+5;
int h,w,q,lst[N],l[N],r[N],L[N],R[N],nxt[N][20];
int mx[N];
inline void update(int i,int x){
	for(;i<=h+1;i+=lb(i))mx[i]=max(mx[i],x);
	return;
}
inline int query(int i,int res=0){
	for(;i;i-=lb(i))res=max(res,mx[i]);
	return res;
}
int main(){
//	freopen("c.out","w",stdout);
	scanf("%d%d",&h,&w);
	for(int i=1,x;i<=w;i++){
		scanf("%d",&x);
		if(!l[x])l[x]=r[x]=x;
		if(lst[x-1]&&lst[x]<lst[x-1])l[x]=min(l[x],l[x-1]);
		if(lst[x+1]&&lst[x]<lst[x+1])r[x]=max(r[x],r[x+1]);
		lst[x]=i;
//		printf("|%d:[%d,%d]\n",x,l[x],r[x]);
	}
	for(int i=0;i<=h+1;i++){
		L[i]=h+1,R[i]=0;
		if(lst[i]==0)L[i]=R[i]=i; 
		if(lst[i-1]&&lst[i]<lst[i-1]){
			L[i]=min(L[i],l[i-1]);
			R[i]=max(R[i],r[i-1]);
		}
		if(lst[i+1]&&lst[i]<lst[i+1]){
			L[i]=min(L[i],l[i+1]);
			R[i]=max(R[i],r[i+1]);
		}
//		printf("%d:[%d,%d]\n",i,L[i],R[i]);
		if(L[i]&&L[i]<=R[i]&&R[i]<=h)update(L[i],R[i]);
	}
	for(int i=1;i<=h;i++)nxt[i][0]=query(i)+1;//,printf("nxt[%d][%d]=%d\n",i,0,nxt[i][0]);
	for(int i=18;i>=0;i--)nxt[h+1][i]=h+1;
	for(int i=h;i>=1;i--){
		if(nxt[i][0]==i)continue;
		for(int j=1;nxt[i][j-1]&&nxt[nxt[i][j-1]][j-1]&&nxt[i][j-1]<=h;j++)
			nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	}
	scanf("%d",&q);
	for(int i=1,a,b,res,ans;i<=q;i++){
		scanf("%d%d",&a,&b);ans=h;res=0;
		for(int j=18;j>=0;j--)
			if(nxt[a][j]>a){
				if(nxt[a][j]<b+1)a=nxt[a][j],res+=(1<<j);
				else ans=min(ans,res+(1<<j));
			}
		printf("%d\n",ans);
	}
	return 0;
}