segmenttree

POJ 2104 を
http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/index.php?2010%2F%C6%FC%C4%F8%C9%BD%2F01-17
のスライドを参考にして解こうとしたけどうまくできなかった
コードの残骸だけ載せておく(一部分)

void init(int d, int l, int r){
	if(l == r-1) return;
	int n=r-l;

	//solve median
	P a[n];
	for(int i = 0; i < n; i++)
		a[i] = P(tree[d][l+i],i);
	sort(a,a+n);
	int m=a[n/2].first;

	int t=0;
	//printf("d=%d l=%d r=%d m=%d\n", d,l,r,m);
	for(int i=l;i<r;i++){
		if(tree[d][i] < m)
			S[d][i] = ++t;
		else
			S[d][i] = t;
	}
	int index[n];
	bool used[n];
	fill(used, used+n, false);
	for(int i=0;i<n;i++){
		index[i] = a[i].second;
	}
	sort(index, index+n/2);
	sort(index+n/2, index+n);
	for(int i=0;i<n;i++){
		tree[d+1][l+i] = tree[d][l+index[i]];
	}
	init(d+1,l,l+n/2);
	init(d+1,l+n/2,r);
	return;
}