Cod sursă (job #786383)

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

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

int n,q,marime;
struct burlane{
    int dest,sar,urm;
} v[101001];

void update_secv(int poz,int start){
    int i,sfa=start+marime,next;
    if(!poz) poz=1;
    for(i=poz;i<sfa;i++){
        next=v[i].dest;
        if(next<start){
            v[i].sar=1;
            v[i].urm=next;
        }else{
            v[i].sar=1+v[next].sar;
            v[i].urm=v[next].urm;
        }

    }

}

void update(int poz,int poz_noua){
    v[poz].dest=poz_noua;
    update_secv(poz,poz/marime*marime);
}

int query(int poz){
    int rasp=0;
    while(poz){
        rasp+=v[poz].sar;
        poz=v[poz].urm;
    }
    return rasp;
}

void init(){
    int i;
    n++;
    marime=sqrt(n);
    for(i=0;i<(n-1)/marime+1;i++){
        update_secv(i*marime,i*marime);
    }
}

int main()
{
    int i,cer,a,b;
    cin>>n>>q;
    for(i=1;i<=n;i++){
        cin>>v[i].dest;
    }
    init();
    for(i=0;i<q;i++){
        cin>>cer;
        if(cer==1){
            cin>>a;
            cout<<query(a)<<"\n";
        }else{
            cin>>a>>b;
            update(a,b);
        }
    }
    return 0;
}