Cod sursă (job #786791)

#include <fstream>
#include <math.h>
#define MAXN 101005
using namespace std;

ifstream cin("burlane.in");
ofstream cout("burlane.out");

int n, q, blk_size;

struct burlan
{
    int dest, jumps, next;
};

burlan b[MAXN];

void citire()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>b[i].dest;
}

void update_range(int pos, int blk_start)
{
    int blk_end = blk_start + blk_size;
    if(pos == 0) pos = 1;
    for(int i=pos; i<blk_end; i++)
    {
        int k=b[i].dest;
        if(k<blk_start)
        {
            b[i].jumps = 1;
            b[i].next = k;
        }
        else
        {
            b[i].jumps = b[k].jumps + 1;
            b[i].next = b[k].next;
        }
    }
}

void init()
{
    n++;
    blk_size = sqrt(n);
    int nr_blk = (n-1)/blk_size + 1;
    for(int i=0;i<nr_blk;i++)
    {
        int first = i * blk_size;
        update_range(first,first);
    }
}

void update(int pos, int n_dest)
{
    b[pos].dest = n_dest;
    int blk_start = pos/blk_size * blk_size;
    update_range(pos, blk_start);
}

void solve(int pos)
{
    int ans=0;
    while(pos)
    {
        ans+=b[pos].jumps;
        pos=b[pos].next;
    }
    cout<<ans<<'\n';
}

void queries()
{
    int t, pos, n_dest;
    for(int i=1;i<=q;i++)
    {
        cin>>t>>pos;
        if(t==1)
            solve(pos);
        else
        {
            cin>>n_dest;
            update(pos, n_dest);
        }
    }
}

int main()
{
    citire();
    init();
    queries();
    return 0;
}