POJ 2828線分樹単点更新、単点照会

九野のブログ、転載は出所を明記してください:http://blog.csdn.net/acmmmm/article/details/11971839
件名:
n個人
n行:a,bはbという人がaの位置に割り込むという意味です.
最後の列の順番を聞きます.
考え方:
最後の一人から、割り込みの過程を表します.
bをa番目の空いている席に置いてください.
 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <math.h>
#include <queue>
#define N  201000
#define M 2000100
#define inf64 0x7ffffff
#define inf 0x7ffffff
#define ll int
#define L(x) x<<1
#define R(x) x<<1|1
#define Mid(x,y) (x+y)>>1
using namespace std;
inline ll Min(ll a,ll b){return a>b?b:a;}
inline ll Max(ll a,ll b){return a>b?a:b;}

ll len,maxdeep,Query;
struct node{
	int l,r;
	ll sum,num;//sum        ，num           
}tree[N*4];

void build(int l,int r,int id){
	tree[id].l = l;	tree[id].r = r;
	tree[id].num = r-l+1;
	if(l==r) return ;
	int mid = Mid(l,r);
	build(l,mid,L(id));	 build(mid+1,r,R(id));

}

void updata_point(int pos,int id, ll data){//    
	if(tree[id].l == tree[id].r)
	{	
		tree[id].num--;
		tree[id].sum = data;
		return ; 
	}
	tree[id].num--;

	if( tree[ L(id) ].num > pos) updata_point(pos,L(id),data);
	else updata_point(pos-tree[L(id)].num,R(id),data);

}

ll query_point(int pos, int id){ //     sum
	if(tree[id].l == pos && pos == tree[id].r)
		return tree[id].sum ;

	int mid = Mid(tree[id].l, tree[id].r);

	if(pos <= mid) 		return query_point(pos, L(id));
	else				return query_point(pos, R(id));

}

struct quenode{
	int a, b;
}qq[N];
int main(){
	int n,a,b,i;
	while(~scanf("%d",&n)){
		build( 1, n, 1);

		for(i=0;i<n;i++)
			scanf("%d %d",&qq[i].a,&qq[i].b);

		for(i=n-1;i>=0;i--)
		{

			updata_point( qq[i].a, 1, qq[i].b);

		}
		for(i=1;i<n;i++)printf("%d ",query_point(i,1));
		printf("%d
",query_point(i,1));
	}
	return 0;
}