题意:区间修改序列值,最后输出。
1 //hdu1166 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define ls l,m,rt<<1 6 #define rs m+1,r,rt<<1|1 7 using namespace std; 8 const int maxn=100005; 9 int sum[maxn<<2],add[maxn<<2];//sum求和,add懒惰标记 10 int a[maxn]={0},n=100000;//存原数组数据下标[1,n] 11 //更新节点信息,这里是求和 12 void pushup(int rt) 13 { 14 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 15 } 16 //建树 17 void pushdown(int rt,int ln,int rn) 18 {//ln,rn为左子树,右子树的数量 19 if(add[rt])//下推标记 20 { 21 add[rt<<1]+=add[rt]; 22 add[rt<<1|1]+=add[rt]; 23 sum[rt<<1]+=add[rt]*ln; 24 sum[rt<<1|1]+=add[rt]*rn; 25 add[rt]=0;//清除本节点标记 26 } 27 } 28 void build(int l,int r,int rt)//rt表示当前节点编号 29 { 30 if(l==r) 31 { 32 sum[rt]=a[l]; 33 return; 34 } 35 int m=(l+r)>>1; 36 build(l,m,rt<<1); 37 build(m+1,r,rt<<1|1); 38 pushup(rt); 39 } 40 41 //点修改a[L]+=c; 42 void update(int L,int c,int l,int r,int rt) 43 {//l,r当前节点区间,rt当前节点编号,L需要修改的节点,c修改的值 44 if(l==r) 45 { 46 sum[rt]+=c; 47 return; 48 } 49 int m=(l+r)>>1; 50 //根据条件判断调用左子树还是右子树 51 if(L<=m) 52 update(L,c,l,m,rt<<1); 53 else 54 update(L,c,m+1,r,rt<<1|1); 55 pushup(rt);//子节点更新,所以本节点也需要更新 56 } 57 58 //区间修改a[r,t]+=c 59 void update_(int L,int R,int c,int l,int r,int rt) 60 {//L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号 61 if(L<=l&&r<=R)//遍历的区间在操作区间内 62 { 63 sum[rt]+=c*(r-l+1); 64 add[rt]+=c; 65 return; 66 } 67 int m=(l+r)>>1; 68 pushdown(rt,m-l+1,r-m); 69 if(L<=m) 70 update_(L,R,c,l,m,rt<<1); 71 if(R>m) 72 update_(L,R,c,m+1,r,rt<<1|1); 73 pushup(rt); 74 } 75 76 //区间查询 a[l,r]的和 77 //下推标记函数 78 int query(int L,int R,int l,int r,int rt) 79 { 80 if(L<=l&&r<=R) 81 { 82 return sum[rt]; 83 } 84 int m=(l+r)>>1; 85 pushdown(rt,m-l+1,r-m); 86 int ans=0; 87 if(L<=m) 88 ans+=query(L,R,l,m,rt<<1); 89 if(R>m) 90 ans+=query(L,R,m+1,r,rt<<1|1); 91 return ans; 92 } 93 94 int main() 95 { 96 int n; 97 while(scanf("%d",&n)&&n) 98 { 99 memset(sum,0,sizeof(sum)); 100 memset(add,0,sizeof(add)); 101 build(1,n,1); 102 for(int i=0;i<n;i++) 103 { 104 int a,b; 105 scanf("%d%d",&a,&b); 106 update_(a,b,1,1,n,1);//区间修改 107 108 } 109 for(int i=1;i<=n;i++) 110 { 111 if(i!=1) 112 printf(" "); 113 printf("%d",query(i,i,1,n,1));//因为查询单点所以是i到i 114 } 115 printf("\n"); 116 } 117 return 0; 118 }