区间询问【倍增思想】

例题一：F-瓜瓜的跳棋_浙江农林大学第二十三届程序设计竞赛（同步） (nowcoder.com)

题目描述

瓜瓜有一个 1×n 的条状棋盘，从左到右的位置编号是 1,⋯,n。每个位置上都有一个数字 ai​，表示位置 iii 能跳到的下一个位置是 ai​。

瓜瓜会进行 m 次游戏，每次游戏给定一个起始位置 x 和允许跳跃的区间[l,r]，瓜瓜只能在该区间内跳跃。瓜瓜想知道每轮游戏最多跳几次？

输入描述:

第一行有两个正整数 n,m，其1⩽n,m⩽2×10^5。

第二行有 n 个正整数 ai​，其中 1⩽ai​⩽n。

接下来 m 行，每行有三个正整数 l,r,x，表示允许跳跃的区间和起始位置，其中 1⩽l,r,x⩽n保证 l⩽x⩽r。

输出描述:

输出共 m 行，每行有一个数字，表示跳跃的次数。如果能永远跳跃，则输出 INF。

 输入：

6 3
2 4 2 5 3 1
2 5 2
5 6 6
3 5 4

输出：

INF
0
2

思路：考虑倍增。维护每个点跳 2^i 次后的目标值、沿途经过坐标的最小最大值，这样即可 O(log⁡n) 的回答跳 k 次是否合法。

代码：

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
#define PII pair<int,int>
const int Max=2e5+10;
const int N=1e5+5;
const int mod=1e9+7;
int f[Max][25];
int mi[Max][25];
int mx[Max][25];
int cnt=20;
int a[Max];
int main(){
	int n;sc(n);int m;sc(m);
	for(int i=1;i<=n;i++) sc(a[i]);
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
		mi[i][0]=a[i];
		mx[i][0]=a[i];
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=n;j++){
			int past=f[j][i-1];
			f[j][i]=f[past][i-1];
			mi[j][i]=min(mi[past][i-1],mi[j][i-1]);
			mx[j][i]=max(mx[past][i-1],mx[j][i-1]);
		}
	}
	while(m--){
		int l,r,x;
		sc(l);sc(r);sc(x);
		int ans=0;
		for(int i=cnt;i>=0;i--){
			if(mi[x][i]>=l&&mx[x][i]<=r){
				x=f[x][i];
				// cout<<x<<' ';
				ans+=(1<<i);
			}
		}
		if(ans<=n) cout<<ans<<endl;
		else cout<<"INF\n";
	}
}

例题二：Problem - D - Codeforces

  输入：

6 3
2 3 10 7 5 14
1 6
2 4
3 5

输出：

3
1
2

可以证明，用贪心的方法，对于每个开始数找一个最大区间作为划分，接着这个区间后的第一个数最为新区间的第一个数即可得到最优解（最少划分）。

预处理方法为倒序处理，定义数组go[i]为下标i ii跳转到的下一个区间第一个数的下标，当处理第i ii个数的时候，遍历这个数的所有质因子，找到有这个因子的下一个位置，更新为go[i]=min(go[i],nx[j])，同时更新nx[j]。

有了以上跳转数组之后，考虑l o g ( n ) log(n)log(n)的方法去跳转遍历区间，用到倍增方法（有一定单调性）。

代码：

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
#define PII pair<int,int>
const int Max=2e5+10;
const int N=1e5+5;
const int mod=1e9+7;
int a[Max];
int go[Max],nx[Max];
int f[Max][25];
int cnt=20;
int main(){
	int n,m;
	sc(n);sc(m);
	for(int i=1;i<=n;i++){
		sc(a[i]);
	}
	for(int i=1;i<Max;i++){
		go[i]=Max;
		nx[i]=Max;
	}
	go[n+1]=n+1;
	for(int i=n;i>=1;i--){
		go[i]=n+1;
		int tmp=a[i];
		for(int j=2;j*j<=tmp;++j){
			if(tmp%j) continue;
			go[i]=min(go[i],nx[j]);
			while(tmp%j==0) tmp/=j;
			nx[j]=i;
		}
		if(tmp>1){
			go[i]=min(go[i],nx[tmp]);
			nx[tmp]=i;
		}
		go[i]=min(go[i],go[i+1]);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=cnt;j++){
			f[i][j]=Max;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][0]=go[i];
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=n;j++){
			if(f[j][i-1]>n) break;
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	while(m--){
		int l,r;sc(l);sc(r);
		int ans=1;
		for(int i=cnt;i>=0;i--){
			if(f[l][i]<=r){
				l=f[l][i];
				ans+=(1<<i);
			}
		}
		cout<<ans<<endl;
	}
}