Cod sursă (job #786283)

#include <fstream>
#include <vector>

using namespace std;

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

const int nMax=1e5;
const int sqrtn=317;

struct nume{
    int buck;///bucket-ul destinatie
    int ind;///indicele burlanului
    int pasi;
};

int n,q;
vector < nume > dest;
vector < int > v;

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

void precalc(int l, int r)
{
    for(int i=l;i<r;i++)
    {
        if(v[i]==0){
            dest[i]={0,0,1};
            continue;
        }
        int bi=i/sqrtn;
        int bdest=v[i]/sqrtn;
        if(bdest==bi){
            dest[i]=dest[v[i]];
            dest[i].pasi++;
        }
        else
            dest[i]={bdest,v[i],1};
    }
}

void inlocuire(int x, int y)
{
    int bx=x/sqrtn;
    v[x]=y;
    precalc(bx*sqrtn,min(n+1,(bx+1)*sqrtn));
}

int calcans(int x)
{
    int ret=0;
    while(x!=0){
        ret+=dest[x].pasi;
        x=dest[x].ind;
    }
    return ret;
}

void solve()
{
    int tip,a,b;
    while(q--)
    {
        cin>>tip>>a;
        if(tip==2)
        {
            cin>>b;
            inlocuire(a,b);
        }
       else
            cout<<calcans(a)<<'\n';
    }
}

int main()
{
    read();
    precalc(1,n+1);
    solve();
    return 0;
}