Cod sursă (job #785947)

/*
Impartim burlanele in blocuri de sqrt (n). Pentru fiecare burlan calculam burlanul din blocul urmator si distanta pana la acesta.
*/
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("burlane.in");
ofstream fout ("burlane.out");
struct burlan
{
    int capat; ///capatul burlanului
    int dist; ///distanta pana la urmatorul bloc de sqrt (n)
    int nxt; ///prima pozitie din urmatorul bloc
};
burlan v[100001];
int n,q,buc_size;
void read ()
{
    fin>>n>>q;
    buc_size=sqrt (n);
    for (int i=1; i<=n; i++)
        fin>>v[i].capat;
}
int get_sol (int pos)
{
    int sol=0;
    while (pos>0) ///mergem de maxim sqrt (n)
    {
        sol+=v[pos].dist;
        pos=v[pos].nxt;
    }
    return sol;
}
void update (int pos)
{
    int capat=v[pos].capat;
    int buc_pos=pos/buc_size;
    int buc_capat=capat/buc_size;
    if (buc_pos!=buc_capat||capat==0) ///urmatorul burlan e in alt bloc
    {
        v[pos].nxt=capat;
        v[pos].dist=1;
    }
    else ///luam raspunsul de la urmatorul burlan
    {
        v[pos].nxt=v[capat].nxt;
        v[pos].dist=v[capat].dist+1;
    }
}
void solve_qry ()
{
    int qty,pos,capat;
    for (int i=1; i<=n; i++)
        update (i);
    for (int i=0; i<q; i++)
    {
        fin>>qty; ///tipul intrebarii
        if (qty==1)
        {
            fin>>pos;
            fout<<get_sol (pos)<<"\n";
        }
        else
        {
            fin>>pos>>capat;
            v[pos].capat=capat;
            int buc_pos=pos/buc_size;
            int l=pos,r=(buc_pos+1)*buc_size-1;
            for (int j=l; j<=r; j++)
                update (j);
        }
    }
}
int main()
{
    read ();
    solve_qry ();
    return 0;
}