首页 > 代码库 > HDU 1556 Color the ball 树状数组
HDU 1556 Color the ball 树状数组
Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10150 Accepted Submission(s): 5161
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
31 12 23 331 11 21 30
Sample Output
1 1 13 2 1
Ｎｏｔｅ
道题是一个区间更新，然后单点查询的问题
树状数组，套模版~
#include <cstdio>#include <cmath>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <set>#include <vector>#include <sstream>#include <queue>#include <typeinfo>#include <fstream>typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define maxn 100001int d[maxn];int N,a,b;int lowbit(int x)//求某点的管辖范围{ return x&(-x);}void update(int x,int num)//区间修改 使得a[1]一直修改到a[x]{ while(x>0) { d[x]+=num; x-=lowbit(x); }}int getSum(int x)//单点查询{ int s=0; while(x<=N) { s+=d[x]; x+=lowbit(x); } return s;}int main(){ while(scanf("%d",&N)!=EOF) { if(N==0) break; memset(d,0,sizeof(d)); for(int i=0;i<N;i++) { scanf("%d%d",&a,&b); update(a-1,-1); update(b,1); } int first=1; for(int i=1;i<=N;i++) { if(first==1) { printf("%d",getSum(i)); first=0; } else { printf(" %d",getSum(i)); } } printf("\n"); } return 0;}
HDU 1556 Color the ball 树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。