Cod sursă (job #786244)

#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;
}