Cod sursă (job #786829)

#include <iostream>
#include <fstream>
#include <cmath>
//#define fin cin
//#define fout cout

using namespace std;

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

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

int n, q, blockSize;

void updateInterval(int x, int bucketFront){
    int bucketEnd = bucketFront + blockSize - 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 build(){
    blockSize = sqrt(n + 1);
    for(int i = 0; i <= (n) / blockSize; i++)
        updateInterval(i * blockSize, i * blockSize);
}

void update(int x, int y){
    v[x].p = y;
    int bucketFront = x / blockSize * blockSize;
    updateInterval(x, bucketFront);
}

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();
    build();
    solveQueries();
    return 0;
}