程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2828 線段樹插孔處理

poj 2828 線段樹插孔處理

編輯:C++入門知識

poj 2828 線段樹插孔處理


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

 

4
0 77
1 51
1 33
2 69
第一步 77

 

第二部 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;
}

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved