poj2828（线段树单点更新）

题意不说了。思路是将人倒叙插入，线段树各个区间的值代表前面有多少个空位。

#include <stdio.h>  
#include <iostream>  
#include <algorithm>  
#include <string.h>  
#include <string>  
#include <queue>  
#include <stack>  
#include <math.h>  
#include <map>  
#include <vector>  
#define LL __int64  
using namespace std;  
  
const int maxn=200005; 

int sum[maxn*4];
int num[maxn*4];
int p[maxn],v[maxn];

void build(int o,int L,int R)       //建树过程  
{  
    if(L==R)  
    {  
        sum[o]=1;                   //初始都为1  
        return;  
    }  
    int M=(L+R)>>1;     
    build(o*2,L,M);                 //左子树  
    build(o*2+1,M+1,R);             //右子树  
    sum[o]=sum[o*2+1]+sum[o*2];     //当前区间的和为左右子树的和  
} 

void update(int o,int p,int w,int L,int R)      
{
	if(L==R && sum[o]==1)							//1表示这个位置没有人
	{
		sum[o]--;
		num[L]=w;
		return;
	}
	int M=(L+R)>>1;
	if(p>sum[o*2])
		update(o*2+1,p-sum[o*2],w,M+1,R);			//注意这里p要减去左子树的值
	else
		update(o*2,p,w,L,M);
	sum[o]=sum[o*2]+sum[o*2+1];
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		build(1,1,n);
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&p[i],&v[i]);
			p[i]++;
		}
		for(int i=n-1;i>=0;i--)
		{
			update(1,p[i],v[i],1,n);
		}
		for(int i=1;i<=n;i++)
		{
			printf("%d",num[i]);
			if(i==n)
				printf("\n");
			else
				printf(" ");
		}
	}
	return 0;
}

poj2828（线段树单点更新）,布布扣,bubuko.com

poj2828（线段树单点更新）

原文：http://blog.csdn.net/mfmy_szw/article/details/21192727