首页 > 代码库 > Color the ball（hdu1556）（hash）或（线段树，区间更新）
Color the ball（hdu1556）（hash）或（线段树，区间更新）
Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9502 Accepted Submission(s): 4872
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
由于数据比较多所以简单的可以用hash，当然也可以用线段树区间更新！
ps：http://acm.hdu.edu.cn/showproblem.php?pid=1556
hash
#include<stdio.h>#include<string.h>int hash[100002];int main(){ int n,i,x,y,sum; while(scanf("%d",&n),n) { memset(hash,0,sizeof(hash)); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); hash[x]++; hash[y+1]--; } printf("%d",hash[1]); sum=hash[1]; for(i=2;i<=n;i++) { sum+=hash[i]; printf(" %d",sum); } printf("\n"); } return 0;}
线段树区间跟新。
#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#define Lson left,mid,n<<1#define Rson mid+1,right,n<<1|1const int MAX=100001;const int Max=100000<<2;int s[Max];int m;using namespace std;typedef struct Node{ int left; int right; int value;};Node node[Max];void build_tree(int left,int right,int n){ node[n].left=left; node[n].right=right; node[n].value=0; if(node[n].left==node[n].right) return ; int mid=(node[n].left+node[n].right)>>1;//位运算相当于除以2 build_tree(Lson); build_tree(Rson);}void query(int left,int right,int n)//查询{ if(node[n].left>=left&&node[n].right<=right)//找到要涂颜色区间，这里很重要，表示用区间后再慢慢回归到子节点上 { node[n].value+=1; return; } int mid=(node[n].left+node[n].right)>>1; if(right<=mid) query(left,right,n<<1); else if(left>mid) query(left,right,n<<1|1);//相当于2*n+1 else { query(Lson); query(Rson); }} void sum(int n){ if(node[n].left==node[n].right) { s[m]=node[n].value; m+=1; return; } node[n<<1].value+=node[n].value; node[n<<1|1].value+=node[n].value; sum(n<<1); sum(n<<1|1);}int main(){ int n,i,j,a,b; while(scanf("%d",&n)&&n) { build_tree(1,n,1); for(i=0;i<n;i++) { scanf("%d%d",&a,&b); query(a,b,1); } m=0; sum(1); for(i=0;i<m;i++) { if(i==m-1) printf("%d\n",s[i]); else printf("%d ",s[i]); } } return 0;}
Color the ball（hdu1556）（hash）或（线段树，区间更新）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。