#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;
}

• 顶一下,非常想弄清楚线段树,请诸位帮个忙 (1181) hhhh 2006-08-29 08:24:13
  • ft..原来是数组开小了，开到600000就过了，想不通！！ (48) hhhh 2006-08-29 21:55:14
    • 不知道，我们当时也开2*n, RE (21) wywcgs 2006-08-29 22:21:16
      • 要大于等于n的最小2幂才安全吧... (27) ArXoR 2006-08-29 22:24:26
        • 哦，是哈~大脑进水了 (0) wywcgs 2006-08-29 22:25:08
          • 静态的也是吗？好象是2*n啊，就是普通的2叉树嘛。 (0) hhhh 2006-08-29 22:27:03
            • 那是节点总数不是下标上限 (0) wywcgs 2006-08-29 22:44:20
              • 明白了，不是平衡二叉树，事实上下标开到3*n就没问题了，对吧？ (0) hhhh 2006-08-30 14:32:45
          • 啊.是2n不是n...大脑同进水了 (0) ArXoR 2006-08-29 22:27:38
      • 本人的第一个线段树程序啊！看了lirui的文章学的方法。目前只会静态的5555...... (41) hhhh 2006-08-29 22:24:59