poj 2828 線段樹插孔處理

poj 2828 線段樹插孔處理

給你一個數列出現的先後順序num【i】和對應數值 輸出最後排好序的對應數值，如

4
0 77
1 51
1 33
2 69

第二部 77 51

第三步 77 33 51

第四部77 33 69 51

後面先出現的位置是固定的 所以從後往前處理。 線段樹每個節點存當前區間還有多少個空位；

#include
#include
#include
using namespace std;

#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

struct node 
{
	int cont;
}tree[4*200000];
int num[200010][3],queue[200010];
int deal(int L,int R,int point)
{
	tree[point].cont=R-L+1;
	if(L==R)return 0;
	int mid=(L+R)/2;
	deal(L,mid,LL(point));
	deal(mid+1,R,RR(point));
	return 0; 	
}
int update(int L,int R,int pos,int point,int value)
{
	tree[point].cont--;
	if(L==R)
	{
		queue[L]=value;
		return 0;
	}
	int mid=(L+R)/2;
	if(pos<=tree[LL(point)].cont) update(L,mid,pos,LL(point),value);
	else update(mid+1,R,pos-tree[LL(point)].cont,RR(point),value);
	return 0;
}
int main()
{
	int n,i,j;
	while(~scanf("%d",&n))
	{
		deal(1,n,1);
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&num[i][1],&num[i][2]);
			num[i][1]++;
		}
		for(i=n;i>=1;i--)
		{   
			update(1,n,num[i][1],1,num[i][2]);
		}
		for(i=1;i<=n;i++)
		{
			if(i!=1) printf(" ");
			printf("%d",queue[i]);
		}
		printf("\n");
	}
	return 0;
}