Cod sursă (job #786170)

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream f("burlane.in");
ofstream g("burlane.out");

const int NMAX = 101001;///+sqrt in caz ca depaseste

struct burlane
{
    int jumps,///sarituri pana in blockul urmator
        next,///pointer spre primul burlan in care ajunge dupa ce iese din block
        dest;///destinatia urmatoare
};

burlane v[NMAX];
int n, m, q;
int nr_blocks, block_sz;

void update_all(int start, int fin, int poz)
{
    for(int i = poz; i <= fin; i++)
    {
        int d = v[i].dest;
        if(d < start)
        {
            v[i].next = d;
            v[i].jumps = 1;
        }
        else
        {
            v[i].next = v[d].next;
            v[i].jumps = v[d].jumps + 1;
        }
    }
}

void update(int poz, int new_dest)
{
    v[poz].dest = new_dest;
    int nr_bl = (poz - 1) / block_sz;
    int start = nr_bl * block_sz + 1;
    update_all(start, start + block_sz - 1, poz);
}

int query(int poz)
{
    int sol = 0;
    while(poz > 0)
    {
        sol += v[poz].jumps;
        poz = v[poz].next;
    }
    return sol;
}

void ReadAndInit()
{
    f >> n >> q;
    ///
    block_sz = sqrt(n);
    nr_blocks = n / block_sz + 1;
    ///
    for(int i = 1; i <= n; i++)
    {
        f >> v[i].dest;
        update(i, v[i].dest);
    }

}

void ReadQ_solve()
{
    int cer, x, y;
    while(q--)
    {
        f >> cer >> x;
        if(cer == 1)
            g << query(x) << '\n';
        else
        {
            f >> y;
            update(x, y);
        }
    }
}

int main()
{
    ReadAndInit();
    ReadQ_solve();
    return 0;
}