区间询问倍增思想

例题一：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。

 输入：

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

输出：

1.  
   INF
2.  
   0
3.  
   2

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

代码：

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   #define sc(x) scanf("%d",&x)
4.  
   #define sl(x) scanf("%lld",&x)
5.  
   #define ll long long
6.  
   #define pb push_back
7.  
   #define PII pair<int,int>
8.  
   const int Max=2e5 10;
9.  
   const int N=1e5 5;
10.  
    const int mod=1e9 7;
11.  
    int f[Max][25];
12.  
    int mi[Max][25];
13.  
    int mx[Max][25];
14.  
    int cnt=20;
15.  
    int a[Max];
16.  
    int main(){
17.  
    int n;sc(n);int m;sc(m);
18.  
    for(int i=1;i<=n;i ) sc(a[i]);
19.  
    for(int i=1;i<=n;i ){
20.  
    f[i][0]=a[i];
21.  
    mi[i][0]=a[i];
22.  
    mx[i][0]=a[i];
23.  
    }
24.  
    for(int i=1;i<=cnt;i ){
25.  
    for(int j=1;j<=n;j ){
26.  
    int past=f[j][i-1];
27.  
    f[j][i]=f[past][i-1];
28.  
    mi[j][i]=min(mi[past][i-1],mi[j][i-1]);
29.  
    mx[j][i]=max(mx[past][i-1],mx[j][i-1]);
30.  
    }
31.  
    }
32.  
    while(m--){
33.  
    int l,r,x;
34.  
    sc(l);sc(r);sc(x);
35.  
    int ans=0;
36.  
    for(int i=cnt;i>=0;i--){
37.  
    if(mi[x][i]>=l&&mx[x][i]<=r){
38.  
    x=f[x][i];
39.  
    // cout<<x<<' ';
40.  
    ans =(1<<i);
41.  
    }
42.  
    }
43.  
    if(ans<=n) cout<<ans<<endl;
44.  
    else cout<<"INF\n";
45.  
    }
46.  
    }

例题二：Problem - D - Codeforces

  输入：

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

输出：

1.  
   3
2.  
   1
3.  
   2

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

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

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

代码：

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   #define sc(x) scanf("%d",&x)
4.  
   #define sl(x) scanf("%lld",&x)
5.  
   #define ll long long
6.  
   #define pb push_back
7.  
   #define PII pair<int,int>
8.  
   const int Max=2e5 10;
9.  
   const int N=1e5 5;
10.  
    const int mod=1e9 7;
11.  
    int a[Max];
12.  
    int go[Max],nx[Max];
13.  
    int f[Max][25];
14.  
    int cnt=20;
15.  
    int main(){
16.  
    int n,m;
17.  
    sc(n);sc(m);
18.  
    for(int i=1;i<=n;i ){
19.  
    sc(a[i]);
20.  
    }
21.  
    for(int i=1;i<Max;i ){
22.  
    go[i]=Max;
23.  
    nx[i]=Max;
24.  
    }
25.  
    go[n 1]=n 1;
26.  
    for(int i=n;i>=1;i--){
27.  
    go[i]=n 1;
28.  
    int tmp=a[i];
29.  
    for(int j=2;j*j<=tmp; j){
30.  
    if(tmp%j) continue;
31.  
    go[i]=min(go[i],nx[j]);
32.  
    while(tmp%j==0) tmp/=j;
33.  
    nx[j]=i;
34.  
    }
35.  
    if(tmp>1){
36.  
    go[i]=min(go[i],nx[tmp]);
37.  
    nx[tmp]=i;
38.  
    }
39.  
    go[i]=min(go[i],go[i 1]);
40.  
    }
41.  
    for(int i=1;i<=n;i ){
42.  
    for(int j=0;j<=cnt;j ){
43.  
    f[i][j]=Max;
44.  
    }
45.  
    }
46.  
    for(int i=1;i<=n;i ){
47.  
    f[i][0]=go[i];
48.  
    }
49.  
    for(int i=1;i<=cnt;i ){
50.  
    for(int j=1;j<=n;j ){
51.  
    if(f[j][i-1]>n) break;
52.  
    f[j][i]=f[f[j][i-1]][i-1];
53.  
    }
54.  
    }
55.  
    while(m--){
56.  
    int l,r;sc(l);sc(r);
57.  
    int ans=1;
58.  
    for(int i=cnt;i>=0;i--){
59.  
    if(f[l][i]<=r){
60.  
    l=f[l][i];
61.  
    ans =(1<<i);
62.  
    }
63.  
    }
64.  
    cout<<ans<<endl;
65.  
    }
66.  
    }

这篇好文章是转载于：学新通技术网