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

• 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