Cod sursă (job #786035)

#include <iostream>
#include <fstream>

using namespace std;

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

const int Nmax=1e5+5, SqrtNmax=317;

int n, q, t, x, y;
int nxt[Nmax], steps[Nmax], ext[Nmax];

inline void update_pos(int l, int pos){
    if (nxt[pos]<l){
        steps[pos]=1;
        ext[pos]=nxt[pos];
    }
    else{
        steps[pos]=steps[nxt[pos]]+1;
        ext[pos]=ext[nxt[pos]];
    }
}

int main()
{
    fin>>n>>q;
    for (int i=1; i<=n; i++)
        fin>>nxt[i];

    // precalculate chunks
    int l=0, r=SqrtNmax-1;
    for (int i=1; i<=n; i++){
        if (i==r){
            r+=SqrtNmax;
            l+=SqrtNmax;
        }
        // number of steps till I exit this chunk and where i exit
        update_pos(l, i);
    }

    // answer queries
    while (q--){
        fin>>t;
        if (t==1){
            fin>>x;
            int sol=0;
            while (x!=0){
                sol+=steps[x];
                x=ext[x];
            }
            fout<<sol<<'\n';
        }
        else{
            fin>>x>>y;

            nxt[x]=y;
            int ind_chunk=x/SqrtNmax;
            int l=ind_chunk*SqrtNmax;
            int r=l+SqrtNmax-1;

            int i=l;
            if (ind_chunk==0) // nu il luam pe 0 daca suntem in primul chunk
                i++;

            while (i<=r){
                update_pos(l, i++);
            }
        }
    }

    return 0;
}