Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

顶一下,非常想弄清楚线段树,请诸位帮个忙

Posted by hhhh at 2006-08-29 08:24:13 on Problem 2828
In Reply To:第一个线段树程序就不知道哪里错了,麻烦诸位大牛帮帮忙,谢谢。 Posted by:hhhh at 2006-08-28 17:02:32
> #include<iostream.h>
> 
> int B[400002],E[400002],C[400002];     //分别表示线段起点,终点,线段内1的个数
> int person[200000][2];                 //进入队中的人
> int result[200001];                    //结果序列
> 
> void Init(int begin,int end,int v)      //初始化线段树
> {
> 	if(begin==end)                      //叶子
> 	{
> 		B[v]=begin;
> 		E[v]=end;
> 		C[v]=1;
> 	}
> 	else                         
> 	{
> 		B[v]=begin;
> 		E[v]=end;
> 		C[v]=end-begin+1;
> 		Init(begin,(begin+end)/2,2*v);
> 		Init((begin+end)/2+1,end,2*v+1);
> 	}
> }
> 
> void change(int count,int value,int v) //用每个进入队伍的人调整线段树
> {
> 	C[v]--;
> 	if(B[v]==E[v])                     
> 	{
> 		result[B[v]]=value;
> 		return;
> 	}
> 	if(C[2*v]>count)
> 	{
> 		change(count,value,2*v);
> 	}
> 	else
> 	{
> 		change(count-C[2*v],value,2*v+1);
> 	}
> }
> int main()
> {
> 	int n,i;
> 	while(cin>>n)
> 	{
> 		Init(1,n,1);
> 		for(i=0;i<n;i++)
> 		{
> 			cin>>person[i][0]>>person[i][1];
> 		}
> 		for(i=n-1;i>=0;i--)
> 		{
> 			change(person[i][0],person[i][1],1);
> 		}
> 		for(i=1;i<n;i++)
> 		{
> 			cout<<result[i]<<' ';
> 		}
> 		cout<<result[i]<<endl;
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator