Cod sursă (job #786825)

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("burlane.in");
ofstream fout("burlane.out");

struct burlan{
    int p, next, jumps;
}v[100001];

int n, q, blockSize;

void build(){
    v[1].next = 0, v[1].jumps = 1;
    for(int i = n; i >= 2; i--){
        int block = (i - 1) / blockSize, j = i, k = i;
        v[i].jumps = 0;
        while(j != 0 && block == (j - 1) / blockSize){
            j = v[k].p, v[i].jumps++;
            k = j;
        }
        v[i].next = j;
    }
}

void update(int x, int y){
    v[x].p = y;
    int bucketFront = x / blockSize * blockSize, bucketEnd = blockSize * (x / blockSize + 1) - 1;
    if(x == 0)
        x = 1;
    for(int i = x; i <= bucketEnd; i++){
        int j = v[i].p;
        if(j < bucketFront)
            v[i].jumps = 1, v[i].next = j;
        else
            v[i].jumps = v[j].jumps + 1, v[i].next = v[j].next;
    }
}

void query(int x){
    int rez = 0;
    while(x != 0)
        rez += v[x].jumps, x = v[x].next;
    fout << rez << "\n";
}

void readHoles(){
    fin >> n >> q;
    for(int i = 1; i <= n; i++)
        fin >> v[i].p;
}

void solveQueries(){
    int t, x, y;
    for(int i = 1; i <= q; i++){
        fin >> t >> x;
        if(t == 1)
            query(x);
        else
            fin >> y, update(x, y);
    }
}

int main(){
    readHoles();
    blockSize = int(sqrt(n));
    build();
    solveQueries();
    return 0;
}