Cod sursă (job #786546)

#include <bits/stdc++.h>
#define MAX 100005

using namespace std;

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

struct info
{
    int parent;
    int nrblock;
    int jumps;
    int next;
}etaj[MAX];
int N,Q;
int BLOCK_SIZE;

void read()
{
    fin>>N>>Q;
    int i;
    for(i=1;i<=N;++i)
        fin>>etaj[i].parent;
}

void update_range(int pos)
{
    int block=etaj[pos].nrblock;
    int block_end=min(block*BLOCK_SIZE,N);
    int block_start=(block-1)*BLOCK_SIZE+1;
    int i;
    for(i=pos;i<=block_end;++i)
    {
        int parent=etaj[i].parent;
        if(parent<block_start)
        {
            etaj[i].next=parent;
            etaj[i].jumps=1;
        }
        else
        {
            etaj[i].next=etaj[parent].next;
            etaj[i].jumps=etaj[parent].jumps+1;
        }
    }
}

void init()
{
    BLOCK_SIZE=sqrt(N);
    int i;
    for(i=1;i<=BLOCK_SIZE;++i)
        etaj[i].nrblock=1;
    for(i=BLOCK_SIZE+1;i<=N;++i)
        etaj[i].nrblock=etaj[i-BLOCK_SIZE].nrblock+1;
    for(i=1;i<=etaj[N].nrblock;++i)
        update_range((i-1)*BLOCK_SIZE+1);
}

void update(int x,int y)
{
    etaj[x].parent=y;
    update_range(x);
}

int query(int x)
{
    int jumps=0;
    while(x)
    {
        jumps+=etaj[x].jumps;
        x=etaj[x].next;
    }
    return jumps;
}

void solve()
{
    int i;
    for(i=1;i<=Q;++i)
    {
        int task;
        fin>>task;
        if(task==1)
        {
            int x;
            fin>>x;
            fout<<query(x)<<'\n';
        }
        else
        {
            int x,y;
            fin>>x>>y;
            update(x,y);
        }
    }
}

int main()
{
    read();
    init();
    solve();
    return 0;
}