题目描述

难度分:$2700$

输入$n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$，数组下标从$1$ 开始。
然后输入$m$个操作，输入格式如下：

1. 0 p v表示把$a[p]$改成$v$。
2. 1 p表示从位置$p$开始向右跳，每次更新$p=p+a[p]$，直到$p \gt n$。输出最后一次$\leq n$的位置，以及当$p \gt n$ 时跳了多少次。

其中$(1 \leq p,v \leq n)$。

输入样例

8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

输出样例

8 7
8 5
7 3

算法

分块

将整个数组分块，块的大小为$\sqrt{n}$。先预处理出几个辅助数组，$block$、$st$、$ed$、$num$、$pla$。其中$block[i]$表示$i$属于的块，$st[i]$和$ed[i]$分别为块$i$的起始和结束索引，$num[i]$表示从$i$开始跳出其所在块所需要的步数，$pla[i]$表示从$i$位置可以跳到的最终位置。

$block$，$st$，$ed$用数学方法就能预处理出来。$num$和$pla$的计算方式本质上是一个动态规划：

1. 如果$i+a[i] \gt ed[block[i]]$，那么就有$num[i]=1$，$pla[i]=a[i]+i$，表示只需要一步就能跳出去了。
2. 否则就有状态转移$num[i]=num[a[i]+i]+1$，$pla[i]=pla[a[i]+i]$。

预处理出这几个数组，对于操作$1$就可以模拟了，从$p$位置开始，每次跳往$pla[p]$。而对于操作$0$，从$p$位置开始往前递推，修改$p$所在块的$num$和$pla$值就可以了。由于进行了分块，两种操作的时间复杂度都是$O(\sqrt{n})$的。

复杂度分析

时间复杂度

分块预处理的时间复杂度为$O(n\sqrt{n})$，$m$条操作，更新和查询操作的时间复杂度都是$O(\sqrt{n})$。因此，整个算法的时间复杂度为$O((n+m)\sqrt{n})$。

空间复杂度

分块的辅助数组都是$O(n)$规模的，因此额外空间复杂度也是$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 100010;
int CHUNK;
int n, m, a[N], block[N], ed[N], st[N], num[N], pla[N];

void build(){
    CHUNK = (int)sqrt(n);
    for(int i = 1; i <= CHUNK; i++) {
        st[i] = (n / CHUNK)*(i - 1) + 1;      // 第i个块开始的位置
        ed[i] = (n / CHUNK)*i;                // 第i个块结束的位置
    }
    ed[CHUNK] = n;
    for(int i = 1; i <= CHUNK; i++){
        for(int j = st[i]; j <= ed[i]; j++) {
            block[j] = i;                     // 每个位置属于的块编号
        }
    }
    for(int i = 1; i <= CHUNK; i++) {
        for(int j = ed[i]; j >= st[i]; j--){
            if(a[j] + j > ed[i]) {
                num[j] = 1;                   // 跳出块所需要的步数
                pla[j] = a[j] + j;            // 下一步的位置
            }else {
                num[j] = num[j + a[j]] + 1;
                pla[j] = pla[j + a[j]];
            }
        }
    }
}

void query(int x) {
    int pos, step = 0;
    // 最后一次<=n的步数
    for(int i = x; i <= n; i = pla[i]) {
        step += num[i], pos = i;
    }
    // pos>n时的位置
    for(int i = pos; i <= n; i += a[i]){
        if(i + a[i] > n) {
            pos = i;
        }
    }
    printf("%d %d\n", pos, step);
}

void modify(int x, int y) {
    a[x] = y;
    int block_id = block[x];
    for(int i = x; i >= st[block_id]; i--){
        if(a[i] + i > ed[block_id]) {
            num[i] = 1;
            pla[i] = a[i] + i;
        }else {
            num[i] = num[i + a[i]] + 1;
            pla[i] = pla[i + a[i]];
        }
    }
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build();      // 分块
    for(int i = 1; i <= m; i++) {
        int t, p, v;
        scanf("%d%d", &t, &p);
        if(t == 0) {
            scanf("%d", &v);
            modify(p, v);
        }else {
            query(p);
        }
    }
    return 0;
}