题意：区间修改序列值，最后输出。
//hdu1166
#include<iostream>
#include<cstdio>
#include<cstring>
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
using namespace std;
const int maxn=;
int sum[maxn<<],add[maxn<<];//sum求和，add懒惰标记
int a[maxn]={},n=;//存原数组数据下标[1,n]
//更新节点信息，这里是求和
void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
//建树
void pushdown(int rt,int ln,int rn)
{//ln,rn为左子树，右子树的数量
if(add[rt])//下推标记
{
add[rt<<]+=add[rt];
add[rt<<|]+=add[rt];
sum[rt<<]+=add[rt]*ln;
sum[rt<<|]+=add[rt]*rn;
add[rt]=;//清除本节点标记
}
}
void build(int l,int r,int rt)//rt表示当前节点编号
{
if(l==r)
{
sum[rt]=a[l];
return;
}
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
pushup(rt);
} //点修改a[L]+=c;
void update(int L,int c,int l,int r,int rt)
{//l,r当前节点区间，rt当前节点编号，L需要修改的节点，c修改的值
if(l==r)
{
sum[rt]+=c;
return;
}
int m=(l+r)>>;
//根据条件判断调用左子树还是右子树
if(L<=m)
update(L,c,l,m,rt<<);
else
update(L,c,m+,r,rt<<|);
pushup(rt);//子节点更新，所以本节点也需要更新
} //区间修改a[r,t]+=c
void update_(int L,int R,int c,int l,int r,int rt)
{//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
if(L<=l&&r<=R)//遍历的区间在操作区间内
{
sum[rt]+=c*(r-l+);
add[rt]+=c;
return;
}
int m=(l+r)>>;
pushdown(rt,m-l+,r-m);
if(L<=m)
update_(L,R,c,l,m,rt<<);
if(R>m)
update_(L,R,c,m+,r,rt<<|);
pushup(rt);
} //区间查询 a[l,r]的和
//下推标记函数
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int m=(l+r)>>;
pushdown(rt,m-l+,r-m);
int ans=;
if(L<=m)
ans+=query(L,R,l,m,rt<<);
if(R>m)
ans+=query(L,R,m+,r,rt<<|);
return ans;
} int main()
{
int n;
while(scanf("%d",&n)&&n)
{
memset(sum,,sizeof(sum));
memset(add,,sizeof(add));
build(,n,);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
update_(a,b,,,n,);//区间修改 }
for(int i=;i<=n;i++)
{
if(i!=)
printf(" ");
printf("%d",query(i,i,,n,));//因为查询单点所以是i到i
}
printf("\n");
}
return ;
}