首页 > 代码库 > HDU1556:Color the ball(简单的线段树区域更新）
HDU1556:Color the ball(简单的线段树区域更新）
http://acm.hdu.edu.cn/showproblem.php?pid=1556
Problem Description
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
Input
每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。
当N = 0，输入结束。
Output
每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
模板题，没什么好说的，搜了一下这题看见大家都是用树状数组做的，有空学一下。
#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#define N 1000010using namespace std;struct node{ int l,r,lz,w;} q[4*N];int n;void pushdown(int rt){ if(q[rt].lz) { q[rt<<1].lz+=q[rt].lz; q[rt<<1|1].lz+=q[rt].lz; q[rt<<1].w+=q[rt].lz; q[rt<<1|1].w+=q[rt].lz; q[rt].lz=0; }}void build(int l,int r,int rt){ q[rt].l=l; q[rt].r=r; q[rt].w=0; q[rt].lz=0; if(l==r) return ; int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); return ;}void update(int lf,int rf,int l,int r,int rt){ if(lf<=l&&rf>=r) { q[rt].w+=1; q[rt].lz+=1; return ; } pushdown(rt); int mid=(l+r)>>1; if(lf<=mid) update(lf,rf,l,mid,rt<<1); if(rf>mid) update(lf,rf,mid+1,r,rt<<1|1);}void query(int l,int r,int rt){ if(l==r) { if(l==1) printf("%d",q[rt].w); else printf(" %d",q[rt].w); return ; } pushdown(rt); int mid=(l+r)>>1; query(l,mid,rt<<1); query(mid+1,r,rt<<1|1); return ;}int main(){ int s1,s2; while(scanf("%d",&n)!=EOF&&n!=0) { build(1,n,1); for(int i=0; i<n; i++) { scanf("%d%d",&s1,&s2); update(s1,s2,1,n,1); } query(1,n,1); printf("\n"); }}
HDU1556:Color the ball(简单的线段树区域更新）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。