poj 2828 Buy Tickets(線分木単点更新)

http://poj.org/problem?id=2828
タイトル:
n人がいて、一人一人がvalueに対応して、それらは順番に自分が挿入したい位置(0から)に挿入して、最後のキューの状態がどのようなものかを聞きます.
 
題意を読んだ後、線分樹でどうするか思いもよらず、単点更新しか知らなかった.人の考えを見て、線分の木に逆順に挿入すべきだと分かった.最後の人は必ずその位置にいることができるので、オンラインセグメントツリーでその位置を見つけて削除します.つまり、最後から2番目の人の位置選択は最後の人の位置とは関係なく、一人一人の最後の位置を確定することができます.最後の人まで操作を繰り返します.
線分ツリーで特定の人の位置が単一の更新と類似している場合、1つの区間内で削除されていない(すなわち無視されていない)数字の個数を現在探している位置posと比較し、posが小さい場合は左の区間を更新し、そうでない場合は右の区間を更新します.
この問題はpoj 2182と似ています.

#include <stdio.h>
#include <string.h>

const int maxn = 200001;

struct line
{
	int l;
	int r;
	int len;//      
}tree[4*maxn];

int n;
int ans[maxn];

//  
void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].len = r-l+1;

	if(l == r) return;

	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

void update(int v, int posi, int vali)
{
	tree[v].len--;//     1，    posi  
	if(tree[v].l == tree[v].r)
	{
		ans[tree[v].l] = vali;
		return;
	}

	if(posi < tree[v*2].len)
		update(v*2,posi,vali);
	else update(v*2+1,posi - tree[v*2].len,vali);
}

int main()
{
	int pos[maxn],val[maxn];
	while(~scanf("%d",&n))
	{
		build(1,0,n-1);
		for(int i = 0; i < n; i++)
			scanf("%d %d",&pos[i],&val[i]);

		for(int i = n-1; i >= 0; i--)	//    
		{
			update(1,pos[i],val[i]);
		}

		for(int i = 0; i < n-1; i++)
			printf("%d ",ans[i]);
		printf("%d
",ans[n-1]);

	}
	return 0;
}