HDU.1556 Color the ball (线段树 区间更新 单点查询)
题意分析
注意一下pushdown 和 pushup
模板类的题还真不能自己套啊，手写一遍才行
代码总览
#include <bits/stdc++.h>
#define nmax 200000
using namespace std;
struct Tree{
int l,r,val;
int lazy;
int mid(){
return (l+r)>>1;
}
};
Tree tree[nmax<<2];
int num[nmax<<2];
void PushUp(int rt)
{
tree[rt].val = tree[rt<<1].val + tree[rt<<1|1].val;
}
void PushDown(int rt)
{
if(tree[rt].lazy){
tree[rt<<1].lazy += tree[rt].lazy;
tree[rt<<1|1].lazy += tree[rt].lazy;
tree[rt<<1].val += tree[rt].lazy ;
tree[rt<<1|1].val +=tree[rt].lazy;
tree[rt].lazy = 0;
}
}
void Build(int l, int r, int rt)
{
tree[rt].l = l; tree[rt].r = r;
tree[rt].val = tree[rt].lazy = 0;
if(l == r){
return;
}
Build(l,tree[rt].mid(),rt<<1);
Build(tree[rt].mid()+1,r,rt<<1|1);
PushUp(rt);
}
void UpdatePoint(int val, int pos, int rt)
{
if(tree[rt].l == tree[rt].r){
tree[rt].val+=val;
return;
}
PushDown(rt);
if(pos<= tree[rt].mid()) UpdatePoint(val,pos,rt<<1);
else UpdatePoint(val,pos,rt<<1|1);
PushUp(rt);
}
void UpdateInterval(int val, int l, int r, int rt)
{
if(tree[rt].l >r || tree[rt].r < l) return;
if(tree[rt].l >= l && tree[rt].r <= r){
tree[rt].val+= val;
tree[rt].lazy+= val;
return;
}
PushDown(rt);
UpdateInterval(val,l,r,rt<<1) ;
UpdateInterval(val,l,r,rt<<1|1);
PushUp(rt);
}
int Query(int l,int r,int rt)
{
if(l>tree[rt].r || r<tree[rt].l) return 0;
PushDown(rt);
if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;
else return Query(l,r,rt<<1) +Query(l,r,rt<<1|1);
}
int T,N,a,b;
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&N) != EOF && N){
Build(1,N,1);
for(int i = 0;i<N;++i){
scanf("%d %d",&a,&b);
UpdateInterval(1,a,b,1);
}
for(int i = 1;i<=N;++i){
if(i == 1) printf("%d",Query(i,i,1));
else printf(" %d",Query(i,i,1));
}
printf("\n");
}
return 0;
}