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