joi report

report.cpp

#include<cstdio>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;

const int MX = 100005, x18 = 18, n18 = 1<<x18, INF = 100000000;

int n;
int head[MX], next[MX], to[MX], g;
int par[MX];
int gr[MX], k;
bool rb[MX];

bool nu(int v){ // 頂点の番号付け
    if(gr[v] == -1){
		gr[v] = k;
		rb[v] = true;
		return true;
	}
	if(gr[v]) return false;
	
	gr[v] = -1;
	if(nu(par[v])){
		if(gr[v] == -1){
			gr[v] = k;
			return true;
		} else {
			k++;
			return false;
		}
	}
	
	gr[v] = k++;
	return false;
}


int s[MX], t[MX], h;// 影響を及ぼす範囲(s~t)

void dfs(int v){
	s[v] = h++;
	for(int i = head[v]; i != -1; i = next[i]) dfs(to[i]);
	t[v] = h++;
}

int bit[n18+1];
void add(int i){
	while(i <= n18){
		bit[i]++;
		i += i&-i;
	}
}

int sum(int i){
	int x = 0;
	while(i){
		x += bit[i];
		i -= i&-i;
	}
	return x;
}


int main(){
	scanf("%d",&n);
	
	rep(i,n){
		scanf("%d",&par[i]);
		par[i]--;
		head[i] = -1;
	}
	
	k = 1;
	rep(i,n) nu(i);
	
	int a, b;
	rep(i,n){
		a = gr[i]; b = gr[par[i]];
		if(a != b){ next[g] = head[b]; to[g] = a; head[b] = g++;}
	}
	
	h = 1;
	rep(i,n) if(rb[i]) dfs(gr[i]);
	
	rep(i,n){
		a = gr[i];
		printf("%d\n",sum(t[a])-sum(s[a]-1));
		add(s[a]);
	}
	
	return 0;
}