vx5YS2 - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define canuc12k ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, a[300005];
int seg[1500005];
int spr[20][300005];
int high[300005];
int elt[300005], sz[300005], stt[300005];
vector<int> g[300005];
int u, cnt=1;
int dfs(int a, int par){
	spr[0][a]=par;
//	cout<<a<<"\n";
	elt[cnt]=a;
	stt[a]=cnt;
	cnt++;
	for(auto i : g[a]){
		if(i==par) continue;
		high[i]=high[a]+1;
		sz[a]+=dfs(i,a);
	}
	return sz[a]+1;
}
void update(int pos, int l, int r, int u, int val){
	if(l>u || r<u) return;
	if(l==r){
		seg[pos]=val;
		return;
	}
	int mid=(l+r)>>1;
	update(pos*2, l, mid, u, val);
	update(pos*2+1, mid+1, r, u, val);
	seg[pos]=max(seg[pos*2], seg[pos*2+1]);
}
int get(int pos, int l, int r, int u, int v){
	if(l>v || r<u) return 0;
	if(l>=u && r<=v) return seg[pos];
	int mid=(l+r)>>1;
	return max(get(pos*2, l, mid, u, v), get(pos*2+1, mid+1, r, u, v));
}
int main(){
	canuc12k

	cin>>n;
	cin>>a[1];
	for(int i=2;i<=n+1;i++){
		cin>>a[i]>>u;
		g[u+1].pb(i);
		g[i].pb(u+1);
	}
	n++;
	dfs(1,1);
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			spr[i][j]=spr[i-1][spr[i-1][j]];
		}
	}

    update(1, 1, n, stt[1], a[1]);

	for(int i=2;i<=n;i++){
        int x = i;
        for(int k = log2(high[i]); k >= 0; k--) {
            int cha = spr[k][x];
            int val = get(1, 1, n, stt[cha], stt[cha]+sz[cha]);
            if(val < a[i]) x = spr[k][x];
        }

        cout << high[i] - high[x] <<"\n";

		update(1, 1, n, stt[i], a[i]);
	}
}