Cod sursă (job #786245)

#include <bits/stdc++.h>

using namespace std;

const int DIM = 1e5;

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

int nxt[1 + DIM], bucket[1 + DIM];
int nxt_out[1 + DIM]; // next out of bucket
int dist_out[1 + DIM]; // distance out of bucket

void read( int &n, int &q ) {
  fin >> n >> q;
  for ( int i = 1; i <= n; ++i ) {
    fin >> nxt[i];
  }
}

void init( int n ) { 
  int bsize = sqrt(n);
  for ( int i = 1; i <= n; ++i ) {
    bucket[i] = (i - 1) / bsize + 1;
    int j = i;
    while ( bucket[i] == bucket[j] ) {
      ++dist_out[i];
      j = nxt[j];
    }
    nxt_out[i] = j;
  }
}

void repair_bucket( int n, int x, int bk ) {
  while ( x <= n && bucket[x] == bk ) {
    if ( bucket[nxt[x]] == bk ) {
      dist_out[x] = dist_out[nxt[x]] + 1;
      nxt_out[x] = nxt_out[nxt[x]];
    }
    ++x; 
  }
}

void update( int n, int x, int y ) {
  if ( bucket[y] != bucket[x] ) {
    nxt_out[x] = y;
    dist_out[x] = 1;
  }
  nxt[x] = y;
  repair_bucket(n, x, bucket[x]);  
}

int query( int x ) {
  int dist = 0;
  while ( x ) {
    dist += dist_out[x];
    x = nxt_out[x];
  }
  return dist;
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, q, x, y, type;
  
  read(n, q);
  init(n);
  while ( q-- ) {
    fin >> type >> x;
    if ( type == 2 ) {
      fin >> y;
      update(n, x, y);
    } else {
      fout << query(x) << "\n";
    }
  }
  fin.close();
  fout.close();
  return 0;
}